I want to simulate a binary variable (Y) within a linear program I am trying something similar to BigM, but I call this LittleM. This is what I am trying:

Y - 0.01 <= 0 + 0.01 * ( 1 - Y ) 0.99 - Y <= 0 + 0.01 * Y Y - 1.01 <= 0 + 0.01 * Y Y <= 1.01

The first equation is TRUE when Y = 0.005, and the other two are FALSE. The second and third equations are TRUE when Y = 0.995, and the first equation is FALSE.

This is saying that either Y <= 0.01 or ( Y >= 0.99 and Y <= 1.01 )

I am using a tolerance of 0.01

This does not work in the LP solver. Any suggestions on how to implement this?

This would allow anyone the ability to use LP solvers to solve MILP.

Regards, Fulton Loebel

asked 17 Oct '17, 14:35

fulton's gravatar image

fulton
111
accept rate: 0%


Abandon all hope. It can't be done. Keep in mind that the feasible region of a linear program is convex. So, regardless of whatever constraints you come up with, if there is a feasible solution (call it S1) where Y = 0, and a feasible solution (S2) where Y = 1, then average 0.5 * S1 + 0.5 * S2 will be a feasible solution (due to convexity) where Y = 0.5.

link

answered 17 Oct '17, 14:56

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

The third equation was mistated. For more readability, the four equations are:

Y - 0.01 <= 0 + 0.01 * ( 1 - Y )

0.99 - Y <= 0 + 0.01 * Y

1.01 - Y <= 0 + 0.01 * Y

Y <= 1.01

link

answered 17 Oct '17, 14:42

fulton's gravatar image

fulton
111
accept rate: 0%

Paul knows whereof he speaks. Integer (binary) constraints are non-convex. You can't possibly capture non-convex constraints with (only) a system of linear inequalities, which is convex. More specifically, your system of inequalities is infeasible. In order to be feasible, a solution Y must simultaneously satisfy all the constraints. By your own admission, for your proposed values of Y, some of the constraints are satisfied, while others are not. Of course, the LP solver declares an LP having your 4 constraints to be infeasible.

(17 Oct '17, 19:22) Mark L Stone
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:

×28
×14
×6
×2
×1

Asked: 17 Oct '17, 14:35

Seen: 330 times

Last updated: 17 Oct '17, 19:22

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