Reputation: 668
Typical optimization problem are of the type:
minimize ax + by
x1 <= x <= x2
y1 <= y <= y2
where we can think of a and b as the costs related to the two variables.
Is it possible to solve an optimization problem where variables have multiple possible interval bounds?
Ex.:
minimize x + y
x1 <= x <= x2 OR x3 <= x <= x4
y1 <= y <= y2 OR y3 <= y <= y4
possibly with different costs in the different ranges? I don't know how to express this latter requirement in a formula.
In the documentation I found only a single lower bound and a single upper bound and costs related to variables
Upvotes: 1
Views: 145
Reputation: 16782
Math tells us this is not convex and this we will never be able to formulate this as a pure LP. We can however introduce binary variables (the problem will become a MIP) and write
c1 ≤ x ≤ c2 OR c3 ≤ x ≤ c4
as
δ1 * c1 ≤ x1 ≤ δ1 * c2
δ2 * c3 ≤ x2 ≤ δ2 * c4
δ1 + δ2 = 1
x1 + x2 = x
δ1, δ2 ∈ {0,1}
I assumed the c's are constants for the problem (if not, i.e. they are decision variables, the reformulation is similar but slightly more complicated).
Of course if the c's are ordered we can also do:
c1 ≤ x ≤ c4 (these are bounds)
x <= c2 OR x >= c3
I'll leave that as an exercise (hint: again a binary variable is needed)
Upvotes: 2