Lexicographic optimization for the multi-container loading problem with open dimensions for a shoe manufacturer

Manuel V. C. Vieira, Margarida Carvalho

Research output: Contribution to journalArticlepeer-review


Motivated by a real-world application, we present a multi-container loading problem with 3-open dimensions. We formulate it as a biobjective mixed-integer nonlinear program with lexicographic objectives in order to reflect the decision maker’s optimization priorities. The first objective is to minimize the number of containers, while the second objective is to minimize the volume of those containers. Besides showing the NP-hardness of this sequential optimization problem, we provide bounds for it which are used in the three proposed algorithms, as well as, on their evaluation when a certificate of optimality is not available. The first is an exact parametric-based approach to tackle the lexicographic optimization through the second objective of the problem. Nevertheless, given that the parametric programs correspond to large nonlinear mixed-integer optimizations, we present a heuristic that is entirely mathematical-programming based. The third algorithm enhances the solution quality of the heuristic. These algorithms are specifically tailored for the real-world application. The effectiveness and efficiency of the devised heuristics is demonstrated with numerical experiments.

Original languageEnglish
Number of pages22
Early online date29 Aug 2022
Publication statusPublished - Sept 2023


  • 3-open dimensions
  • Lexicographic optimization
  • Mixed-integer programming
  • Packing
  • Practice of OR


Dive into the research topics of 'Lexicographic optimization for the multi-container loading problem with open dimensions for a shoe manufacturer'. Together they form a unique fingerprint.

Cite this