logic-based benders decomposition

Computational evaluation of cut-strengthening techniques in logic-based Benders’ decomposition

  • Aigerim Saken
  • Emil Karlsson
  • Stephen J. Maher
  • Elina Rönnberg
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Scheduling Tags , , , , ,

    Cut-strengthening techniques have a significant impact on the computational effectiveness of the Logic-based Benders’ decomposition (LBBD) scheme. While there have been numerous cut-strengthening techniques proposed, very little is understood about which techniques achieve the best computational performance for the LBBD scheme. This is typically due to implementations of LBBD being problem specific and thus, no … Read more

    A Double-oracle, Logic-based Benders decomposition approach to solve the K-adaptability problem

  • Alireza Ghahtarani
  • Ahmed Saif
  • Alireza Ghasemi
  • Erick Delage
    • Categories Combinatorial Optimization, Robust Optimization Tags , , , ,

    We propose a novel approach to solve K-adaptability problems with convex objective and constraints and integer first-stage decisions. A logic-based Benders decomposition is applied to handle the first-stage decisions in a master problem, thus the sub-problem becomes a min-max-min robust combinatorial optimization problem that is solved via a double-oracle algorithm that iteratively generates adverse scenarios … Read more

    Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling

  • Emil Karlsson
  • Elina Rönnberg
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    Pre-runtime scheduling of large-scale electronic systems, as those in modern aircraft, can be computationally challenging. In this paper, we study a distributed integrated modular avionic system of practical relevance where the scheduling includes to assign communication messages to time slots and to sequence tasks on modules. For this problem, the challenge is the huge number … Read more

    Network Migration Problem: A Logic-based Benders Decomposition Driven by Column Generation and Constraint Programming

  • Maryam Daryalal
  • Hamed Pouya
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    Telecommunication networks frequently face technological advancements and need to upgrade their infrastructure. Adapting legacy networks to the latest technology requires synchronized technicians responsible for migrating the equipment. The goal of the network migration problem is to find an optimal plan for this process. This is a defining step in the customer acquisition of telecommunications service … Read more

    The multiphase course timetabling problem

  • Rasul Esmaeilbeigi
  • Vicky Mak-Hau
  • John Yearwood
  • Vivian Nguyen
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Integer Programming Tags , , ,

    This paper introduces the multiphase course timetabling problem and presents mathematical formulations and effective solution algorithms to solve it in a real case study. Consider a pool of lessons and a number of students who are required to take a subset of these lessons to graduate. Each lesson consists of a predetermined and consecutive sequence … Read more