Projective Cutting-Planes for Robust Linear Programming and Cutting Stock Problems
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)