Implementação de Ramificação Local

Question

Recentemente, li alguns artigos onde os autores usam ramificações locais especificamente na decomposição de Benders ( consulte para referência). Embora eu entenda até certo ponto como o algoritmo funciona, estou tendo dificuldade em entender como ele é implementado na prática.

Por exemplo, afirma-se que podemos dividir a região viável em duas partes usando $\Delta(x_o,x) \leq \kappa$ e $\Delta(x_o,x) \geq \kappa+1$ que são identificados como os ramos esquerdo e direito, respectivamente.

Gostaria de saber se alguém pode explicar brevemente como essa operação pode ser realizada a partir da perspectiva de codificação ao usar a API Java usando CPLEX.

Algumas referências acadêmicas são:

Rei, W., Cordeau, JF, Gendreau, M., & Soriano, P. (2009). Acelerando a decomposição de Benders por ramificação local . INFORMS Journal on Computing, 21 (2), 333-345.

Baena, D., Castro, J., & Frangioni, A. (2020). Métodos de benders estabilizados para otimização combinatória em grande escala, com aplicação para privacidade de dados . Ciência da Administração.

Answer 1

Você precisa usar um retorno de chamada e o CPLEX introduziu um novo sistema de retorno de chamada ("retornos de chamada genéricos") na versão 12.8 (eu acho), enquanto mantém o suporte, pelo menos por agora, para o sistema de retorno de chamada original ("retornos de chamada legados"). Os detalhes de fazer a ramificação dependem em parte de qual sistema você usa.

Com retornos de chamada legados, você cria uma classe que estende IloCplex.BranchCallback e a anexa ao seu modelo usando IloCplex.use (). Dentro do método main (), você usa uma das sobrecargas de makeBranch () para fazer cada ramificação. Para criar dois nós filho, você chama makeBranch () duas vezes.

Com callbacks genéricos, você cria uma classe que implementa a interface IloCplex.Callback.Function e a anexa ao seu modelo usando uma sobrecarga diferente de IloCplex.use (). Nessa sobrecarga de use (), você deve especificar uma máscara para os contextos nos quais o retorno de chamada é invocado e, em particular, você precisará incluir o contexto de "ramificação" na máscara. A classe que implementa IloCplex.Callback.Function terá um método invoke (), que o CPLEX chamará, passando um argumento do tipo IloCplex.Callback.Context. Em sua implementação de invoke (), depois de verificar se necessário para ter certeza de que está no contexto de ramificação, você invoca o método makeBranch () do objeto de contexto uma vez para cada nó filho.

Em ambas as abordagens, a tentativa de criar mais de dois filhos em um nó causará o colapso do contínuo espaço-tempo.