Implementación de sucursales locales

Sep 28 2020

Recientemente he estado leyendo algunos artículos en los que los autores utilizan la ramificación local específicamente en Benders Decomposition ( ver como referencia). Aunque entiendo hasta cierto punto cómo funciona el algoritmo, me cuesta entender cómo se implementa en la práctica.

Por ejemplo, se afirma que podemos dividir la región factible en dos partes usando $\Delta(x_o,x) \leq \kappa$ y $\Delta(x_o,x) \geq \kappa+1$ que se identifican como las ramas izquierda y derecha, respectivamente.

Me preguntaba si alguien puede explicar brevemente cómo se puede realizar esta operación desde la perspectiva de la codificación cuando se usa en la API de Java CPLEX.

Algunas referencias académicas son:

Rei, W., Cordeau, JF, Gendreau, M. y Soriano, P. (2009). Aceleración de la descomposición de Benders por ramificación local . INFORMA Revista de Computación, 21 (2), 333-345.

Baena, D., Castro, J. y Frangioni, A. (2020). Métodos de dobladores estabilizados para la optimización combinatoria a gran escala, con aplicación a la privacidad de los datos . Ciencias de la gestión.

Respuestas

4 prubin Sep 29 2020 at 01:30

Necesita usar una devolución de llamada, y CPLEX introdujo un nuevo sistema de devolución de llamada ("devoluciones de llamada genéricas") en la versión 12.8 (creo) mientras mantiene el soporte, al menos por ahora, para el sistema de devolución de llamada original ("devoluciones de llamada heredadas"). Los detalles de la ramificación dependen en parte del sistema que utilice.

Con las devoluciones de llamada heredadas, crea una clase que extiende IloCplex.BranchCallback y la adjunta a su modelo usando IloCplex.use (). Dentro del método main (), usas una de las sobrecargas de makeBranch () para hacer cada rama. Para crear dos nodos secundarios, llame a makeBranch () dos veces.

Con las devoluciones de llamada genéricas, crea una clase que implementa la interfaz IloCplex.Callback.Function y la adjunta a su modelo usando una sobrecarga diferente de IloCplex.use (). En esta sobrecarga de use (), debe especificar una máscara para los contextos en los que se invoca la devolución de llamada y, en particular, deberá incluir el contexto de "ramificación" en la máscara. La clase que implementa IloCplex.Callback.Function tendrá un método invoke (), al que llamará CPLEX, pasando un argumento de tipo IloCplex.Callback.Context. Dentro de su implementación de invoke (), después de verificar si es necesario para asegurarse de que está en el contexto de ramificación, invoca el método makeBranch () del objeto de contexto una vez para cada nodo hijo.

En ambos enfoques, intentar crear más de dos hijos en un nodo hará que el continuo espacio-tiempo colapse sobre sí mismo.