Part1: Fixed charges

A careful formulation for a mixed integer program (MIP) can lead to a solution of the model in a reasonable amount of time, while a not-so-careful formulation can make the model practically unsolvable.

The over-riding principle of a careful formulation is to make the feasible region described by the linear programming relaxation as close as possible to the feasible region that contains only feasible integer solutions. A more tightly constrained model is often better than a less tightly constrained model, even if the linear program (LP) sub-problems are more difficult.

To model a fixed charge—a cost that is incurred once when a process is used, but is not proportional to the level of the process—a "Big M" formulation is usually used. The level of the process is a continuous variable y and the "on-off" binary variable is x. The objective function coefficient for y is the cost for each additional unit of y and the coefficient for x is the fixed charge. The constraint that describes the relationship between x and y is “y <= Mx.”

For y to be positive, x must be 1. The value of the constant M has to be large enough so that when x is 1, the constraint does not limit y below its true upper bound.

One might typically choose a very large M that wouldn't limit any of the y variables in the problem and use it everywhere an M is needed. This approach has several drawbacks, including:

• The value of x in the solution to the LP relaxation will be y/M. (Using a minimal amount of x is preferred since the fixed charge will be large relative to the unit cost.) The objective function value then reflects only y/M of the fixed charge. For example, if y is 10 and M is 10000, only 0.001 of the fixed charge is used, which means the relaxation objective value is far from the integer objective value.

• The branching algorithm will likely try to force x to 0 first, and therefore y to 0, because the value of x is already close to 0. That is the LP solution. The LP solution is that y should be positive.

If M is set to the true upper bound of y (15), then the solution to the LP relaxation will be x = 0.6666, so both the objective function value of the relaxation and the x value reflect more closely what will happen when the integer restriction is enforced through branching. The branching algorithm will have a better idea of how to set x, and the bounding process will have better objective value information.

Using priority orders and preferred branching directions can also speed solution of a fixed charge model. ILOG CPLEX allows a preferred branching direction for each variable as well as a default preferred direction. Set the branching direction to "up" for any of the fixed charge (x) variables. The x variables should be assigned a higher ordering value than other integer variables that use x.

If it is not possible to reduce the value of M, ILOG CPLEX does provide an alternative. Indicator constraints can be used in the matrix interface and logical constraints can be used in the object-oriented interfaces.