Nonconvex Combinatorial Optimization without Auxiliary Binary Variables

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

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.