2
$\begingroup$

I am trying to implement benders decomposition for a simple two stage unit commitment problem. I implemented the classic Benders decomposition to add feasible cut and optimal cut to relax master problem by solving the dual of sub-problem. When I use a 6bus system it works fine, however when I change to a larger system (ex: 118bus) the coefficient of the cut started to become ill-conditioned and the result cannot be found. For example：

 ...13.6 onOff(gen30)(time22)#2291- 12 onOff(gen30)(time23)#2292+ 1.4210854715202e-14 onOff(gen30)(time24)#2293...

the coefficient of variable onOff(gen30)(time24) should to zero and the variable should not be included into the constraints and the warning below is also given.

Detected nonzero <= CPX_MINBOUND at constraint 7878, variable 'onOff[gen30][time24]'

My questions are listed as follow:

  1. As far as I know cplex will treat the value below 1e-9 as zero. I wonder if the above problem will be the reason that my program fail or I need to look at different direction?
  2. The following warning also repeatedly appear but the coefficient seem to be normal 16.4799999999999 onOff(gen22)(time13)#2090. I would be grateful if you could give some explanation regarding to the meaning of this warning!

Detected nonzero <= the maximum value of either CPX_PARAM_EPRHS or CPX_PARAM_EPOPT at constraint 7824, variable 'onOff[gen22][time13]'

  1. A large scale problem such as this one, is there any method to improve the numerical stability of the cut? I think the above coefficient should be 16.48 rather than 16.4799999999999 and the coefficient such as 1.4210854715202e-14 should not have happened in the first place. I should mention that I also use IloRound to any master binary variable, but it does not seem to change anything.

I should note that I am using Cplex 12.9 and C++ technology concert.

I would be grateful if you could help me out !

Best regards,

Improve this question
$\endgroup$
2
$\begingroup$
  1. CPLEX treats certain small values as negligible for purposes of constraint satisfaction (including satisfying integrality constraints). That does not mean it automatically rounds small values to zero. If the coefficient 1.4210854715202e-14 in your cut is the value of a dual variable from a subproblem, it is up to you to decide whether to round it to zero when constructing the cut or leave it as it is.
  2. Are you sure that the warning applies to the coefficient 16.47999...? Might you be looking at the wrong constraint? The value 16.48(ish) should not be less than either of the mentioned bounds, unless you changed one of those parameters to an unusually large value.
  3. For certain sources of instability (such as the notorious "big M" constraint), you may be able to mitigate stability issues by either changing the model in a fundamental way, scaling things better, or just finding a tighter value of M. Otherwise, it's a hit-and-miss thing. You can try rounding/truncating dual values a bit before creating Benders cuts (in particular, rounding anything times 10^-14 to 0) and see what happens. Also, keep in mind that the CPLEX messages are just warnings of a possible issue, not guarantees that your results are buggered. If your model is producing plausible answers, it may not need any fixing.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Sir first of all thank you for the reply! I am curious about how to truncate/ round a variable in systematic way. The only way I think of is using if statement to check every coefficient before I multiply it with variable, but I think it will be very hard to maintain once the problem become too complicated. $\endgroup$
    – Lee Adolin
    Apr 15 at 12:05
  • 1
    $\begingroup$ I would use an if statement, and I don't think it's that hard to maintain. To screen out small numbers, after getting the value of a variable in the subproblem dual, just compare it to some predefined cutoff and either keep the value or replace it with zero. In fact, you might define your own "get value" function that calls the CPLEX getValue function and then does the truncation check before returning a value. Use that anywhere you would have called getValue. $\endgroup$
    – prubin
    Apr 15 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.