CODEWITHSUNDEEP
linear-programmingglpk
sthor69
sthor69

Reputation: 668

Is it possible to define a multi bound optimization problem in GLPK?

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

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16797

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

Related Questions