A New Reformulation Technique for Tightening Relaxations of Some Combinatorial Optimization Problems with Application tothe General Linear Complementarity Problem

这一建议涉及一种新的组合问题的重构技术，该组合问题可以建模为混合0-1规划问题。该模型可以包括连续变量中没有乘积的多项式项。然而，研究集中在两个重要的、一般性的子类，它们出现在许多工程、经济和工业应用中，即线性混合整数零-1规划问题和线性互补问题(LCP)。重构技术使用变量因子的枚举来乘以约束，并创建新的非线性约束，然后通过定义新的变量来线性化这些约束。其动机是提供一个紧线性规划松弛，该松弛近似于可行解的凸壳，从而允许离散优化技术的成功应用。据推测，这种技术确实刻画了二元背包问题可行解的凸包(我们已经在二维和三维验证了这一点)，因此对于非结构化的稀疏问题将特别有用。在此基础上提出了各种实现方案和约束生成步骤，以供研究。作为一种特殊的测试用例，同时也为了研究一个本身具有重要意义的问题，我们提出了一个针对一般LCP的详细算法。该算法包括使用新的重构技术以及其他专门的构造，如基于问题的新观点的增强的凸性切割。提出了一项研究计划，这将为将这一研究努力扩展到为利用这种重构策略的各种问题开发有效的算法奠定基础。

This proposal deals with a novel reformulation technique for combinatorial problems which can be modelled as mixed zero-one programming problems. The model may include polynomial terms without products among continuous variables. The research, however, concentrates on two important, general subclasses which arise in numerous engineering, economic and industrial applications, namely, the linear mixed-integer zero-one programming problem and the linear complementarity problem (LCP). The reformulation technique uses an enumeration of variable factors to multiply constraints and create new nonlinear constraints which are subsequently linearized by defining new variables. The motivation is to provide a tight linear programming relaxation which closely approximates the convex hull of feasible solutions and hence admits a successful application of discrete optimization techniques. It is conjectured that this technique indeed characterizes the convex hull of feasible solutions for binary knapsack problems (we have verified this for two and three dimensions), and therefore would be particularly beneficial for unstructured, sparse problems. Various implementation schemes and constraint generation procedures based on this reformulation are proposed for investigation. As a special test case, and also to study a problem important in its own right, we propose an elaborate algorithm for the general LCP. The algorithm includes the use of the new reformulation technique as well as other specialized constructs such as strengthened convexity cuts based on new viewpoints of the problem. A plan for research is proposed which will lay the groundwork for extending this research effort into developing effective algorithms for a rich variety of problems which exploit this reformulation strategy.