TY: THES
T1 - Polyhedral study of mixed integer sets arising from inventory problems
A1 - Doostmohammadi, Mahdi
N2 - ?Branch-and-cut? algorithm is one of the most efficient exact approaches
to solve mixed integer programs. This algorithm combines
the advantages of a pure branch-and-bound approach and cutting
planes scheme. Branch-and-cut algorithm computes the linear
programming relaxation of the problem at each node of the search
tree which is improved by the use of cuts, i.e. by the inclusion of valid
inequalities. It should be taken into account that selection of strongest
cuts is crucial for their effective use in branch-and-cut algorithm.
In this thesis, we focus on the derivation and use of cutting
planes to solve general mixed integer problems, and in particular
inventory problems combined with other problems such as distribution,
supplier selection, vehicle routing, etc. In order to achieve this goal,
we first consider substructures (relaxations) of such problems which
are obtained by the coherent loss of information. The polyhedral
structure of those simpler mixed integer sets is studied to derive strong
valid inequalities. Finally those strong inequalities are included in the
cutting plane algorithms to solve the general mixed integer problems.
We study three mixed integer sets in this dissertation. The first
two mixed integer sets arise as a subproblem of the lot-sizing with
supplier selection, the network design and the vendor-managed
inventory routing problems. These sets are variants of the well-known
single node fixed-charge network set where a binary or integer variable
is associated with the node. The third set occurs as a subproblem
of mixed integer sets where incompatibility between binary variables
is considered. We generate families of valid inequalities for those
sets, identify classes of facet-defining inequalities, and discuss the
separation problems associated with the inequalities. Then cutting
plane frameworks are implemented to solve some mixed integer
programs. Preliminary computational experiments are presented in
this direction.
UR - https://ria.ua.pt/handle/10773/12864
Y1 - 2013
PB - Universidade de Aveiro