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.
| Identifer | oai:union.ndltd.org:unibo.it/oai:amsdottorato.cib.unibo.it:3593 |
| Date | 29 March 2011 |
| Creators | Furini, Fabio <1982> |
| Contributors | Toth, Paolo |
| Publisher | Alma Mater Studiorum - Università di Bologna |
| Source Sets | Università di Bologna |
| Language | English |
| Detected Language | English |
| Type | Doctoral Thesis, PeerReviewed |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds