Skip to Main content Skip to Navigation
Journal articles

Projective Cutting-Planes for Robust Linear Programming and Cutting Stock Problems

Daniel Porumbel 
Abstract : We explore the Projective Cutting-Planes algorithm proposed in Porumbel (2020) from new angles by applying it to two new problems, that is, to robust linear programming and to a cutting-stock problem with multiple lengths. Projective Cutting-Planes is a generalization of the widely used Cutting-Planes, and it aims at optimizing a linear function over a polytope P with prohibitively many constraints. The main new idea is to replace the well-known separation subproblem with the following projection subproblem: given an interior point x∈P and a direction d, find the maximum steplength t such that x + td ∈ P. This enables one to generate a feasible solution at each iteration, a feature that does not exist built-in in a standard Cutting-Planes algorithm. The practical success of this new algorithm does not mainly come from the higher level ideas already presented in Porumbel (2020). Its success is significantly more dependent on the computation time needed to solve the projection subproblem in practice. Thus, the main challenge addressed by the current paper is the design of new techniques for solving this subproblem very efficiently for different polytopes P. We first address a well-known robust linear programming problem in which P is defined as a primal polytope. We then solve a multiple-length cutting stock problem in which P is a dual polytope defined in a column generation model. Numerical experiments on both these new problems confirm the potential of the proposed ideas. This enables us to draw conclusions supported by numerical results from both the current paper and Porumbel (2020) while also gaining more insight into the dynamics of the algorithm.
Document type :
Journal articles
Complete list of metadata

https://hal-cnam.archives-ouvertes.fr/hal-03715458
Contributor : Marie-Liesse Bertram Connect in order to contact the contributor
Submitted on : Tuesday, July 19, 2022 - 1:28:12 PM
Last modification on : Friday, August 5, 2022 - 3:24:26 PM

File

ijoc2022.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Daniel Porumbel. Projective Cutting-Planes for Robust Linear Programming and Cutting Stock Problems. INFORMS Journal on Computing, Institute for Operations Research and the Management Sciences (INFORMS), In press, ⟨10.1287/ijoc.2022.1160⟩. ⟨hal-03715458⟩

Share

Metrics

Record views

0

Files downloads

0