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

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

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

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

Integer programming column generation: Accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems

Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch- and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with … Read more