Nonconvex Combinatorial Optimization without Auxiliary Binary Variables

没有辅助二元变量的非凸组合优化

• 批准号: 0100020
• 负责人: George Nemhauser
• 金额: $ 40.57万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-06-01 至 2005-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0100020&HistoricalAwards=false
• 关键词: Nonconvex; Combinatorial; Optimization; without; Auxiliary

This project is about solving Nonconvex Combinatorial Optimization Problems (NCOPs) by linear programming based branch-and-bound algorithms. Most NCOPs can be reformulated as mixed-integer programs (MIPs) by the addition of auxiliary binary variables. For this reason the study of NCOPs other than MIPs has been very limited. However, reformulation may have many disadvantages including increasing the size of the problem significantly. There are some NCOP structures that arise naturally in many practical applications and therefore merit study in their own right. These include: (1) semi-continuous - if a nonnegative variable is positive, it must be at least some positive constant; (2) k-cardinality - no more than k variables from a set of n nonnegative variables may be positive; (3) special ordered set of type 2 - no more than 2 variables from a sequence of n nonnegative variables may be positive, and if 2 variables are positive, they must be adjacent in the sequence. The primary objective of this project is to study these and a small number of other NCOP structures, as has been done for MIPS, and to develop preprocessing procedures, polyhedral results (cuts), branching procedures, and primal heuristics for dealing with them directly. The end result will be efficient branch-and-cut algorithms for linear programs with piecewise linear nonconvex objectives, nonconvex quadratic programs, scheduling and facility location problems, and several other NP-hard problems for which an MIP approach has not been very successful. Decision making problems in manufacturing and logistics, such as resource allocation and facility location are represented by optimization models. This project contributes to the knowledge of algorithms for solving such optimization models that contain certain types of nonlinearities that make the models very difficult to solve. The results of this project will provide significant enhancements to the optimization tools that are used in practice.

这个项目是关于用基于线性规划的分支定界算法来解决非凸组合优化问题。通过添加辅助二进制变量，可以将大多数NCOP重新表示为混合整数规划(MIP)。因此，对MIP以外的NCOP的研究一直非常有限。然而，重新提法可能有许多缺点，包括显著增加问题的规模。有一些NCOP结构在许多实际应用中是自然出现的，因此它们本身就值得研究。它们包括：(1)半连续--如果一个非负变量为正，则它必须至少是某个正常数；(2)k-基数--一组n个非负变量中不超过k个变量可以为正；(3)第二类特殊有序集--一个由n个非负变量组成的序列中，不超过2个变量可以为正，并且如果2个变量为正，则它们必须在序列中相邻。这个项目的主要目标是研究这些和少数其他NCOP结构，就像对MIPS所做的那样，并开发用于直接处理它们的预处理程序、多面体结果(CUTS)、分支程序和原始启发式算法。最终的结果将是具有分段线性非凸目标的线性规划、非凸二次规划、调度和设施选址问题以及其他几个MIP方法不太成功的NP-Hard问题的有效分枝和切割算法。用最优化模型描述了制造和物流中的资源分配、设施选址等决策问题。这个项目有助于了解用于求解此类优化模型的算法知识，这些优化模型包含使模型非常难以求解的某些类型的非线性。该项目的成果将大大改进实践中使用的优化工具。