Cómo comenzar a usar las herramientas OR para C++

En las siguientes secciones, podrás comenzar a usar las herramientas OR con C++:

• ¿Qué es un problema de optimización?
• Solución de un problema de optimización en C++
• Más ejemplos de C++
• Identifica el tipo de problema que quieres resolver

¿Qué es un problema de optimización?

El objetivo de la optimización es encontrar la mejor solución para un problema de un amplio conjunto de soluciones posibles. (A veces, estarás satisfecho con encontrar una solución factible; las herramientas OR también pueden hacerlo).

Este es un problema de optimización típico. Supongamos que una empresa de transporte entrega paquetes a sus clientes mediante una flota de camiones. Todos los días, la empresa debe asignar paquetes a los camiones y, luego, elegir una ruta para que cada camión entregue los paquetes. Cada asignación posible de paquetes y rutas tiene un costo, según la distancia total de viaje de los camiones y posiblemente otros factores. El problema es elegir las asignaciones de paquetes y rutas que tienen el menor costo.

Como todos los problemas de optimización, este tiene los siguientes elementos:

• El objetivo: la cantidad que deseas optimizar. En el ejemplo anterior, el objetivo es minimizar el costo. Para configurar un problema de optimización, debes definir una función que calcule el valor del objetivo para cualquier solución posible. Esto se denomina función objetivo. En el ejemplo anterior, la función objetiva calcularía el costo total de cualquier asignación de paquetes y rutas.

  Una solución óptima es aquella para la que el valor de la función objetiva es el mejor. ("Muy bueno" puede ser un máximo o un mínimo).

• Las restricciones: restricciones sobre el conjunto de soluciones posibles, según los requisitos específicos del problema. Por ejemplo, si la empresa de transporte no puede asignar paquetes superiores a un peso determinado a los camiones, esto impone una restricción para las soluciones.

  Una solución posible es aquella que cumple con todas las restricciones determinadas para el problema, sin ser óptima.

El primer paso para resolver un problema de optimización es identificar el objetivo y las restricciones.

Resolver un problema de optimización en C++

A continuación, se brinda un ejemplo de un problema de optimización y se muestra cómo configurarlo y resolverlo en C++.

Un ejemplo de optimización lineal

Una de las áreas de optimización más antiguas y más usadas es la optimización lineal (o la programación lineal), en la que la función objetiva y las restricciones se pueden escribir como expresiones lineales. Aquí hay un ejemplo simple de este tipo de problema.

Maximiza 3x + y sujeto a las siguientes restricciones:

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

La función objetiva de este ejemplo es 3x + y. Tanto la función objetiva como las restricciones se proporcionan mediante expresiones lineales, lo que hace que este sea un problema lineal.

Pasos principales para resolver el problema

En cada idioma, los pasos básicos para configurar y resolver un problema son los mismos:

1. Importa las bibliotecas requeridas,
2. Declara el solucionador
3. Crea las variables,
4. Definir las restricciones,
5. Define la función objetiva,
6. Invoca el solucionador y
7. Muestra los resultados.

Programa C++

En esta sección, se explica un programa de C++ que configura y resuelve el problema.

Nota: El programa C++ completo y los pasos para ejecutarlo se muestran al final de la sección.

A continuación, se indican los pasos que debes seguir:

• Importa las bibliotecas requeridas.

  #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"

• Declara el solucionador.

  // 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 es un wrapper para resolver cualquier problema de programación lineal o programación de números enteros mixtos.
• Crea las variables.

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

• Define las restricciones. Las primeras dos restricciones, 0 ≤ x ≤ 1 y 0 ≤ y ≤ 2, ya están establecidas por las definiciones de las variables. En el siguiente código, se define la restricción 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();

  El método SetCoefficient establece los coeficientes de x y y en la expresión de la restricción.
• Define la función objetiva.

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

  El método SetMaximization declara que se trata de un problema de maximización.
• Invoca el solucionador y muestra los resultados.

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

Completar programa

A continuación, se muestra el programa completo.

// 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ómo ejecutar el programa de C++

Puedes ejecutar el programa anterior de la siguiente manera:

1. Copia y pega el código anterior en el archivo nuevo y guárdalo como program.cc.
2. Abre una ventana de comandos en el nivel superior del directorio en el que instalaste OR-Tools y, luego, ingresa lo siguiente:

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

   , donde relative/path/to/ es la ruta de acceso al directorio donde guardaste el programa.

Nota: Debes ejecutar el comando anterior desde el nivel superior del directorio en el que instalaste OR-Tools.

El programa muestra los valores de x y y que maximizan la función objetivo:

Solution:
x =  1.0
y =  1.0

Para compilar el programa sin ejecutarlo, ingresa lo siguiente:

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

Cómo compilar en el modo de optimización

Para compilar en modo O3:

make DEBUG='-O3' all

Cómo ejecutar el ejecutable de C++

