  


Ray Projection for Optimizing Polytopes with Prohibitively Many Constraints in SetCovering Column Generation
Daniel Porumbel(daniel.porumbelunivartois.fr) Abstract: A recurrent task in mathematical programming requires optimizing polytopes with prohibitivelymany constraints, e.g., the primal polytope in cuttingplane 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 subproblem: 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) subproblem can be solved by Dynamic Programming (DP), so can be the intersection subproblem. 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 subproblem tractable by rindexed DP. We show that in such conditions, the intersection subproblem can be even easier than the CG subproblem, especially when no other integer data is available to index states in DP, i.e., if the CG subproblem input only consists of fractional (or largerange) values. As such, the proposed method can tackle scaled instances (with largerange weights) of capacitated problems that seem prohibitively hard for classical CG. This is confirmed by numerical experiments on various capacitated SetCovering problems: Capacitated ArcRouting, CuttingStock and other three versions of Elastic CuttingStock (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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  