Furini, Fabio
(2011)
Decomposition and reformulation of integer linear programming problems, [Dissertation thesis], Alma Mater Studiorum Università di Bologna.
Dottorato di ricerca in
Automatica e ricerca operativa, 23 Ciclo. DOI 10.6092/unibo/amsdottorato/3593.
Documenti full-text disponibili:
Abstract
This thesis deals with an investigation of Decomposition and Reformulation to solve Integer
Linear Programming Problems. This method is often a very successful approach computationally,
producing high-quality solutions for well-structured combinatorial optimization problems
like vehicle routing, cutting stock, p-median and generalized assignment . However, until now
the method has always been tailored to the specific problem under investigation. The principal
innovation of this thesis is to develop a new framework able to apply this concept to
a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation
of the input problem applicable as a resolving black box algorithm and works as
a complement and alternative to the normal resolving techniques. The idea of Decomposing
and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is,
given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the
partially convexified polyhedron(s) obtained. For a given MIP several decompositions can
be defined depending from what sets of constraints we want to convexify. In this thesis we
mainly reformulate MIPs using two sets of variables: the original variables and the extended
variables (representing the exponential extreme points). The master constraints consist of
the original constraints not included in any slaves plus the convexity constraint(s) and the
linking constraints(ensuring that each original variable can be viewed as linear combination
of extreme points of the slaves). The solution procedure consists of iteratively solving the
reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and
in which case adding it to the master and solving it again (columns generation), or otherwise
stopping the procedure. The advantage of using DWD is that the reformulated relaxation
gives bounds stronger than the original LP relaxation, in addition it can be incorporated in
a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality.
If the computational time for the pricing problem is reasonable this leads in practice to a
stronger speed up in the solution time, specially when the convex hull of the slaves is easy
to compute, usually because of its special structure.
Abstract
This thesis deals with an investigation of Decomposition and Reformulation to solve Integer
Linear Programming Problems. This method is often a very successful approach computationally,
producing high-quality solutions for well-structured combinatorial optimization problems
like vehicle routing, cutting stock, p-median and generalized assignment . However, until now
the method has always been tailored to the specific problem under investigation. The principal
innovation of this thesis is to develop a new framework able to apply this concept to
a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation
of the input problem applicable as a resolving black box algorithm and works as
a complement and alternative to the normal resolving techniques. The idea of Decomposing
and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is,
given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the
partially convexified polyhedron(s) obtained. For a given MIP several decompositions can
be defined depending from what sets of constraints we want to convexify. In this thesis we
mainly reformulate MIPs using two sets of variables: the original variables and the extended
variables (representing the exponential extreme points). The master constraints consist of
the original constraints not included in any slaves plus the convexity constraint(s) and the
linking constraints(ensuring that each original variable can be viewed as linear combination
of extreme points of the slaves). The solution procedure consists of iteratively solving the
reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and
in which case adding it to the master and solving it again (columns generation), or otherwise
stopping the procedure. The advantage of using DWD is that the reformulated relaxation
gives bounds stronger than the original LP relaxation, in addition it can be incorporated in
a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality.
If the computational time for the pricing problem is reasonable this leads in practice to a
stronger speed up in the solution time, specially when the convex hull of the slaves is easy
to compute, usually because of its special structure.
Tipologia del documento
Tesi di dottorato
Autore
Furini, Fabio
Supervisore
Co-supervisore
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Ciclo
23
Coordinatore
Settore disciplinare
Settore concorsuale
Parole chiave
Combinatorial Optimisation, Integer Programming,Decomposition and Reformulation,Column
Generation, Resource Allocation Problem, AVG Assignment Problem.
URN:NBN
DOI
10.6092/unibo/amsdottorato/3593
Data di discussione
29 Marzo 2011
URI
Altri metadati
Tipologia del documento
Tesi di dottorato
Autore
Furini, Fabio
Supervisore
Co-supervisore
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Ciclo
23
Coordinatore
Settore disciplinare
Settore concorsuale
Parole chiave
Combinatorial Optimisation, Integer Programming,Decomposition and Reformulation,Column
Generation, Resource Allocation Problem, AVG Assignment Problem.
URN:NBN
DOI
10.6092/unibo/amsdottorato/3593
Data di discussione
29 Marzo 2011
URI
Statistica sui download
Gestione del documento: