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

点击翻译按钮获取中文摘要

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.