Начало работы с OR-Tools для Java

Следующие разделы помогут вам начать работу с OR-Tools для Java:

• Что такое проблема оптимизации?
• Решение задачи оптимизации в Java
• Больше примеров Java
• Определение типа проблемы, которую вы хотите решить

Что такое проблема оптимизации?

Цель оптимизации — найти лучшее решение проблемы из большого множества возможных решений. (Иногда вам будет достаточно найти любое осуществимое решение; OR-Tools тоже может это сделать.)

Вот типичная задача оптимизации. Предположим, что транспортная компания доставляет посылки своим клиентам с помощью парка грузовиков. Каждый день компания должна распределять посылки по грузовикам, а затем выбирать маршрут для каждого грузовика для доставки своих посылок. Стоимость каждого возможного назначения пакетов и маршрутов зависит от общего расстояния поездки грузовиков и, возможно, от других факторов. Проблема состоит в том, чтобы выбрать назначения пакетов и маршрутов с наименьшей стоимостью.

Как и все задачи оптимизации, эта задача имеет следующие элементы:

• Цель — количество, которое вы хотите оптимизировать. В приведенном выше примере целью является минимизация затрат. Чтобы поставить задачу оптимизации, вам необходимо определить функцию, которая вычисляет значение цели для любого возможного решения. Это называется целевой функцией . В предыдущем примере целевая функция рассчитает общую стоимость любого назначения пакетов и маршрутов.

  Оптимальное решение — это решение, для которого значение целевой функции является наилучшим. («Лучшее» может быть либо максимальным, либо минимальным.)

• Ограничения — ограничения на множество возможных решений, основанные на конкретных требованиях задачи. Например, если транспортная компания не может назначить грузовым автомобилям посылки, вес которых превышает заданный, это наложит ограничения на решения.

  Допустимое решение — это решение, которое удовлетворяет всем заданным ограничениям задачи, но не обязательно является оптимальным.

Первым шагом в решении задачи оптимизации является определение цели и ограничений.

Решение задачи оптимизации в Java

Далее мы приведем пример задачи оптимизации и покажем, как ее настроить и решить на Java.

Пример линейной оптимизации

Одной из старейших и наиболее широко используемых областей оптимизации является линейная оптимизация (или линейное программирование ), в которой целевая функция и ограничения могут быть записаны в виде линейных выражений. Вот простой пример проблемы такого типа.

Максимизируйте 3x + y при следующих ограничениях:

1. 0 ≤ x ≤ 1
2. 0 ≤ y ≤ 2
3. x + y ≤ 2

Целевая функция в этом примере равна 3x + y . И целевая функция, и ограничения задаются линейными выражениями, что делает эту задачу линейной.

Основные шаги решения проблемы

Для каждого языка основные этапы постановки и решения задачи одинаковы:

1. Импортируйте необходимые библиотеки,
2. Объявите решатель,
3. Создайте переменные,
4. Определите ограничения,
5. Определить целевую функцию,
6. Вызовите решатель и
7. Отобразите результаты.

Java-программа<

В этом разделе рассматривается программа Java, которая устанавливает и решает проблему.

Примечание. Полная программа Java и шаги по ее запуску показаны в конце раздела.

Вот шаги:

• Импортируйте необходимые библиотеки.

  import com.google.ortools.Loader;
  import com.google.ortools.init.OrToolsVersion;
  import com.google.ortools.linearsolver.MPConstraint;
  import com.google.ortools.linearsolver.MPObjective;
  import com.google.ortools.linearsolver.MPSolver;
  import com.google.ortools.linearsolver.MPVariable;

• Объявите решатель.

  // Create the linear solver with the GLOP backend.
  MPSolver solver = MPSolver.createSolver("GLOP");
  if (solver == null) {
    System.out.println("Could not create solver GLOP");
    return;
  }

  MPSolver — это оболочка для решения любых задач линейного или смешанного целочисленного программирования .
