CPLEX: Strange behaviour with big M constraints

 0 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 11●3 accept rate: 0%

 1 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. answered 02 Nov '15, 11:54 Ehsan ♦ 4.8k●3●11●22 accept rate: 16%
 1 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. answered 07 Nov '15, 17:31 Paul Rubin ♦♦ 14.6k●4●12 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 ♦♦
 toggle preview community wiki

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,765 times

Last updated: 09 Nov '15, 09:59

Related questions

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