Originally posted by: derekan

Hello, everyone

I am using Benders Decomposition for an extension of location-transportation problem.

The original MIP is decomposed into two problems: MP determines the location of facilities(binary variables) and SP determines the routing of commodities (continuous variables)

The subproblem is using its dual formulation. After solving the subproblem, I use getValue() to obtain values of multipliers that are needed to generate benders cuts in each iteration.

I would say this is a rather simple application of Cplex, in my model there is no infeasibility issue (for any facility location generated by MP, SP is always feasible), so I do not need to consider finding extreme rays and adding feasibility cuts.

But when I run the code for some cases, the results are not correct (I can simply let Cplex to solve the whole model and compare the results), the Benders code terminate with a solution that is inferior to the real optimal solution and with the gap less than 0. Definitely, there is something wrong with the multipliers I get from the subproblem, another possibility is that the master problem cut off the optimal solution.

Note that the Cplex works well for some cases, so I guess this is a technical problem of Cplex.

Thank you in advance and any suggestion is welcomed
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: derekan

"gap less than 0"

I mean the gap between the lower bound found by MP and the best feasible solution.

For the MP, I use the default tolerance "0.0001"
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

How do you add cuts to the master (if callbacks, what kind)? Do you check the subproblem status when you get a dual solution?

Also, which version of CPLEX are you using?

FWIW, I and quite a few others have had success with Benders using CPLEX.

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: derekan

Paul，

Thank you for your response,
The version is 12.1

I check the subproblem status and it is "optimal" in each iteration(note that my model has no feasibility issue)

As I said before, this is a rather simple application of Cplex on Benders Decomposition, I do not use "callback" stuff,
I simply use the instruction mod.add(eta >= rhs) to add a new benders cut, the multipliers in rhs are obtained through using cplex.getValue() after solving the dual of the subproblem.

hope that's enough for you to diagnose my problem
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Ed answered your other questions, so I'll focus on the bug. I would suggest evaluating each cut at the known optimal solution. See if the true optimum violates one of the cuts. If so, export the subproblem that produced the cut and the master that led to that subproblem as SAV files and sees if you get the same solutions to them in the interactive optimizer.

If the true optimum satisfies all the cuts, then it may be that a presolve reduction is causing problems (possibly due to numerical instability). We can cross that bridge if we get to it.

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: derekan

Hi,Paul

I am new to Cplex, so I don't know the concept of callback.

Is it possible that different kind of "callback" will influence the value of multipliers?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I would recommend adapting your "full" model to make your binary variables parameters, solve one instance, and compare to your dual solution (ie, solve both the primal and dual for one set of binary variables and verify that the objective values matchup as a way of checking that your dual is properly formulated). If your dual problem is properly formulated, then attack the cuts (verify that they are cutting off non-optimal solutions. If one is cutting off the true optimal, try and examine it closer and determine why. It is tedious but necessary).

Callbacks are a method to add cuts during the search rather than solving the problem entirely, adding a cut, and starting from scratch. They will most likely speed up your problem but if you are not comfortable using them, it would be a good idea to continue solving the way you currently do until you can at least verify that the problems are being solved correctly, then consider adapting your problem to callbacks. That's just what I would do.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Also, I believe there is an example of Bender's Decomposition with callbacks distributed with v12.3 and later that is not with 12.1 (at least for the python API, that is what I used). You may want to download a new version to get it.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: derekan

Thank you so much, Eumpfenbach and Paul

Today, I picked several wrong cases and did some experiments that are easier to implement than you suggested:

here is the output of a wrong case:

Iter 0: gap is:1
+++++++++++++++++++++++++++
Iter 1: gap is:0.810442
+++++++++++++++++++++++++++
Iter 2: gap is:0.358167
+++++++++++++++++++++++++++
Iter 3: gap is:0.0690513
+++++++++++++++++++++++++++
Iter 4: gap is:<0

Then in the Master problem of Iter 4, I forced the solution to be the real optimal solution (real optimal facility location in my model) by adding constraints, the results are:

Iter 0: gap is:1
+++++++++++++++++++++++++++
Iter 1: gap is:0.810442
+++++++++++++++++++++++++++
Iter 2: gap is:0.358167
+++++++++++++++++++++++++++
Iter 3: gap is:0.0690513
+++++++++++++++++++++++++++
Iter 4: gap is:0.0895883 (MP is still feasible)

