Optimization Online


Ray Projection for Optimizing Polytopes with Prohibitively Many Constraints in Set-Covering Column Generation

Daniel Porumbel(daniel.porumbel***at***univ-artois.fr)

Abstract: 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.

Keywords: Column Generation, Intersection Problem

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Citation: submitted work (Artois University, PRES Lille Nord de France)

Download: [PDF]

Entry Submitted: 09/30/2013
Entry Accepted: 09/30/2013
Entry Last Modified: 09/30/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society