idol

Idol: un marco C ++ para la optimización

Idol es una biblioteca C ++ para la optimización matemática y la compleja toma de decisiones.

Está diseñado para ayudarlo a construir nuevos algoritmos fácilmente para resolver problemas más y más desafiantes. Es una herramienta versátil y potente que se puede utilizar para resolver una amplia gama de problemas de optimización, incluida la programación lineal de introducción mixta (MILP), problemas cuadráticamente limitados (MIQCQP y MIQP), problemas de nivel bille (BO), problemas de optimización robustos (RO y ARO) y muchos más.

• Documentación
• ¿Usar ídolo para la investigación?
• Ejemplos
  • Rama y precio
  • Problema bilevel (usando monedas o mibs)
• Características implementadas
  • Ram para
  • Generación de columnas y ramificación y precio
  • Solucionadores externos

Documentación

Visite nuestra documentación en línea.

¿Usar ídolo para la investigación?

Si está optando por Idol en uno de sus proyectos de investigación y se encuentra con algunos problemas, contáctenos en Lefebvre (AT) Uni-Trier.de.

Ejemplos

Rama y precio

Mire lo fácil que es implementar un algoritmo de rama y precio utilizando Idol.

 const auto [model, decomposition] = create_model(); // Creates the model with an annotation for automatic decomposition

const auto sub_problem_specifications = 
        DantzigWolfe::SubProblem ()
          .add_optimizer(Gurobi()); // Each sub-problem will be solved by Gurobi

const auto column_generation = 
        DantzigWolfeDecomposition (decomposition)
          .with_master_optimizer(Gurobi::ContinuousRelaxation()) // The master problem will be solved by Gurobi
          .with_default_sub_problem_spec(sub_problem_specifications);

const auto branch_and_bound =
        BranchAndBound ()
          .with_node_selection_rule(BestBound()) // Nodes will be selected by the "best-bound" rule
          .with_branching_rule(MostInfeasible()) // Variables will be selected by the "most-fractional" rule
          .with_log_level(Info, Blue);

const auto branch_and_price = branch_and_bound + column_generation; // Embed the column generation in the Branch-and-Bound algorithm

model.use(branch_and_price);

model.optimize();

Problema bilevel (usando mibs)

Aquí, Idol usa el solucionador externo Coin-OR/MIBS para resolver un problema de optimización de nivel bilevel con un nivel inferior entero.

 /*
 This example is taken from "The Mixed Integer Linear Bilevel Programming Problem" (Moore and Bard, 1990).

    min -1 x + -10 y
    s.t.

    y in argmin { y :
        -25 x + 20 y <= 30,
        1 x + 2 y <= 10,
        2 x + -1 y <= 15,
        2 x + 10 y >= 15,
        y >= 0 and integer.
    }
    x >= 0 and integer.

 */

Env env;

// Define High Point Relaxation
Model high_point_relaxation (env);

auto x = high_point_relaxation.add_var( 0 , Inf, Integer, " x " );
auto y = high_point_relaxation.add_var( 0 , Inf, Integer, " y " );

high_point_relaxation.set_obj_expr(-x - 10 * y);
auto follower_c1 = high_point_relaxation.add_ctr(- 25 * x + 20 * y <= 30 );
auto follower_c2 = high_point_relaxation.add_ctr(x + 2 * y <= 10 );
auto follower_c3 = high_point_relaxation.add_ctr( 2 * x - y <= 15 );
auto follower_c4 = high_point_relaxation.add_ctr( 2 * x + 10 * y >= 15 );

// Prepare bilevel description
Bilevel::LowerLevelDescription description (env);
description.set_follower_obj_expr(y);
description.set_follower_var(y);
description.set_follower_ctr(follower_c1);
description.set_follower_ctr(follower_c2);
description.set_follower_ctr(follower_c3);
description.set_follower_ctr(follower_c4);

// Use coin-or/MibS as external solver
high_point_relaxation.use(Bilevel::MibS(description));

// Optimize and print solution
high_point_relaxation.optimize();

std::cout << high_point_relaxation.get_status() << std::endl;
std::cout << high_point_relaxation.get_reason() << std::endl;
std::cout << save_primal(high_point_relaxation) << std::endl;

Idol también se puede interactuar con la raíz para monitorear el progreso de su algoritmo. Por ejemplo, aquí hay una captura de pantalla del monitoreo de MIB para una instancia bilevel.

Características implementadas

Optimización de enteros mixtos

Solucionadores externos

Idol se puede utilizar como una interfaz unificada para varios solucionadores comerciales o de código abierto como

• Gurobi
• Mosek
• GLPK
• Máximo
• Coin-OR/OSI-> CPlex, Symphony, CBC

Ram para

• Reglas de selección de nodos: Mejor límite, peor límite, profundidad primero, mejor estimación, amplitud primero.
• Reglas de ramificación (para ramificación variable): pseudo costo, ramificación fuerte (con fases), la más aceptable, menos inviable, primero encontrada, uniformemente aleatoria.
• Exploración subárbol
• Heurística (para ramificación variable): redondeo simple, vecindario forzado relajado, ramificación local
• Devoluciones de llamada: cortes de usuario, cortes perezosos

Generación de columnas y ramificación y precio

• Reformulación automática de Dantzig-Wolfe
• Ramificación suave y dura disponible (es decir, ramificarse en maestro o subproblema)
• Estabilización por suavizado de doble precio: Wentges (1997), Neame (2000)
• Puede resolver subproblemas en paralelo
• Apoya la heurística de precios
• Heurística: Integer Master

Optimización bilevel

• Idol puede resolver problemas optimistas de vibración de entorno mixto utilizando el solucionador externo Coin-OR/MIBS.

Optimización robusta de dos etapas

Generación de columna y restricción (CCG)

• Implementación genérica del algoritmo CCG para problemas de optimización sólidos ajustables.
• Estabilización de la región de confianza para problemas con las decisiones binarias de la primera etapa.
• Problema de separación (Max-Min) resuelto por un solucionador de bille.

Punto de referencia

• Un punto de referencia para la implementación de sucursal y precio está disponible para el problema de asignación generalizada.
• Un punto de referencia para la implementación de ramificación y encuadernación está disponible para el problema de la mochila.

Este es un perfil de rendimiento calculado según Dolan, E., Moré, J. Software de optimización de benchmarking con perfiles de rendimiento. Matemáticas. Programa. 91, 201–213 (2002) https://doi.org/10.1007/S101070100263.

Misceláneas

Versionning cumple con Semantic Versionning 2.0.0.