Абсолютное значение целевой функции линейной оптимизации

Я пытаюсь найти решение для следующего выражения

Целевая функция:

минимизировать (| 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

Целевая функция:

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. Пожалуйста, предложите любое более простое решение, которое я мог упустить из виду. Любая помощь будет оценена по достоинству.

Спасибо, Рам


c++ or-tools linear-programming objective-function absolute-value
person RamKumar RanjithKumar    schedule 07.02.2020    source источник
comment
Вопрос: Пробовали ли вы какое-либо из этих предложений: lpsolve.sourceforge.net/5.5/Infeasible.htm < / а>   -  person FoggyDay    schedule 07.02.2020
comment
Извините, забыл упомянуть, проблема имеет реальное решение. У меня проблемы с реализацией с использованием Google-OR (C ++). Спасибо, что заметили неполноту вопроса   -  person RamKumar RanjithKumar    schedule 07.02.2020
comment
Нет, похоже, проблема в том, что библиотека считает ее неразрешимой. Ссылка, которую я процитировал, дает вам возможные причины этого. Пожалуйста, просмотрите его и посмотрите, поможет ли это. Пожалуйста, обновите свой пост, указав то, что вы пробовали, и результаты.   -  person FoggyDay    schedule 07.02.2020
comment
Где переменные xbar и ybar?   -  person Laurent Perron    schedule 10.02.2020
comment
Я использовал X = xbar; Y = ybar в коде   -  person RamKumar RanjithKumar    schedule 10.02.2020
comment
но X и Y - пустые линейные выражения - ›== 0   -  person Laurent Perron    schedule 11.02.2020
comment
X = (x - c0) для x ›c0; - (x - c0) для x ‹c0. аналогично для Y. это выражается в 4 ограничениях.   -  person RamKumar RanjithKumar    schedule 11.02.2020
comment
сказанное выше верно для минимизации (X + Y)   -  person RamKumar RanjithKumar    schedule 11.02.2020

Ответы (1)


arrow_upward
0
arrow_downward

Вот рабочий пример. Вы перепутали переменные в своем коде

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
person Laurent Perron    schedule 10.02.2020
comment
Спасибо за ответ. Добавляя к нему, (xbar, ybar) не обязательно должны быть в пределах (A, B). Итак, в моем коде я установил для него значение «бесконечность». - person RamKumar RanjithKumar; 10.02.2020