ILOG CPLEX 11.0 User's Manual > Discrete Optimization > Using Column Generation: a Cutting Stock Example > Solving the Problem: Using More than One Algorithm |
Solving the Problem: Using More than One Algorithm |
INDEX PREVIOUS NEXT |
This example does not solve the problem to optimality. It only generates a good feasible solution. It does so by first solving a continuous relaxation of the column-generation problem. In other words, the application drops the requirement for integrality of the variables while the columns are generated. After all columns have been generated for the continuous relaxation, the application keeps the variables generated so far, changes their type to integer, and solves the resulting integer problem.
As you've seen, this example manages two models of the problem, cutOpt
and patGen
. Likewise, it uses two algorithms (that is, two instances of IloCplex
) to solve them.
Here's how to create the first algorithm cutSolver
and extract the initial model cutOpt
:
IloCplex cutSolver(cutOpt); |
And here is how to create the second algorithm and extract the model patGen
:
IloCplex patSolver(patGen); |
The heart of the example is here, in the column generation and optimization over current patterns:
Those lines solve the current subproblem cutOpt
by calling cutSolver.solve
. Then they copy the values of the negative dual solution into the array price
. They use that array to set objective coefficients in the model patGen
. Then they solve the right pattern generation problem.
If the objective value of the subproblem is nonnegative within the tolerance RC_EPS
, then the application has proved that the current solution of the model cutOpt
is optimal within the given optimality tolerance (RC_EPS
). Otherwise, the application copies the solution of the current pattern generation problem into the array newPatt
and uses that new pattern to build the next column to add to the model cutOpt
. Then it repeats the procedure.
Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |