|
 
|
[Por16a] Ray Projection for Optimizing Polytopes with Prohibitively Many Constraints in Set-Covering Column Generation
Revue Internationale avec comité de lecture : Journal Mathematical Programming, vol. 155(1), pp. 147-197, 2016, (doi:dx.doi.org/10.1007/s10107-014-0840-7)Mots clés: Linear Programming, Column Generation, Dynamic Programming, Ray Projection
Résumé:
A recurrent task in mathematical programming consists of optimizing polytopes with
prohibitively-many constraints, e.g., the primal polytope in cutting-planes methods or the dual
polytope in Column Generation (CG). We present a method to optimize such polytopes using the
following intersection sub-problem: given ray r∈Z_n , find the maximum t≥0 such that tr is
feasible. We interpret 0→r as a direction of growth from the origin 0 ;tr is the intersection
point between 0→r and the polytope boundary. To ease the exposition, the first part of the paper
is devoted to the general context of a (primal or dual) polytope with rational data such that: (i)
the intersection sub-problem can be effectively solved in practice for input rays r ∈ Zn and (ii) 0
is feasible. By iterating over such rays r, our method produces a sequence of feasible solutions tr
that we prove to be finitely convergent. From Section 3 on, we focus on dual polytopes in CG
formulations. Typically, if the CG (separation) sub-problem can be solved by Dynamic Programming
(DP), so can be the intersection sub-problem. The proposed Integer Ray Method (IRM) only uses
integer rays, and so, the intersection sub-problem can be solved using a DP scheme based on states
indexed by integer ray values. We show that under 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 consists of fractional (or large-range) values. As
such, the IRM 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 class that includes Variable Size Bin Packing).
Equipe:
oc
BibTeX
| @article { | |||
| Por16a, | |||
| title | = | "{Ray Projection for Optimizing Polytopes with Prohibitively Many Constraints in Set-Covering Column Generation}", | |
| author | = | "D. Porumbel", | |
| journal | = | "Mathematical Programming", | |
| year | = | 2016, | |
| volume | = | 155, | |
| number | = | 1, | |
| pages | = | "147-197", | |
| doi | = | "dx.doi.org/10.1007/s10107-014-0840-7", | |
| } | |||
