Branch-and-Cut for Combinatorial Optimization Problems without Auxiliary Binary Variables Ismael Regis de Farias Jr., ABSTRACT: A large number of optimization problems involve combinatorial constraints on continuous variables. Typical examples include cardinality constraints, semi-continuous variables, and special ordered sets. Traditionally, these problems have been modeled as mixed-integer programs (MIP) by introducing auxiliary binary variables and integer constraints. Because the number of variables and constraints becomes larger and the combinatorial structure is not used to advantage, these MIPs may not be solved satisfactoraly, except for small instances. I will present an alternative branch-and-cut approach for these problems that dispenses with auxiliary binary variables. I will discuss why this approach can be more practical than traditional MIP, and I will report encouraging computational results on general MIPs, cardinality constrained problems, the generalized assignment problem, and p-median. Bibliography: Branch-and-cut for combinatorial optimization problems without auxiliary binary variables, Knowledge Engineering Review 16, 25-39 (2001), with E.L. Johnson and G.L. Nemhauser. Semi-continuous cuts for mixed-integer programming, working paper, CORE (2002). A polyhedral study of the cardinality constrained knapsack problem, working paper, CORE (2002), with G.L. Nemhauser (.pdf). A branch-and-cut algorithm for quadratic programming over a box, working paper, CORE (2002). With D. Vandenbussche and G.L. Nemhauser. Facets of the complementarity knapsack polytope, to appear in Mathematics of Operations Research, with E.L. Johnson and G.L. Nemhauser (.pdf). Branch-and-cut for transportation problems with piecewise linear cost functions, working paper, CORE (2002), with A. Keha and G.L. Nemhauser. A generalized assignment problem with special ordered sets: a polyhedral study, Mathematical programming 89, 187-203 (2000), with E.L. Johnson and G.L. Nemhauser. A family of inequalities for the generalized assignment polytope, Operations Research Letters 29, 49-51 (2001), with G.L. Nemhauser. A family of facets for the uncapacitated p-median polytope, Operations Research Letters 28, 161-167 (2001). Actualizado em 15 de Março de 2002 por João Soares |