Cuando compilas un programa OR-Tools de C++ con make, el archivo ejecutable se crea en el directorio bin. Puedes ejecutar el archivo ejecutable para el programa de ejemplo de la siguiente manera:

cd bin && ./program

Si realizas cambios en el programa, tendrás que volver a compilarlo como se muestra más arriba.

Más ejemplos de C++

Para ver más ejemplos de C++ que muestran cómo resolver varios tipos de problemas de optimización, consulta Ejemplos.

Identificar el tipo de problema que deseas resolver

En el mundo, existen muchos tipos diferentes de problemas de optimización. Para cada tipo de problema, existen diferentes enfoques y algoritmos para encontrar una solución óptima.

Antes de comenzar a escribir un programa para resolver un problema de optimización, debes identificar con qué tipo de problema se trata y, luego, elegir un solucionador adecuado: un algoritmo para encontrar una solución óptima.

A continuación, encontrarás una breve descripción general de los tipos de problemas que resuelven las herramientas del operador OR y vínculos a las secciones de esta guía que explican cómo resolver cada tipo de problema.

• Optimización lineal
• Optimización de restricciones
• Optimización de números enteros mixtos
• Tarea
• Programación
• Empaquetado
• Enrutamiento
• Flujos de red

Optimización lineal

Como aprendiste en la sección anterior, un problema de optimización lineal es uno en el que la función objetivo y las restricciones son expresiones lineales en las variables.

El solucionador principal de las herramientas OR para este tipo de problema es el solucionador de optimización lineal, que en realidad es un wrapper para varias bibliotecas diferentes destinadas a la optimización de números enteros mixtos y a las bibliotecas de terceros.

Más información sobre la optimización lineal

Optimización de números enteros mixtos

Un problema de optimización de números enteros mixtos es aquel en el que se requiere que algunas o todas las variables sean números enteros. Un ejemplo es el problema de asignación, en el que se necesita asignar un grupo de trabajadores a un conjunto de tareas. Para cada trabajador y tarea, se define una variable cuyo valor es 1 si ese trabajador está asignado a la tarea en cuestión y 0 en el caso contrario. En este caso, las variables solo pueden tomar los valores 0 o 1.

Más información sobre la optimización de números enteros mixtos

Optimización de restricciones

La optimización de restricciones, o programación de restricciones (CP), identifica soluciones posibles a partir de un gran conjunto de candidatos, en las que el problema se puede modelar en términos de restricciones arbitrarias. La CP se basa en la viabilidad (encontrar una solución factible) en lugar de en la optimización (encontrar una solución óptima) y se centra en las restricciones y las variables, en lugar de la función objetiva. Sin embargo, la CP se puede usar para resolver problemas de optimización con solo comparar los valores de la función objetiva para todas las soluciones posibles.

Más información sobre la optimización de restricciones

Assignment

Los problemas de asignación implican la asignación de un grupo de agentes (por ejemplo, trabajadores o máquinas) a un conjunto de tareas, en el que hay un costo fijo para asignar cada agente a una tarea específica. El problema es encontrar la tarea con el menor costo total. Los problemas de asignación son, en realidad, un caso especial de problemas de flujo de red.

Más información sobre las asignaciones

Empaquetado

El empaquetado de contenedores se refiere al problema de empaquetar un conjunto de objetos de diferentes tamaños en contenedores con distintas capacidades. El objetivo es empaquetar la mayor cantidad posible de objetos, sujeto a la capacidad de los contenedores. Un caso especial de esto es el problema de Knapsack, en el que solo hay un contenedor.

Más información sobre el empaquetado en contenedores

Programación

Los problemas de programación implican la asignación de recursos para realizar un conjunto de tareas en momentos específicos. Un ejemplo importante es el problema de la tienda de trabajo, en el que varios trabajos se procesan en varias máquinas. Cada trabajo consiste en una secuencia de tareas que deben realizarse en un orden determinado y cada tarea debe procesarse en una máquina específica. El problema es asignar un programa para que todos los trabajos se completen en el menor intervalo de tiempo posible.

Más información sobre la programación

Enrutamiento

Los problemas de enrutamiento implican encontrar las rutas óptimas para que una flota de vehículos atraviese una red, definida por un grafo dirigido. El problema de asignar paquetes a camiones de reparto, que se describe en la sección ¿Qué es un problema de optimización?, es un ejemplo de un problema relacionado con el enrutamiento. Otro es el problema del vendedor que viaja.

Más información sobre el enrutamiento

Flujos de red

Muchos problemas de optimización se pueden representar con un grafo dirigido que consta de nodos y arcos dirigidos entre ellos. Por ejemplo, los problemas de transporte, en los que los productos se envían a través de una red ferroviaria, se pueden representar con un gráfico en el que los arcos son líneas ferroviarias y los nodos son centros de distribución.

En el problema de flujo máximo, cada arco tiene una capacidad máxima que se puede transportar por él. El problema es asignar la cantidad de bienes que se enviarán en cada arco para que la cantidad total que se transporte sea lo más grande posible.

Más información sobre los flujos de red