Dear, Would you please help me answer some questions regard to using big M constraints in cplex solver? I have an optimization problem containing big M constraints, such as, a - b - M*c >= -M. The purpose of the constraint is c = 1 -> a>=b; I set M as MAX_INT. I observed that with default integrality tolerance value (1e-5), cplex solver produces solution but violates the constraint above, for example, c=0.99... and a < b (instead of a >= b). Then I reduce the integrality tolerance (tol) value from 1e-5 to 1e-15, I observed that with tol= 1e-7 cplex produces solution that satisfies all constraints, but with tol=1e-10 cplex produces solution that does not satisfies the constraint above. I do not understand the behaviour. Can you please help me explain that ? Additionally, with tol= 1e-7 and tol = 1e-14 cplex produces solutions that satisfy all constraints, but the optimal values that cplex produces in these two cases are different. I though there is only one optimal solution, but here cplex produces different optimal points with different integrality tolerance values. Would you please help me explain that ?

Thank you so much.

asked 01 Nov '15, 18:07

Nero's gravatar image

Nero
113
accept rate: 0%


Ehsan is correct that large values of M are a known source of numerical instability. Also, you may need to worry about more than just the integrality tolerance; the constraint tolerance will determine whether a value of \(a\) slightly less than \(b\) is accepted as feasible.

If you cannot find a reasonably small value of M that is valid, you might want to do a search for "combinatorial Benders cuts" -- Benders decomposition to eliminate the need for big M versions of logical implication constraints.

link

answered 07 Nov '15, 17:31

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

For example, I have a conditional constraint: if c = 1 --> a >= b Using big M-constraint the constraint will be modelled as: a - b + (1-c)*M >=0. Can you please give me an example about using combinatorial benders cuts to model the problem (in interactive optimizer)?

Thank you so much.

(09 Nov '15, 07:48) Nero

The interactive optimizer is unsuitable for any sort of decomposition method, including Benders. You would have to use one of the programming APIs (or possibly OPL models and a script to let them interact). CPLEX ships with source code for a number of examples, and I believe there is at least one Benders example among them. A reference for combinatorial Benders cuts is "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming" by Gianni Codato and Matteo Fischetti (Operations Research vol. 54, no. 4, 2006).

(09 Nov '15, 09:59) Paul Rubin ♦♦

Choosing very large big-M values could cause numerical instability. You should try finding the smallest value for each big-M constraint that would ensure accepting all the feasible solutions and rejecting the infeasible ones. This could be done either based on a structural property of the problem data or trial and error.

link

answered 02 Nov '15, 11:54

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×71
×1

Asked: 01 Nov '15, 18:07

Seen: 1,766 times

Last updated: 09 Nov '15, 09:59

OR-Exchange! Your site for questions, answers, and announcements about operations research.