Primeros pasos con las herramientas OR para .NET

En las siguientes secciones, aprenderás a usar las herramientas OR para .NET:

• ¿Qué es un problema de optimización?
• Solución de un problema de optimización en .NET
• Más ejemplos de .NET
• 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 .NET

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

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 .NET

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

Nota: El programa.NET 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.

  using System;
  using Google.OrTools.Init;
  using Google.OrTools.LinearSolver;

• Declara el solucionador.

  // Create the linear solver with the GLOP backend.
  Solver solver = Solver.CreateSolver("GLOP");
  if (solver is null)
  {
      Console.WriteLine("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.
  Variable x = solver.MakeNumVar(0.0, 1.0, "x");
  Variable y = solver.MakeNumVar(0.0, 2.0, "y");
  
  Console.WriteLine("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.
  Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
  constraint.SetCoefficient(x, 1);
  constraint.SetCoefficient(y, 1);
  
  Console.WriteLine("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.
  Objective objective = solver.Objective();
  objective.SetCoefficient(x, 3);
  objective.SetCoefficient(y, 1);
  objective.SetMaximization();

  El método setMaximization declara que es un problema de maximización. (El método de C++ subyacente es SetMaximization.
• Invoca el solucionador y muestra los resultados.

  Console.WriteLine("Solving with " + solver.SolverVersion());
  Solver.ResultStatus resultStatus = solver.Solve();
  Console.WriteLine("Status: " + resultStatus);
  if (resultStatus != Solver.ResultStatus.OPTIMAL)
  {
      Console.WriteLine("The problem does not have an optimal solution!");
      if (resultStatus == Solver.ResultStatus.FEASIBLE)
      {
          Console.WriteLine("A potentially suboptimal solution was found");
      }
      else
      {
          Console.WriteLine("The solver could not solve the problem.");
          return;
      }
  }
  
  Console.WriteLine("Solution:");
  Console.WriteLine("Objective value = " + solver.Objective().Value());
  Console.WriteLine("x = " + x.SolutionValue());
  Console.WriteLine("y = " + y.SolutionValue());

Completar programa

A continuación, se muestra el programa completo.

using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        Console.WriteLine("Google.OrTools version: " + OrToolsVersion.VersionString());

        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            Console.WriteLine("Could not create solver GLOP");
            return;
        }

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

        Console.WriteLine("Number of variables = " + solver.NumVariables());

        // Create a linear constraint, x + y <= 2.
        Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
        constraint.SetCoefficient(x, 1);
        constraint.SetCoefficient(y, 1);

        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

        // Create the objective function, 3 * x + y.
        Objective objective = solver.Objective();
        objective.SetCoefficient(x, 3);
        objective.SetCoefficient(y, 1);
        objective.SetMaximization();

        Console.WriteLine("Solving with " + solver.SolverVersion());
        Solver.ResultStatus resultStatus = solver.Solve();

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

        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());

        Console.WriteLine("Advanced usage:");
        Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
        Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
    }
}

Ejecuta el programa .NET

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 BasicExample.cs. en el subdirectorio examples/dotnet del directorio en el que instalaste OR-Tools.
2. En el mismo directorio, crea un archivo nuevo, BasicExample.csproj, y agrega el siguiente código:

   <Project Sdk="Microsoft.NET.Sdk">
     <PropertyGroup>
       <OutputType>Exe</OutputType>
       <LangVersion>7.3</LangVersion>
       <TargetFramework>netcoreapp3.1</TargetFramework>
       <EnableDefaultItems>false</EnableDefaultItems>
       <!-- see https://github.com/dotnet/docs/issues/12237 -->
       <RollForward>LatestMajor</RollForward>
       <RestoreSources>../../../temp_dotnet/packages;$(RestoreSources);https://api.nuget.org/v3/index.json</RestoreSources>
       <AssemblyName>Google.OrTools.BasicExample</AssemblyName>
       <IsPackable>true</IsPackable>
     </PropertyGroup>
   
     <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
       <DebugType>full</DebugType>
       <Optimize>true</Optimize>
       <GenerateTailCalls>true</GenerateTailCalls>
     </PropertyGroup>
   
     <ItemGroup>
       <Compile Include="BasicExample.cs" />
       <PackageReference Include="Google.OrTools" Version="9.1.*" />
     </ItemGroup>
   </Project>
   

3. En el nivel superior del directorio en el que instalaste OR-Tools, abre una ventana de comandos y, luego, ingresa:

   make run SOURCE=examples/dotnet/BasicExample.cs

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

Es posible guardar y ejecutar programas .NET en un directorio diferente a examples/dotnet/, pero esto es un poco más complicado: debes modificar la siguiente línea del archivo csproj, que se muestra arriba:

../../../packages;$(RestoreSources);https://api.nuget.org/v3/index.json

para tener la ruta de acceso correcta al directorio packages.

La solución más sencilla es colocar tus programas .NET en el directorio examples/dotnet/.

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/SimpleProgram.cs

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

Más ejemplos de .NET

Para obtener más ejemplos de .NET que ilustran 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