Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Graph Generation: A New Approach to Solving Expanded Linear Programming
  Relaxations   In this article we introduce Graph Generation, an enhanced Column Generation
(CG) algorithm for solving expanded linear programming relaxations of mixed
integer linear programs. To apply Graph Generation, we must be able to map any
given column to a small directed acyclic graph for which any path from source
to sink describes a feasible column. This structure is easily satisfied for
vehicle routing and crew scheduling problems; and other such problems where
pricing is a resource constrained shortest path problem. Such graphs are then
added to the restricted master problem (RMP) when the corresponding column is
generated during pricing. The use of Graph Generation does not weaken the
linear programming relaxation being solved. At any given iteration of CG
enhanced by Graph Generation; the technique permits the RMP to express a much
wider set of columns than those generated during pricing, leading to faster
convergence of CG. Graph Generation does not change the structure of the CG
pricing problem. We show how the method can be applied in a general way, and
then demonstrate the effectiveness of our approach on the classical Capacitated
Vehicle Routing Problem.

33
The categories of this paper are: plasm-ph
24
The categories of this paper are: dg-ga
20
The categories of this paper are: acc-phys
8
The categories of this paper are: hep-ex
31
The categories of this paper are: ao-sci
11
The categories of this paper are: hep-lat
0
The categories of this paper are: hep-ph
14
The categories of this paper are: math-ph
9
The categories of this paper are: nlin
26
The categories of this paper are: bayes-an
32
The categories of this paper are: atom-ph
16
The categories of this paper are: stat
6
The categories of this paper are: astro-ph
13
The categories of this paper are: quant-ph
18
The categories of this paper are: econ
28
The categories of this paper are: alg-geom