Mixed integer programming: variable assignment per condition (if then else)

Question

I am relatively new to (mixed) integer programming and got stuck with the formulation of a constraint.

In my simplified model I have one Parameter and two Variables that are positive Reals having the value 321 as upper bound. The logic I want to express is here:

if Parameter > Variable1:
    Variable2 = Variable1
else:
    Variable2 = Parameter

**edit** (while Variable1 is always >= Variable2)

Is it actually possible to describe this using linear in(equalities)?

If it helps: For the implementation I am using Python, Pyomo and the newest gurobi solver.

Thanks for your help!

LarrySnyder610 · Accepted Answer · 2015-02-09 12:22:44Z

1

Edit: Setting Variable2 equal to min or max of Variable1 and Parameter.

min(Parameter,Variable1):

If you are sure that Variable2 "wants" to be small in the objective function, then you just need to require Variable2 to be less than or equal to both Parameter and Variable1:

Variable2 <= Variable1
Variable2 <= Parameter

max(Parameter,Variable1):

If you are sure that Variable2 "wants" to be large in the objective function, then you just need to require Variable2 to be greater than or equal to both Parameter and Variable1:

Variable2 >= Variable1
Variable2 >= Parameter

In either case:

If there's a chance that it will be optimal to set Variable2 to something strictly less than min(Parameter,Variable1) / strictly greater than max(Parameter,Variable1), then you will also (in addition to the constraints above) need to introduce a new binary variable that equals 1 if Parameter > Variable1:

Parameter - Variable1 <= M * NewVar
Variable1 - Parameter <= M * (1 - NewVar)

where M is a large number. So, if Parameter > Variable1 then NewVar must equal 1, while if Parameter < Variable1 then NewVar must equal 0.

min(Parameter,Variable1):

Introduce constraints that ensure Variable2 >= min(Parameter,Variable1):

Variable2 >= Parameter - M * NewVar
Variable2 >= Variable1 - M * (1 - NewVar)

So, if Parameter > Variable1 then NewVar = 1, the first constraint has no effect, and the second says Variable2 >= Variable1. If Parameter < Variable1 then NewVar = 0, the first constraint says Variable2 >= Parameter, and the second constraint has no effect.

max(Parameter,Variable1):

Introduce constraints that ensure Variable2 <= max(Parameter,Variable1):

Variable2 <= NewVar * Parameter + M * (1 - NewVar)
Variable2 <= Variable1 + M * NewVar

So, if Parameter > Variable1 then NewVar = 1, the first constraint says Variable2 <= Parameter, and the second constraint has no effect. If Parameter < Variable1 then NewVar = 0, the first constraint has no effect, and the second says Variable2 <= Variable1.

In either case:

Note that M should be as small as possible while still ensuring that triggering the M in the constraint makes the constraint non-binding. I think it's sufficient to set it equal to the largest value that |Parameter - Variable1| can possibly get. In general these "big-Ms" weaken the formulation and result in longer solve times, so you always want them as small as possible.

edited Feb 9, 2015 at 12:22

answered Feb 8, 2015 at 21:25

LarrySnyder610

2,39714 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Cord Kaldemeyer Over a year ago

Thank you for your quick response! I completely forgot to mention that Variable1 must be >= Variable2 (I'll add that to the question). So the solution that Variable2 must be >= max(Parameter,Variable1) does not work in my case. Cheers Cord

Cord Kaldemeyer Over a year ago

But your idea to select the maximum of a variable and a parameter using a big-M constraint is interesting. Is it also possible to select the minimum of a variable and a parameter? In this case I could just solve my problem like this: Variable2 = min(Variable1, Parameter)

LarrySnyder610 Over a year ago

Oops I misinterpreted the OP. You want Variable2 = min(Variable1, Parameter) but I gave you ...=max(...). I will edit my answer. (If Variable2 = min(Variable1, Parameter) then Variable1 >= Variable2 always holds.)

Cord Kaldemeyer Over a year ago

Meanwhile, I could solve the "minimum problem" on my own starting from your "big-M-Max-Formulation". The equations look like yours but my assignment is formulated differently: Variable2 = Variable1 * (1-NewVar) + Parameter * NewVar. Since this leads to a quadratic term it can be linearized like described here. Thanks a lot, you saved my week, grendelsdad !!

LarrySnyder610 Over a year ago

Your linearized assignment constraint is probably the same basic idea as my constraints. Anyway, glad I could help.

|

Collectives™ on Stack Overflow

Mixed integer programming: variable assignment per condition (if then else)

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related