Nonconvex Combinatorial Optimization without Auxiliary Binary Variables

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

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.