Better algorithms for discrete optimization, with applications

更好的离散优化算法及其应用

• 批准号: 46602-2010
• 负责人: McCormick, Thomas
• 金额: $ 1.75万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=451113
• 关键词: Better; algorithms; discrete; optimization; applications

Many important business activities can usefully be represented as optimization models where we want to find the best possible feasible values of some decision variables that maximize or minimize some objective function. A challenging but important subset of these models require that the decision variables take only integer values. Such "discrete optimization" problems are provably hard in general, but there are many special cases where it can be proved that a fairly simple model has guaranteed integer optimal solutions.

许多重要的业务活动可以有效地表示为优化模型，在这些模型中，我们希望找到一些决策变量的最佳可能的可行值，以最大化或最小化某个目标函数。这些模型中一个具有挑战性但很重要的子集要求决策变量只取整数值。这类“离散优化”问题通常是困难的，但在许多特殊情况下，可以证明一个相当简单的模型保证了整数最优解。