Начало работы с инструментами OR для C++

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

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

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

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

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

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

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

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

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

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

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

Решение задачи оптимизации на C++

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

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

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

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

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

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

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

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

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

программа на С++

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

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

Вот шаги:

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

  #include <cstdlib>
  #include <memory>
  
  #include "absl/flags/flag.h"
  #include "absl/log/flags.h"
  #include "ortools/base/init_google.h"
  #include "ortools/base/logging.h"
  #include "ortools/init/init.h"
  #include "ortools/linear_solver/linear_solver.h"

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

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

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

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");
  
  LOG(INFO) << "Number of variables = " << solver->NumVariables();

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

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);
  
  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

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

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

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

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();
  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }
  
  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

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

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

// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

Запуск программы на C++

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

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

   make run SOURCE=relative/path/to/program.cc

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

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

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

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/program.cc

Компиляция в режиме opt

Чтобы скомпилировать в режиме O3:

make DEBUG='-O3' all

Запуск исполняемого файла C++

Когда вы компилируете программу OR-Tools C++ с помощью make , исполняемый файл создается в каталоге bin . Вы можете запустить исполняемый файл примера программы следующим образом:

cd bin && ./program

Если вы внесете изменения в программу, вам придется перекомпилировать ее, как показано выше.

Дополнительные примеры C++

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Назначение

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

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

Упаковка

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

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

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

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

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

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

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

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

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

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

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

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