Primeros pasos con las herramientas OR para Java

En las siguientes secciones, podrás comenzar a usar las herramientas OR para Java:

¿Qué es un problema de optimización?

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

Este es un problema de optimización típico. Supongamos que una empresa de envíos 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 sus 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 establecer un problema de optimización, debes definir una función que calcule el valor del objetivo de cualquier solución posible. Esto se denomina función objetivo. En el ejemplo anterior, la función objetivo calcularía el costo total de cualquier asignación de paquetes y rutas.

    Una solución óptima es aquella para la que el mejor valor de la función objetivo 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 por encima de un peso determinado a los camiones, esto impone una restricción en las soluciones.

    Una solución posible es aquella que satisface todas las restricciones dadas del problema, sin ser necesariamente ó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 Java

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

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.

Maximizar 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 objetivo 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. Define las restricciones,
  5. Define la función objetivo,
  6. Invoca el solucionador y
  7. Muestra los resultados.

Programa Java<

En esta sección, se explica un programa de Java que prepara y resuelve el problema.

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

  • Importa las bibliotecas requeridas. 
    import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
  • Declara el solucionador. 
    // Create the linear solver with the GLOP backend.
MPSolver solver = MPSolver.createSolver("GLOP");
    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 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());
  • Define las restricciones. Las dos primeras restricciones, 0 &leq; x ≤ 1 y 0 &leq; 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, 0 <= x + y <= 2.
MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
ct.setCoefficient(x, 1);
ct.setCoefficient(y, 1);

System.out.println("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 objetivo. 
    // Create the objective function, 3 * x + y.
MPObjective 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.
  • Invoca el solucionador y muestra los resultados. 
    solver.solve();
System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());

Completar programa

A continuación, se muestra el programa completo.

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
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();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

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

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 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();

    solver.solve();

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

  private BasicExample() {}
}

Ejecuta el programa Java

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 my_program.java.
  2. Abre una ventana de comandos en el nivel superior del directorio donde instalaste OR-Tools y, luego, ingresa:
    make run SOURCE=relative/path/to/my_program.java
    , donde relative/path/to/ es la ruta de acceso al directorio donde guardaste el programa.

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/my_program.java

Más ejemplos de Java

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

Identificar el tipo de problema que deseas resolver

Existen muchos tipos diferentes de problemas de optimización en el mundo. 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, es decir, un algoritmo para encontrar una solución óptima.

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

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.

La herramienta de resolución principal en las herramientas OR para este tipo de problema es la herramienta de resolución 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 lineales, incluidas las bibliotecas de terceros.

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

Optimización de números enteros mixtos

En un problema de optimización de números enteros mixtos, se requiere que algunas o todas las variables sean números enteros. Un ejemplo es el problema de asignación, en el que se debe asignar un grupo de trabajadores a un conjunto de tareas. Para cada trabajador y tarea, se define una variable cuyo valor es 1 si el trabajador dado está asignado a la tarea determinada 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 los que el problema se puede modelar en términos de restricciones arbitrarias. La CP se basa en la viabilidad (en busca de una solución factible) en lugar de en la optimización (en la búsqueda de 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 incluyen 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 asignación 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 es el problema de empaquetar un conjunto de objetos de diferentes tamaños en contenedores con capacidades diferentes. 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 del taller de trabajo, en el que varios trabajos se procesan en varias máquinas. Cada trabajo consta de una secuencia de tareas, que se deben realizar en un orden determinado, y cada tarea debe procesarse en una máquina específica. El problema es asignar una programación 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 recorra una red, definida por un gráfico dirigido. El problema de asignar paquetes a camiones de reparto, que se describe en la sección ¿Cuál es un problema de optimización?, es un ejemplo de un problema de planificación de ruta. 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, pueden representarse 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 productos que se enviarán en cada arco, de modo que la cantidad total que se transporte sea lo más grande posible.

Más información sobre los flujos de red