3 présentations

• 
  10h30 - 10h55

  A Branch-and-Cut Algorithm for the Quadratic Knapsack Problem

  • M. Eliass Fennich, prés., Université Laval
  • van Hoeve Willem-Jan, Carnegie Mellon University
  • Leandro C. Coelho, Université Laval
  • Djeumou Fomeni Franklin, Lancaster University

  The Quadratic Knapsack Problem (QKP) is a fundamental combinatorial optimization problem that arises in various applications, including portfolio optimization and resource allocation. It extends the classical knapsack problem by incorporating quadratic interactions between selected items, significantly increasing its complexity. The nonlinearity of the objective function weakens standard linear relaxation techniques, making it more difficult to obtain strong bounds and efficiently solve the problem. Consequently, developing exact algorithms that effectively address the quadratic nature of the problem is essential.

  In this work, we propose a branch-and-cut algorithm that strengthens the formulation of the QKP by introducing lifted cover inequalities over quadratic variables. While lifted cover inequalities have been widely employed in knapsack-type problems to enhance the quality of linear relaxations, their extension to quadratic variables remains largely unexplored. To address this gap, we leverage Binary Decision Diagrams (BDDs) in combination with a Dynamic Programming (DP) formulation to construct a compact representation of the solution space. This hybrid approach allows us to derive strong, valid inequalities that significantly improve the problem’s linear relaxation.

  Our methodology relies on a DP formulation tailored to the quadratic variables of the QKP. By exploiting the flexibility of the BDD representation, we develop a computational framework for generating valid cover inequalities specifically for these variables. Furthermore, by embedding the cover inequalities within a BDD structure, we systematically lift them, thereby strengthening their effectiveness in the branch-and-cut framework. This process enables a more refined tightening of the relaxation, reducing the solution space without compromising feasibility.

  To assess the relevance of our proposed inequalities, we conduct extensive computational experiments on benchmark instances of the QKP. The results demonstrate that integrating an approximation to the lifted cover inequalities over quadratic variables into a branch-and-cut algorithm significantly enhances computational efficiency. Compared to the traditional branch-and-bound method, which remains the only dominant exact solution approach for the QKP, our method achieves a substantial reduction in the number of explored nodes, leading to faster convergence to optimal solutions.

  The contributions of this work offer new insights into the design of cutting-plane algorithms for nonlinear combinatorial optimization. By integrating lifted cover inequalities over the nonlinear variables into a branch-and-cut framework, we present an innovative approach that improves exact solution techniques for the QKP. Furthermore, this research highlights the potential of BDDs as a powerful tool for generating strong cutting planes, paving the way for future advancements in quadratic programming and combinatorial optimization.

• 
  10h55 - 11h20

  Searching for optimal Lagrange multipliers that enhance the filtering of the multidimensional knapsack constraint.

  • Frédéric Berthiaume, prés., Université Laval
  • Claude-Guy Quimper, Université Laval

  The multidimensional knapsack constraint consists of finding subsets among n items that both respect linear resource consumption constraints and provide a profit within a specific range. We can overestimate the maximal profit by doing a Lagrangian relaxation of the resources consumption constraint. While doing a subgradient method to find the best estimation possible, reduced cost filtering can be used to find which object can or cannot be part of any solutions. In addition to the classical reduced cost filtering combined with subgradient method, we search Lagrange multipliers that may overestimate the maximal profit but provide previously missed filtering. We also add a procedure to know which items are to be tested in this alterations phase. Experimental results show a significant speed up on solved instances and better solutions on instances that reached the 300-second timeout.

• 
  11h20 - 11h45

  Three-dimensional packing problems with physical packing sequence constraints

  • Davide Croci, prés., Politecnico di Milano
  • Ola Jabali, École Polytechnique de Montréal
  • Joe Naoum-Sawaya, Ivey Business School

  We study the family of Three-Dimensional Packing Problems with Physical Packing Sequence Constraints (3D4PS), where a set of cuboid-shaped items must be packed into one or more bins while ensuring the existence of a feasible sequence of operations for their physical loading. The sequence must ensure that each item is loaded without colliding with any previously placed items, accounting for the physical limitations of the packing device. The typical algorithms from the literature solve the 3D4PS by first computing a three-dimensional packing of items in bins and subsequently attempting to find a feasible loading sequence for each packed bin. In this work, we demonstrate that state-of-the-art three-dimensional packing algorithms often fail to produce bins for which a feasible loading sequence is found a posteriori.
  To address this limitation, we propose two heuristic strategies that jointly optimize packing and sequencing in order to generate bins for which a feasible loading sequence always exists. We provide extensive benchmarks on instances from the literature showing that the proposed strategies achieve superior performance in solving the 3D4PS.