I have an if-then-else condition in one of my constraints and I read online that Big M formulation can actually convert the constraint into a linear one. So, I'd like to ask you guys if my formulation of the constraint is correct or wrong.

subject to Phy {w in PHY, dns in DEMAND}: x_ns[w] := (if
(x_S[dns, w] = 1 or x_P[dns, w] = 1 or x_M[dns, w] = 1 or x_I[dns, w] = 1) then (x_ns[w]) = 1 else (x_ns) = 0);

Now the Big M formulation of the above constraint is as follows:

 5 * x_ns - x_S - x_P - x_M - x_I >= 0 #(constraint 1)
 1 * x_ns - x_S - x_P - x_M - x_I <= 0 #(constraint 2)

Please let me know if this is correct or wrong. Also, I tried using an indicator constraint but I'm having some trouble with it as it always points me to the solution 0.0 Thank You

asked 11 Jun '14, 10:26

crypto's gravatar image

crypto
6727
accept rate: 0%

edited 11 Jun '14, 10:43


I assume all variables are booleans. The second constraint is correct. For the first one, 4 instead of 5 would do it with a smaller big M. However, I would rather write the set of constraints instead:

\[ \begin{align} x_{ns} & \ge x_S\\ x_{ns} & \ge x_P\\ x_{ns} & \ge x_M\\ x_{ns} & \ge x_I \end{align} \]

link

answered 11 Jun '14, 10:43

David's gravatar image

David
30616
accept rate: 12%

edited 11 Jun '14, 11:33

fbahr's gravatar image

fbahr ♦
4.6k716

Yes, all variables are binary and also the constraint you've mentioned could be written but in the objective, what I do is sum up all x_ns' over the number of nodes. So, for every node I'd have only one x_ns. If I follow your formulation, I'm not sure how I can do that. Also do I need both the constraints in my formulation or only one of them would do?

(11 Jun '14, 10:47) crypto

What prevents you to replicate these set of constraints at every node ? I do not understand the relation with the objective function.

(11 Jun '14, 12:48) David

Sorry for the confusion there but when I tried your formulation it provided me the same result the big M formulation provided. Thanks a lot for the answer and I just wanted to implement it using an indicator constraint because the idea sounded cooler but it had a few problems of its own. I'm working on that one as well. So, thanks to your answer I now have three ways to implement the same constraint. Many thanks David

(12 Jun '14, 03:12) crypto

It is a must that any alternative solutions lead to the same optimal solution on small case, otherwise one of the formulation is wrong !

However, some formulations might be better than the other ones, and you will measure it when you do branch & cut. Roughly, you may close the gap much more faster with some formulations rather than others.

(12 Jun '14, 05:31) David
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:

×231
×37

Asked: 11 Jun '14, 10:26

Seen: 1,399 times

Last updated: 12 Jun '14, 06:32

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