Is it possible to forbid a LP variable from being a specific constant?

ex X <> 0.5

asked 25 Apr '18, 13:21

gtg489p's gravatar image

gtg489p
3314
accept rate: 0%


No. But you can (at the cost of adding a binary variable) enforce that x is either below \(0.5-\varepsilon\) or above \(0.5+\varepsilon\) where \(\varepsilon>0\) is a small tolerance.

link

answered 25 Apr '18, 13:28

Sune's gravatar image

Sune
958412
accept rate: 20%

That's unfortunate. Adding a binary var would defeat the purpose for me, because formulation is itself an LP relaxation of a MIP.

I guess I could still give it a try; the LP relaxation with those few binary variables may solve much faster than the original IP, maybe even as fast as the pure LP relaxation.

(25 Apr '18, 13:44) gtg489p

Instead of solving one LP, you can solve two:

  1. original LP & x <= 0.5 - \epsilon
  2. original LP & x >= 0.5 + \epsilon

For a suitable \epsilon value, as per Sune's suggestion. You can then process the solutions accordingly (e.g. compare the two solutions, to see which one is actually optimal based on the two objective function values). As long as you have one or a few such variables, this approach should work.

link

answered 26 Apr '18, 15:49

AndyT's gravatar image

AndyT
6788
accept rate: 7%

edited 26 Apr '18, 17:37

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
×14

Asked: 25 Apr '18, 13:21

Seen: 162 times

Last updated: 26 Apr '18, 17:37

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