A recurrent task in mathematical programming requires optimizing polytopes with prohibitively-many constraints, e.g., the primal polytope in cutting-plane methods or the dual polytope in Column Generation (CG). This paper is devoted to the ray projection technique for optimizing such polytopes: start from a feasible solution and advance on a given ray direction until intersecting a polytope facet. The resulting intersection point is determined by solving the intersection sub-problem: given ray r∈Zn, find the maximum t≥0 such that tr is feasible. We focus on dual polytopes associated to CG: if the CG (separation) sub-problem can be solved by Dynamic Programming (DP), so can be the intersection sub-problem. The convergence towards the CG optimum is realized through a sequence of intersection points tr (feasible dual solutions) determined from such rays r. Our method only uses integer rays r, so as to render the intersection sub-problem tractable by r-indexed DP. We show that in such conditions, the intersection sub-problem can be even easier than the CG sub-problem, especially when no other integer data is available to index states in DP, i.e., if the CG sub-problem input only consists of fractional (or large-range) values. As such, the proposed method can tackle scaled instances (with large-range weights) of capacitated problems that seem prohibitively hard for classical CG. This is confirmed by numerical experiments on various capacitated Set-Covering problems: Capacitated Arc-Routing, Cutting-Stock and other three versions of Elastic Cutting-Stock (i.e., a problem that include Variable Size Bin Packing). We also prove the theoretical convergence of the proposed method.
Citation
submitted work (Artois University, PRES Lille Nord de France)