Общая математика Apache 3: всегда получать UnboundedSolutionException при построении модели

Я хочу решить следующую модель с помощью Commons Math 3 от Apache:

maximize: 30x + 40y
s.t. x+y <= 240; 2x+y <= 320; x,y>=0;

Мой код, связанный с документами, должен быть:

        // objective f = 30x + 40y + 0
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 30, 40},0);


        List<LinearConstraint> constraints = new ArrayList();

        // x + y <= 240
        constraints.add(new LinearConstraint(new double[] {1, 1}, Relationship.LEQ, 240));
        // x + y <= 320
        constraints.add(new LinearConstraint(new double[] {2, 1}, Relationship.LEQ, 320));
        // x,y >=0
        NonNegativeConstraint nonNegativeConstraint = new NonNegativeConstraint(false);


        LinearConstraintSet constraintSet = new LinearConstraintSet(constraints);
        SimplexSolver linearOptimizer = new SimplexSolver();
        // put everything together in order to get a maximization problem
        // in the next line i receive org.apache.commons.math3.optim.linear.UnboundedSolutionException: unbounded solution
        PointValuePair solution = linearOptimizer.optimize(f, constraintSet, GoalType.MAXIMIZE, nonNegativeConstraint);


        if (solution != null) {
            //get solution
            double max = solution.getValue();
            System.out.println("Opt: " + max);
        }

Но каждый раз, когда вызывается linearOptimizer.optimize, я получаю: org.apache.commons.math3.optim.linear.UnboundedSolutionException. Документы говорят:

открытый класс UnboundedSolutionException extends MathIllegalStateException Этот класс представляет исключения, создаваемые оптимизаторами, когда решение уходит в бесконечность.

Но я решил эту проблему оптимизации с помощью графического интерфейса LPSolve, и это дает мне решение x=0; y=240; f(x,y)=9600. Так что я предполагаю, что я делаю что-то не так.

1) Любая идея, что я делаю неправильно?

2) Я прочитал этот сообщение, которое было 4 года назад и было написано с использованием математической библиотеки Commons (не math3). Есть ли сейчас возможность сказать, что некоторые переменные решения должны быть целыми, бинарными и т.д.? В противном случае я бы запрограммировал Branch and Bound -appoach вручную, чтобы архивировать это.

Буду очень рад вашей помощи и любым идеям.

Большое спасибо :-)




Ответы (2)


Никогда не использовал эту библиотеку, но документы говорят вам следующее:

общественное NonNegativeConstraint (логическое ограничение)

Параметры:

limited — если true, все переменные должны быть положительными.

А вы делаете ровно наоборот:

NonNegativeConstraint nonNegativeConstraint = new NegativeConstraint(false);

Читая документы, я сильно склоняюсь к тому, что целочисленное программирование не поддерживается.

person sascha    schedule 28.05.2017
comment
Ах, это решило проблему, спасибо! Итак, в моем решении ранее я сказал: каждая переменная решения может быть отрицательной и положительной, вместо того, чтобы каждая переменная решения должна быть 0 или положительной. Поэтому имеет смысл, что существуют неограниченные значения решения. Я ищу хорошую библиотеку оптимизации. Было бы здорово, если бы он был с открытым исходным кодом. В моем исследовании я работал только с коммерческим инструментом ibm ilog cplex, и это было здорово. Choco CP Solver был отличной альтернативой, но он не поддерживает двойное решение (только целые и двоичные). У вас есть отличная альтернатива? - person Andy; 28.05.2017
comment
Технически вы сказали: add no nonnegativity constraints. Вместе с предположением, что переменные по умолчанию бесплатны (что, вероятно, скрыто где-то в документах), все работает, как и ожидалось. Но имейте в виду, что это предположение часто отличается. Пример: почти все решатели, основанные на методе внутренних точек (не в вашей библиотеке), используют теоретический план, который допускает только неотрицательные переменные (естественная форма и свободные переменные требуют особого внимания;). - person sascha; 28.05.2017
comment
Существует огромный разрыв между бесплатными и несвободными (M)IP-решателями (особенно если задействованы двоичные/целые числа; в чистом случае LP это в большинстве случаев легко решить). Игнорируя Чоко и компанию. (это совершенно другой подход, в основном решающий другие проблемы), мой рейтинг бесплатных решателей таков: CBC > GLPK > LPsolve, причем GLPK и LPsolve имеют лучшую документацию на сегодняшний день! Примечание: когда я играл с Choco, я видел, что есть рациональная поддержка (или назовите ее поплавками), но ее проблематично установить. Но имейте в виду, что CP сильно отличается от MIP. Особенно сложно оптимизировать цели. - person sascha; 28.05.2017
comment
Спасибо за такую ​​подробную информацию! Я также видел SCIP-решатель. Есть ли особая причина, по которой все эти решатели написаны на C(++)? Хотелось бы использовать его как java api. Часто он отлично работает с нативной библиотекой и т. д. Но было бы здорово использовать его без этих зависимостей от ядра java. - person Andy; 28.05.2017
comment
(1) C(++) является ведущим языком высокопроизводительных вычислений (и немного Fortran; но в новых проектах F обычно не используется). Этому есть много причин, но ручное управление памятью, вероятно, является одной из наиболее важных (2) SCIP с открытым исходным кодом, но не бесплатно! Я бы сказал, что это, может быть, даже лучше, чем CBC, но не для коммерческих целей. (3) Язык реализации и API — это две разные вещи. Все коммерческие решатели написаны на C(++)(может быть, и на F), но есть интерфейсы, может быть, для 10 языков, в т.ч. Java, Python... Вероятно, для одного из этих решателей с открытым исходным кодом существуют API-интерфейсы на базе Java. - person sascha; 28.05.2017
comment
Есть ли у CBC такой API для Java? Это сайт да? projects.coin-or.org/Cbc Спасибо за все материалы :-) - person Andy; 28.05.2017
comment
Попробуйте немного погуглить. Я не уверен, так как я не крупный разработчик Java. Но эти ссылки могут быть start (если ortools все еще предлагает это). Как я уже сказал: CBC является мощным, и есть несколько универсальных оболочек, но с точки зрения документации и вспомогательных библиотек, например, glpk гораздо интереснее. - person sascha; 28.05.2017

Вы неправильно настроили NonNegativeConstraint, вы должны передать «true» его конструктору, если хотите, чтобы x, y были положительными

person Alexei Kovalev    schedule 28.05.2017