• Создайте переменные.

  // Create the variables x and y.
  MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
  MPVariable y = solver.makeNumVar(0.0, 2.0, "y");
  
  System.out.println("Number of variables = " + solver.numVariables());

• Определите ограничения. Первые два ограничения, 0 ≤ x ≤ 1 и 0 ≤ y ≤ 2 , уже установлены определениями переменных. Следующий код определяет ограничение x + y ≤ 2 :

  double infinity = Double.POSITIVE_INFINITY;
  // Create a linear constraint, x + y <= 2.
  MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
  ct.setCoefficient(x, 1);
  ct.setCoefficient(y, 1);
  
  System.out.println("Number of constraints = " + solver.numConstraints());

  Метод setCoefficient устанавливает коэффициенты x и y в выражении ограничения.
• Определите целевую функцию.

  // Create the objective function, 3 * x + y.
  MPObjective objective = solver.objective();
  objective.setCoefficient(x, 3);
  objective.setCoefficient(y, 1);
  objective.setMaximization();

  Метод setMaximization объявляет это проблемой максимизации.
• Вызовите решатель и отобразите результаты.

  System.out.println("Solving with " + solver.solverVersion());
  final MPSolver.ResultStatus resultStatus = solver.solve();
  System.out.println("Status: " + resultStatus);
  if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
    System.out.println("The problem does not have an optimal solution!");
    if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
      System.out.println("A potentially suboptimal solution was found");
    } else {
      System.out.println("The solver could not solve the problem.");
      return;
    }
  }
  
  System.out.println("Solution:");
  System.out.println("Objective value = " + objective.value());
  System.out.println("x = " + x.solutionValue());
  System.out.println("y = " + y.solutionValue());

Полная программа

Полная программа представлена ​​ниже.

package com.google.ortools.linearsolver.samples;

import com.google.ortools.Loader;
import com.google.ortools.init.OrToolsVersion;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();

    System.out.println("Google OR-Tools version: " + OrToolsVersion.getVersionString());

    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");
    if (solver == null) {
      System.out.println("Could not create solver GLOP");
      return;
    }

    // Create the variables x and y.
    MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
    MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    double infinity = Double.POSITIVE_INFINITY;
    // Create a linear constraint, x + y <= 2.
    MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    System.out.println("Solving with " + solver.solverVersion());
    final MPSolver.ResultStatus resultStatus = solver.solve();

    System.out.println("Status: " + resultStatus);
    if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("The problem does not have an optimal solution!");
      if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
        System.out.println("A potentially suboptimal solution was found");
      } else {
        System.out.println("The solver could not solve the problem.");
        return;
      }
    }

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());

    System.out.println("Advanced usage:");
    System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
    System.out.println("Problem solved in " + solver.iterations() + " iterations");
  }

  private BasicExample() {}
}

Запуск программы Java

Вы можете запустить приведенную выше программу следующим образом:

1. Скопируйте и вставьте приведенный выше код в новый файл и сохраните его как my_program.java .
2. Откройте командное окно на верхнем уровне каталога, в который вы установили OR-Tools, и введите:

   make run SOURCE=relative/path/to/my_program.java

   где relative/path/to/ — путь к каталогу, в котором вы сохранили программу.

Примечание. Вы должны запустить указанную выше команду с верхнего уровня каталога, в котором вы установили OR-Tools (где находится Makefile ).

Программа возвращает значения x и y , которые максимизируют целевую функцию:

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/my_program.java

Больше примеров Java

Дополнительные примеры Java, иллюстрирующие решение различных типов задач оптимизации, см. в разделе «Примеры» .

Определение типа проблемы, которую вы хотите решить

В мире существует множество различных типов задач оптимизации. Для каждого типа задач существуют разные подходы и алгоритмы поиска оптимального решения.

Прежде чем вы сможете начать писать программу для решения задачи оптимизации, вам необходимо определить, с каким типом проблемы вы имеете дело, а затем выбрать подходящий решатель — алгоритм поиска оптимального решения.