Note that if the optimal solution is cut off, the MP should be infeasible.

I think this result means that the new benders cuts do not cut off the real solution (the same is true for other wrong cases too), I guess the problem lies in the master problem. Maybe the "numerical instability" is the reason.

I do not know too much about how Cplex works, is this easy to solve?

I also turned off presolve by adding: cplex.setParam(cplex.PreInd, 0)

but the code still went wrong,
Iter 0: gap is:1
+++++++++++++++++++++++++++
Iter 1: gap is:0.32446
+++++++++++++++++++++++++++
Iter 2: gap is:0.21922
+++++++++++++++++++++++++++
Iter 3: MP infeasible
if I turn off the presolve and force the solution (of MP at Iter 3) to be the real optimal:

Iter 0: gap is:1
+++++++++++++++++++++++++++
Iter 1: gap is:0.32446
+++++++++++++++++++++++++++
Iter 2: gap is:0.21922
+++++++++++++++++++++++++++
Iter 3: gap is:0.123402 (MP is still feasible)

So I think now the problem is pretty clear, it is the Cplex that solves MP causing the problem.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: derekan

The output are all from the same wrong case

Also currently, I use the default settings of MP's Cplex.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You can try turning on the NumericalEmphasis parameter, which will push CPLEX to be more careful if it thinks it sees possible numerical instability (at the cost of slowing down the computations a bit). You might also set the MIPKappaStats parameter to 2. When CPLEX gets done solving the master, you can inspect the distribution of basis condition numbers (kappa values) and see if there are signs of numerical instability.

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: T_O

Did you remember that you also have to obtain dual multipliers for the variable bounds in order to find the correct cuts?

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: derekan

Thank you for your advice.

I compared the obj value of dual subproblem and the prime subproblem and they are the same.

now let's focus on the MP.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: derekan

Thank you for your suggestion

I tried to set NumericalEmphasis to 1 and the result is exactly the same, the output did not change a bit:

Iter 0: gap is:1
+++++++++++++++++++++++++++
Iter 1: gap is:0.810442
+++++++++++++++++++++++++++
Iter 2: gap is:0.358167
+++++++++++++++++++++++++++
Iter 3: gap is:0.0690513
+++++++++++++++++++++++++++
Iter 4: gap is:<0
Since my version is 12.1 it seems that Cplex does not know what MIPKappaStats is. Sorry for that, is there another way to detect numerical instability? is "numerical instability" the only possible way that can result in a wrong solution of MIP?
Also, I read an online article that discuss how to overcome numerical instability. According to what it says, I changed some parameters relating to barrier algorithm (BarAlg, BarMaxCor, BarStartAlg, BarOrder), but the output remain unchanged.

This is really a tough problem for me, thank you again for your help.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> derekan wrote:
> Since my version is 12.1 it seems that Cplex does not know what MIPKappaStats is. Sorry for that, is there another way to detect numerical instability?

Run the interactive optimizer and see if it recognizes DIsplay SOlution Kappa when solving an LP. If so, write the master to a SAV file, load it into the interactive optimizer, relax it to an LP, solve it and display kappa, which will be the condition number for the final basis (not the full picture, but better than nothing).

> is "numerical instability" the only possible way that can result in a wrong solution of MIP?

A bug in CPLEX is possible (but not terribly likely). A bug in your code is of course also possible. Sometimes, I think, people forget that CPLEX has both an absolute and a relative optimality tolerance. Sometimes one of them triggers a halt while the user is looking at/relying on the other one.

And, of course, there are always gremlins to contend with. :-)

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: derekan2

"Sometimes, I think, people forget that CPLEX has both an absolute and a relative optimality tolerance. Sometimes one of them triggers a halt while the user is looking at/relying on the other one."

Paul, could you explain this in detail?
How should I set the parameters to avoid this problem?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> derekan2 wrote:
> "Sometimes, I think, people forget that CPLEX has both an absolute and a relative optimality tolerance. Sometimes one of them triggers a halt while the user is looking at/relying on the other one."
>
> Paul, could you explain this in detail?
> How should I set the parameters to avoid this problem?

