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 [Formula: see text] 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 [Formula: see text] and a direction [Formula: see text], find the maximum steplength t such that [Formula: see text]. 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 [Formula: see text]. We first address a well-known robust linear programming problem in which [Formula: see text] is defined as a primal polytope. We then solve a multiple-length cutting stock problem in which [Formula: see text] 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. Summary of Contribution: The well-known Cutting-Planes algorithm relies on the separation subproblem to cut off the current optimal solution. This paper belongs to a line of work whose goal is to “upgrade” the widely used separation subproblem to the following projection subproblem: given a feasible solution x inside some polytope P and a direction d, what is the maximum t value such that x + td ∈ P. In simple terms, one has to “shoot” from x along direction d up to the point where the boundary of the polytope is hit. The greatest challenge is to solve this projection subproblem rapidly enough to compete well in terms of computational speed with the separation subproblem algorithm. This paper shows how to achieve this on two new problems: robust linear programming and multiple length cutting stock. The numerical results confirm one important advantage offered by the projection logic: it enables one to generate a new feasible interior solution (i.e., x + td) at each iteration. The interior points thus generated actually guide the evolution of the overall algorithm, which is a feature that does not exist (built-in) in a traditional Cutting-Planes algorithm.

We propose an aggregation method to reduce the size of column generation (CG) models for covering problems in which the feasible subsets depend on a resource constraint. The aggregation relies on a correlation between the resource consumption of the elements and the corresponding optimal dual values. The resulting aggregated dual model is a restriction of the original one, and it can be rapidly optimized to obtain a feasible dual solution. A primal bound can also be obtained by restricting the set of columns to those saturated by the dual feasible solution obtained by aggregation. The convergence is realized by iterative disaggregation until the gap is closed by the bounds. Computational results show the usefulness of our method for different cutting-stock problems. An important advantage is the fact that it can produce high-quality dual bounds much faster than the traditional Lagrangian bound used in stabilized column generation.

Date du colloque : 07/2011