"Cutting Planes, Column Generation and Decomposition with Interior Point Methods"Gondzio, JacekAdvantages of interior point methods (IPMs) applied in the context of nondifferentiable optimization arising in applications such as cutting planes/column generation and various decomposition schemes (Benders, Dantzig-Wolfe) will be discussed. Some of the many false views of the combinatorial optimization community on interior point methods applied in this context will be addressed and corrected. For example, IPMs deliver a natural stabilization when restricted master problems are solved and guarantee fast convergence, measured with merely a few master iterations needed to localize the solution. When applied in the context of decomposition, IPMs deliver epsilon-subgradients and are well-suited to handle the oracles with on-demand accuracy. Various such techniques have been discussed in the recent survey on IPMs ('Interior point methods in the year 2025', EURO J. on Computational Optimization, 2025, {\tt https://doi.org/10.1016/j.ejco.2025.100105}). An approach which combines column generation with IPMs has been successfully used to solve a plethora of applications which include, (robust) vehicle routing problems with time windows, multiple kernel learning problems, truss geometry and topology optimization problems or discrete optimal transport problems, to mention just a few. |
« back