Ниже вы найдете краткий обзор типов проблем, которые решает OR-Tools, а также ссылки на разделы этого руководства, в которых объясняется, как решить каждый тип проблем.

• Линейная оптимизация
• Оптимизация ограничений
• Смешанно-целочисленная оптимизация
• Назначение
• Планирование
• Упаковка
• Маршрутизация
• Сетевые потоки

Линейная оптимизация

Как вы узнали из предыдущего раздела , задача линейной оптимизации — это задача, в которой целевая функция и ограничения представляют собой линейные выражения в переменных.

Основным решателем в OR-Tools для задач такого типа является решатель линейной оптимизации, который на самом деле является оболочкой для нескольких различных библиотек для линейной и смешанно-целочисленной оптимизации , включая сторонние библиотеки.

Узнайте больше о линейной оптимизации

Смешанно-целочисленная оптимизация

Задача смешанной целочисленной оптимизации — это задача, в которой некоторые или все переменные должны быть целыми числами. Примером может служить задача назначения , в которой группе работников необходимо назначить набор задач. Для каждого работника и задачи вы определяете переменную, значение которой равно 1, если данный работник назначен данной задаче, и 0 в противном случае. В этом случае переменные могут принимать только значения 0 или 1.

Узнайте больше о смешанно-целочисленной оптимизации.

Оптимизация ограничений

Оптимизация с ограничениями, или программирование с ограничениями (CP), определяет возможные решения из очень большого набора кандидатов, где проблему можно смоделировать с точки зрения произвольных ограничений. CP основан на осуществимости (поиске возможного решения), а не на оптимизации (поиске оптимального решения), и фокусируется на ограничениях и переменных, а не на целевой функции. Однако CP можно использовать для решения задач оптимизации, просто сравнивая значения целевой функции для всех возможных решений.

Узнайте больше об оптимизации ограничений

Назначение

Проблемы назначения включают назначение группы агентов (скажем, рабочих или машин) для выполнения набора задач, при этом существует фиксированная стоимость назначения каждого агента для выполнения конкретной задачи. Задача состоит в том, чтобы найти задание с наименьшей общей стоимостью. Проблемы назначения на самом деле являются частным случаем проблем сетевых потоков .

Узнать больше о задании

Упаковка

Бин-упаковка — это задача упаковки набора предметов разного размера в контейнеры разной вместимости. Цель — упаковать как можно больше объектов с учетом вместимости контейнеров. Особым случаем является задача о рюкзаке , в которой контейнер всего один.

Узнайте больше об упаковке в мусорные контейнеры

Планирование

Проблемы планирования включают в себя назначение ресурсов для выполнения набора задач в определенное время. Важным примером является задача цеха , в которой несколько заданий выполняются на нескольких машинах. Каждое задание состоит из последовательности задач, которые необходимо выполнять в заданном порядке, и каждая задача должна обрабатываться на определенной машине. Проблема состоит в том, чтобы составить график так, чтобы все задания выполнялись за как можно более короткий интервал времени.

Узнайте больше о планировании

Маршрутизация

Задачи маршрутизации включают в себя поиск оптимальных маршрутов для парка транспортных средств, пересекающих сеть, определяемую ориентированным графом. Проблема назначения посылок грузовикам доставки, описанная в разделе «Что такое задача оптимизации?» , является одним из примеров проблемы маршрутизации. Другая проблема – это задача коммивояжера .

Узнать больше о маршрутизации

Сетевые потоки

Многие задачи оптимизации можно представить в виде ориентированного графа, состоящего из узлов и направленных дуг между ними. Например, транспортные задачи, в которых товары доставляются по железнодорожной сети, можно представить в виде графа, дугами которого являются железнодорожные линии, а узлами — распределительные центры.

В задаче о максимальном потоке каждая дуга имеет максимальную пропускную способность, которую можно через нее перенести. Проблема состоит в том, чтобы распределить количество товаров, подлежащих отправке по каждой дуге, так, чтобы общее транспортируемое количество было как можно большим.

Узнайте больше о сетевых потоках