objective 线性优化函数中的绝对值

Question

我正在尝试为以下表达式找到解决方案

Objective函数：

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

限制条件：

0 < x < A
0 < y < B

其中 c0、c1、A、B 是正常数

按照中给出的转换 http://lpsolve.sourceforge.net/5.1/absolute.htm

我将表达式改写为

约束：

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

     0 < x < A
     0 < y < B

Objective函数：

minimize(xbar + ybar)

但是，我无法实现它。我尝试了以下代码片段

#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);

我遇到了错误， E0206 16:41:08.889048 80935 linear_solver.cc:1577] 无解。 MPSolverInterface::result_status_ = MPSOLVER_INFEASIBLE

我的用例总能产生可行的解决方案（我试图找到点和线之间的最小曼哈顿距离）。

我对使用 GOOGLE-OR 工具还很陌生。请提出我可能忽略的任何更简单的解决方案任何帮助将不胜感激

谢谢，拉姆

Answer 1

这是一个工作示例。您在代码中混淆了变量

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));

它计算

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

objective 线性优化函数中的绝对值

Absolute value in objective function of linear optimization

c++

linear-programming

or-tools

absolute-value

objective-function