Originally posted by: NMaichel

I am having difficulty solving the root in a large MIP. I think the issues are due to degeneracy because the model performs thousands of consecutive iterations and the objective function value does not change. The root has a large network component, and after this is solved, simplex is called to solve the rest of the model. In about 10 minutes and 270000 iterations, the objective function value is changing very little and a perturbation is removed. After the perturbation is removed, simplex proceeds for over two hours with the objective function very nearly constant before it stops with the optimal solution. Also, after the perturbation is removed, the rate at which iterations are performed decreases significantly with the speed before the perturbation is removed being ~50 times greater than after. I tried running the model as a strict LP, explicitly declaring the binary variables to be linear bounded by 0 and 1. This model solved in 10 minutes and solves very quickly after the perturbation is removed. What is the difference between the linear relaxation of the root that CPLEX solves in the MIP and the same model with the binary variables relaxed to linear variables? I have attached the logfiles for both of these instances. The MIP log is at the top of the file followed by the log for the explicit linear relaxation of the MIP.

Thank you,
Nathan
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> NMaichel wrote:
> What is the difference between the linear relaxation of the root that CPLEX solves in the MIP and the same model with the binary variables relaxed to linear variables?

One difference is that in the first instance the presolver may use the fact that the binary variables are declared binary to perform reductions on the problem that will not happen when the LP is presolved. You could try turning off presolving of both the MIP and relaxed LP and see if the solution times converge (although they may converge to a larger value).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RWunderling

nathan,

it looks like you turned off presolve in both runs, so presolve is not a likely culprit. However, you also seem to have changed the markowitz tolerance to a very conservative value of 0.99999 for the first run but not for the second. This could explain the difference of the time per iteration you observerd.
It also suggest that the problem you solves is numerically challenging. With such models it is not
uncommon to observe large differences in performance just due to random changes in the solution path.
In addition, for the pure LP run, you have relaxed the feasibility tolerance to 1e-5 in the relaxation
run but not for the MIP, which can further explain the difference.

That said, I would be interested in taking a more detailed look if you agree to email it to me directly
or ftp it if the size is too large following these steps:

ftp testcase.boulder.ibm.com
login anonymous
password = <your e-mail address>
> cd /software/toibm/ilog
> bin (use binary file transfer for all compressed files)
> put <file name>
> quit

Thanks,

• Roland

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: NMaichel

Thank you for the suggestions. I tried changing the parameters that you noted were different but got the same result.

I sent the mps file of the model to you via ftp and hope you received it successfully.

Thanks,
Nathan
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: NMaichel

I am still confused about why there is a difference between the root relaxation of the MIP that CPLEX solves and my linear relaxation. The mps files for the MIP and my linear relaxation were completely identical except for two header lines stating that certain variables in the MIP were integer.

Also, I wrote out the optimal basis from my linear relaxation and used it as a starting point for the MIP. Starting with this basis, I used primal simplex to solve the root. The solution is not initially optimal, but must perform thousands of iterations to reach optimality. The reported objective value (16 digits displayed) never changes during the solution process. I also tried dual simplex to solve the root starting with the same basis, and it also performed thousands of iterations before it reached optimality. With the starting basis, both were feasible and had the same objective function value. If the basis that was optimal for my linear relaxation was both primal and dual feasible with the same objective function values for the MIP root relaxation, why was it not initially optimal? Here are some excerpts from the log files.

Using primal simplex to solve the root

Iteration log . . .
Iteration:     1    Objective     =    2337275937.910040
Iteration:  1178    Objective     =    2337275937.910040
Iteration:  2362    Objective     =    2337275937.910040
Iteration:  3545    Objective     =    2337275937.910040
Iteration:  4731    Objective     =    2337275937.910040
Iteration:  5920    Objective     =    2337275937.910040
Elapsed time =   11.28 sec. (6000 iterations)
Iteration:  7108    Objective     =    2337275937.910040
*
*
*
Iteration: 58511    Objective     =    2337275937.910040
Iteration: 59625    Objective     =    2337275937.910040
Root relaxation solution time =  126.17 sec.

Using dual simplex to solve the root

Iteration log . . .
Iteration:     1   Dual objective     =    2337275937.910040
Elapsed time =   88.62 sec. (1000 iterations)
Iteration:  1178   Dual objective     =    2337275937.910040
Elapsed time =  188.53 sec. (2000 iterations)
Iteration:  2362   Dual objective     =    2337275937.910040

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Is your root LP dual degenerate (multiple optima)? Given the size of the objective value, I would not be surprised if you were experiencing rounding error in the computation of reduced costs. So CPLEX might view the initial basis you supplied as feasible but not optimal, because reduced costs that were (internally) zero when you generated that basis now look like +/- epsilon. If the basis is dual degenerate, it could go off on an unnecessary snark hunt. (This is also possible if it's primal degenerate.)

You might also ask CPLEX to print the kappa (condition) number for the basis. If it's large, you may be looking at numerical instability problems.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: NMaichel

I have resolved the problems in solving the root. The problems were due to degeneracy and the perturbations performed by CPLEX were unable to solve the problem in a timely manner. By slightly modifying my objective function, I was able to rid my problem of the multiple optima causing the degeneracy while still mostly preserving the integrity of the original problem. Thank you for the help.

Nathan
#CPLEXOptimizers
#DecisionOptimization