Mixed integer programming: variable assignment per

问题:

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!

回答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.