CODEWITHSUNDEEP
linear-programmingor-tools
Mert Akozcan
Mert Akozcan

Reputation: 163

OR Tools - Make decision variables as close to each other and as far from boundaries as possible

I have a linear programming question that I couldn't find the correct objective function as I imagined. Here it is:

a1, a2, b1, b2, c1, c2 ∈ Q+

Decision variables:
x: [a1, a2], y: [b1, b2]

Constraints:
(1 - c1) * y >= (1 + c2) * x

As an objective, I'm trying to make x and y as close, make x as far from a1, and make y as far from b2 as possible.

My current objective function is something like this:

max x - a1 + b2 - y

Unfortunately, many times, this objective function either sets x to a1 or y to b2, but as I said, I need x and y close to each other. Could you please help me build the correct approach? Thanks!

As a reference, here's my code written in Python and OR tools:

solver = pywraplp.Solver.CreateSolver("GLOP")

x = solver.NumVar(lb=a1, ub=a2, name="X")
y = solver.NumVar(lb=b1, ub=b2, name="Y")

solver.Add(constraint=(1 - c1) * y >= (1 + c2) * x)

solver.Maximize(x - a1 + b2 - y)

Upvotes: 1

Views: 746

Answers (1)

Tim
Tim

Reputation: 1098

It sounds like what you want is a combination of 2 objectives:

  1. maximize x and y to be away from their bounds, and
  2. minimize the size of the delta between x and y

There are a lot of ways of reformulating this. Here is one that stays within LP.

You can achieve the first part by adding a non-negative amount epsilon that will be a part of all of the constraints you are trying to push away from, l <= r will be rewritten to l + epsilon <= r. Written in math:

max epsilon 
w.r.t.
epsilon >= 0
a1 + epsilon <= x <= a2 - epsilon
b1 + epsilon <= y <= b2 - epsilon
(1 - c1) * y >= (1 + c2) * x

(For fun you can go back and figure out how this transformation creates a d-dimensional cube with sides of length 2*epsilon around a feasible point (x, y). This also means that if any of constraints are "degenerate", epsilon will be 0 and the transformation will not any be able to help.)

The second part can be achieved by minimizing delta = abs(x-y). Instead of capturing the equality exactly, we can instead bound the difference with a variable delta >= abs(x-y). We can write this as:

delta >= x - y >= -delta

And maximize -delta to push x and y closer. (For fun, you can confirm that delta=abs(x-y) in maximal solutions if its objective coefficient is negative.)

We can combine these two objectives by maximizing:

max d1*epsilon - d2*delta  (for d1, d2 in Q+)

The choice of d1 and d2 are up to you though. This might mean that maximizing the combined objective fails to achieve the balance between the two objectives you are going for.

As x and y are bounded, you do not need to worry about feasible unbounded epsilon values.

Upvotes: 2

Related Questions