Absolute value in objective function of linear optimization

Question

I'm trying to find the solution for the following expression

Objective function:

minimize(| x - c0 | + | y - c1 |)

Constraint:

0 < x < A
0 < y < B

where c0, c1, A, B are positive constants

Following the conversion given in http://lpsolve.sourceforge.net/5.1/absolute.htm

I reworded the expression to

Constraints:

    (x - c0) <= xbar
-1 *(x - c0) <= xbar
    (y - c1) <= ybar
-1 *(y - c1) <= ybar

     0 < x < A
     0 < y < B

Objective function:

minimize(xbar + ybar)

However, I'm not able to implement this. I tried the following snippet

#include "ortools/linear_solver/linear_solver.h"
#include "ortools/linear_solver/linear_expr.h"

MPSolver solver("distanceFinder", MPSolver::GLOP_LINEAR_PROGRAMMING);
MPVariable* x = solver.MakeNumVar(0, A, "x");
MPVariable* y = solver.MakeNumVar(0, B, "y");

const LinearExpr e = x;
const LinearExpr f = y;

LinearExpr X;
LinearExpr Y;

LinearRange Z = slope * e + offset == f; // Where 'slope' & 'offset' are real numbers.
solver.MakeRowConstraint(Z);

const LinearRange r = -1 * (e - c0) <= X;
const LinearRange s = (e - c0]) <= X ;
const LinearRange m = -1 * (f - c1) <= Y;
const LinearRange k = (f - c1) <= Y ;

solver.MakeRowConstraint(r);
solver.MakeRowConstraint(s);
solver.MakeRowConstraint(m);
solver.MakeRowConstraint(k);

MPObjective* const objective = solver.MutableObjective();
objective->MinimizeLinearExpr(X+Y);

I'm getting the error, E0206 16:41:08.889048 80935 linear_solver.cc:1577] No solution exists. MPSolverInterface::result_status_ = MPSOLVER_INFEASIBLE

My use cases always produce feasible solutions (I'm trying to find the least manhattan distance between a point and a line).

I'm very new to using GOOGLE-OR tools. Please suggest any simpler solution I might have overlooked Any help will be appreciated

Thanks, Ram

Q: Have you tried any of these suggestions: http://lpsolve.sourceforge.net/5.5/Infeasible.htm — FoggyDay, Feb 07 '20 at 18:39
Sorry, I forgot to mention.The problem has a feasible solution. I'm having difficulty in the implementation part using Google-OR (C++). Thanks for catching the incompleteness in the question — RamKumar RanjithKumar, Feb 07 '20 at 18:55
No, it sounds like the problem is that the library thinks it's insolvable. The link I cited gives you possible reasons for this. Please review it, and see if it helps. Please update your post with what you tried, and the results. — FoggyDay, Feb 07 '20 at 20:14
X = (x - c0) for x > c0 ; -(x - c0) for x < c0. similarly for Y. this is expressed in the 4 constraints. — RamKumar RanjithKumar, Feb 11 '20 at 18:45

score 0 · Accepted Answer · answered Feb 10 '20 at 13:28

Here is a working example. You mixed up variables in your code

const double A = 10.0;
const double B = 8.0;
const double c0 = 6.0;
const double c1 = 3.5;

MPSolver solver("distanceFinder", MPSolver::GLOP_LINEAR_PROGRAMMING);
MPVariable* x = solver.MakeNumVar(0, A, "x");
MPVariable* y = solver.MakeNumVar(0, B, "y");

MPVariable* xbar = solver.MakeNumVar(0, A, "xbar");
MPVariable* ybar = solver.MakeNumVar(0, B, "ybar");

LinearExpr X(x);
LinearExpr Y(y);

const LinearRange r = -1 * (X - c0) <= xbar;
const LinearRange s = (X - c0) <= xbar;
const LinearRange m = -1 * (Y - c1) <= ybar;
const LinearRange k = (Y - c1) <= ybar;

solver.MakeRowConstraint(r);
solver.MakeRowConstraint(s);
solver.MakeRowConstraint(m);
solver.MakeRowConstraint(k);

MPObjective *const objective = solver.MutableObjective();
objective->MinimizeLinearExpr(LinearExpr(xbar) + LinearExpr(ybar));

It computes

x = 6
y = 3.5
xbar = 0
ybar = -0

thanks for the response. Adding to it, (xbar, ybar) don't need to be within (A, B) limits. So in my code, I've set that to 'infinity'. — RamKumar RanjithKumar, Feb 10 '20 at 18:59

Absolute value in objective function of linear optimization

1 Answers1