Using Column Generation in Column-and-Constraint Generation for Adjustable Robust Optimization (AE)

Jointly with Martin Schmidt, Johannes Thürauf

Year: 2023

Abstract: Adjustable robust optimization (ARO) is a powerful tool to model problems that have uncertain data and that feature a two-stage decision making process. Computationally, they are often addressed using the column-and-constraint generation (CCG) algorithm introduced by Zeng and Zhao (2013). While it was empirically shown that the algorithm scales well if all second-stage decisions are continuous, the presence of integer variables in the second stage rapidly leads to challenging large-scale mixed-integer problems within CCG. These problems can no longer be solved to global optimality within reasonable time limits in general. In this work, we explicitly focus on ARO problems with mixed-integer second-stage decisions and discuss the main difficulties of successfully applying CCG to this problem class. We then introduce, for a large set of problems with specific structural properties, a stronger formulation, which can be used in place of the master problem in the classic CCG algorithm. We show how this model can be effectively solved by column generation (CG). Additionally, we introduce a new CG-based heuristic that is able to generate new feasible points to speed up the overall method. We apply this nested scheme, combining CCG and CG, to two problems in logistics and scheduling. The numerical results show that the proposed method significantly outperforms the classic CCG.

Cite as:

@misc{lefebvre2023column,
  title={Column Generation in Column-and-Constraint Generation for Adjustable Robust Optimization with Interdiction-Type Linking Constraints},
  author={Henri Lefebvre and Martin Schmidt and Johannes Thürauf},
  year={2023},
  archivePrefix={Optimization Online},
  url={https://optimization-online.org/?p=24462}
}

Open Access

Optimization Online

Open Data

All the data which were used are available on our GitHub.
FLP instances JSP instances GAP instances

Open Methodology

We have open methodology on our experimental results thanks to rmarkdown.
FLP: Compiled version JSP: Compiled version GAP: Compiled version

Open Source

Our code is publicly available on our GitHub repository.
hlefebvr/AE-using-column-generation-in-column-and-constraint-generation/

Open Educational Resources