Combinatorial Optimization Math Programming

On a previous page we described the general model for the COP and used integer programming (IP) to illustrate it. On this page we repeat the IP model and show other situations arising from mathematical programming where a COP model might be useful. The Optimize add-in discussion includes illustrations where COP is used to solve an IP, an MIP and the fixed charge network design problem.

 Combinatorial Optimization Problem: COP We further describe G as the conjunction of m logical expressions.

Integer Programming

The general IP model is below. For convenience we write the constraints as "less than or equal to".

 Integer Programming Model: IP

To model the IP as a COP we provide explicit expressions for the components of the COP model.

 Integer Programming Model: IP-COP

There are a variety of special cases of the IP model that are easily obtained by modifying the IP-COP. For example the Binary-IP restricts the variables to be 0 or 1.

 Binary IP COP Model: BIP-COP Same as IP-COP except

The Optimize add-in discussion includes an illustration where the IP is solved as COP.

Mixed IP

The Mixed Integer Programming contains some variables that are integer and some that are continuous. In the following we define n variables to be integer and n' variables to be continuous. We use y for the continuous variables and place primes on the parameters for the continuous variables. For convenience we show all the constraints as "less than or equal to" inequalities, however, slight modifications handle all three allowed constraint types.

 Mixed IP Model: MIP

To obtain the COP representation, we first change the model into two parts, one for the integer variables and one for the continuous variables.

 The integer problem has a term in the objective that is the optimum value of the linear program formed by the continuous variables. The linear problem depends on the integer solution. We have changed the constraints to equalities by adding slack variables that allow both positive and negative deviations from the right side. This model has a feasible solution for all x, but solutions that violate the original constraints are penalized.

The COP model for the MIP includes the objective for the continuous problem as a term in the objective. Constraints are included in the continuous problem, so are only explicitly considered in the COP.

 Mixed IP COP Model: MIP-COP

There are methods for solving the MIP directly using branch and bound or cutting planes, so one might ask, why do we change it to a COP? The COP approach is reasonable if there are not too many integer variables, or some feature of the continuous model makes it easy to solve. For problems with small n, using the enumerative methods of COP allows one to use only an LP rather than a specialized MIP algorithm. For other problems, the continuous problem may be easy to solve. This is particularly true if the LP has the form of one the easy problems, such as the min-cost flow or assignment problems.

The Optimize discussion includes illustrations where the method is used for MIP and the fixed charge network design problem using either a min-cost flow or transportation model for the continuous part of the problem.

Operations Research Models and Methods
Internet
by Paul A. Jensen
Copyright 2004 - All rights reserved