See the section CPLEX > Parameters of CPLEX > Parameters Reference Manual > Topical list of parameters > MIP tolerances in the user's manual. The two parameters in question are EpAGap (default 1e-6) and EpGap (default EpGap). CPLEX stops if either the incumbent solution's objective value is within EpAGap of the best node bound or |best node objective -best integer objective|/(1e-10 + |best integer objective|) is less than EpGap. Not knowing your master problem objective values, I can't say more, but you can compare the objective value of the falsely "optimal" solution in MP #4 with the best node bound at termination and see if one or the other of these triggered premature termination of the solution process.

I'll also mention ObjDif (absolute) and RelObjDif (relative), which can be used to speed pruning by telling CPLEX to ignore solutions that are not at least ObjDif and RelObjDif better than the current incumbent. The default values are both zero, so unless you specifically set nonzero values, these are not involved with your problem. If you did set nonzero values for either of them in the master problem, they may be causing CPLEX to quit with a suboptimal solution.

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: Eumpfenbach

No offense intended Derekan, but searching for a problem in cplex or its settings is probably not going to be fruitful. If Cplex solves your non-decomposed problem fine, I see it as unlikely it wouldn't solve your decomposed problem fine (with maybe a slight tolerance/optimality gap). You are doing something analogous to trying to build a car yourself and then wondering when it doesn't run as well as a Ford. It's possible the pieces are defective, but there is a whole lot more room for error in putting them together.

Did you look at the example distributed with Cplex? Do you have a professor/student/coworker who can verify your model/code? Have you checked if your cuts violate the true solution? Have you checked the subproblem when the cut that cuts off the optimal solution is solved (as described before, formulate the primal, fix the binaries, check the objective value/solution/duals match up)? Do the objective values at each iteration match up with what you would expect (the sum of the binary variables from the master and the dual objective)?

It's a lot of work to verify and I know you said you have checked your code thoroughly, but sometimes bugs sneak by in code after 10 times checking. I would suggest rigorously checking your master, subproblem, and cuts, and comparing them to known solutions before trying to pin it on a cplex issue/setting. If you have done all or most of this, then sorry, I don't have anything else to recommend.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: derekan2

Hi,Paul

I ran my code using Cplex12.5 today:

The result is still wrong,

The Kappa value are shown for each iteration:
Max Kappa Value = 9
Percentage of numerically stable simplex bases = 1
Percentage of numerically unstable simplex bases = 0
Kappa attention Value = 0
Iter 0: gap is:1
+++++++++++++++++++++++++++
Max Kappa Value = 196.062
Percentage of numerically stable simplex bases = 1
Percentage of numerically unstable simplex bases = 0
Kappa attention Value = 0
Iter 1: gap is:0.763409
+++++++++++++++++++++++++++
Max Kappa Value = 31712.3
Percentage of numerically stable simplex bases = 1
Percentage of numerically unstable simplex bases = 0
Kappa attention Value = 0
Iter 2: gap is:0.0848744
+++++++++++++++++++++++++++
Max Kappa Value = 57005.1
Percentage of numerically stable simplex bases = 1
Percentage of numerically unstable simplex bases = 0
Kappa attention Value = 0
Iter 3: gap is:0.224525
+++++++++++++++++++++++++++
Max Kappa Value = 5193.67
Percentage of numerically stable simplex bases = 1
Percentage of numerically unstable simplex bases = 0
Kappa attention Value = 0
Iter 4: gap is:-0.00283963
+++++++++++++++++++++++++++

Is there a sign of numerical instability? I think the MP in iter 4 is not minimized at all(see my previous posts)

I've gone through my code many times before I post here, so let's suppose that cplex have some problem in solving MP (a mixed integer problem).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The kappa values are fine, so apparently numerical instability (in the master problem) is not the issue.

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: derekan

For this wrong case I am talking about:

here is the output of a wrong case:

Iter 0: gap is:1
+++++++++++++++++++++++++++
Iter 1: gap is:0.810442
+++++++++++++++++++++++++++
Iter 2: gap is:0.358167
+++++++++++++++++++++++++++
Iter 3: gap is:0.0690513
+++++++++++++++++++++++++++
Iter 4: gap is:<0

I attach the output of MP at Iter 4.
It seems that 4.51018e11 (wrong sln) is the starting solution, and MP cutoff other better solutions, MP is not minimized at all.
#CPLEXOptimizers
#DecisionOptimization