Pyomo linearization of min(0,x1-x2) in MILP

Question

I have a constraint in a MILP formulated in pyomo. Thats a general formulation of it:

def constraint(m, t): return (m.y[t] <= max(0,m.x1[t] - m.x2[t])) model.constraint_c = pyo.Constraint(model.timeindex, rule=constraint)

y, x1 and x2 are timeindexed Non Negative Real Variables.

In own words: y should be (x1-x2) only in case (x1-x2) is positive, otherwise y=0.

I found different methods for linearizing the Min/Max function but nothing fits my pupose. Thanks a lot for your help!

Answer 1

y ≤ max(0, x1-x2) is non-convex, so you need binary variables (or something related). We essentially want to implement:

 y ≤ 0 OR y ≤ x1-x2

A formulation is:

 y ≤ M⋅δ
 y ≤ x1-x2+M⋅(1-δ)
 δ ∈ {0,1}

where M is a large enough constant. You need to think carefully about the size of M.

If you don't have good bounds (and M becomes very big), then it is better to use a SOS1 set. E.g.:

 y ≤ s1
 y ≤ x1-x2+s2
 s1,s2 ≥ 0
 s1,s2 ∈ SOS1

In Pyomo it may be easier to use its disjunctive programming tool.