Abstract
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 lotsizing with supplier selection, the network design and the vendormanaged inventory routing problems. These sets are variants of the wellknown single node fixedcharge 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 facetdefining 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.
Original language  English 

Qualification  PhD 
Awarding Institution 

Supervisors/Advisors 

Award date  4 Feb 2014 
Place of Publication  Aveiro, Portugal 
Publication status  Published  4 Feb 2014 
Externally published  Yes 
Fingerprint
Keywords
 mixed integer programming
 inventory problems
 polyhedral theory
 valid inequality
 facetdefining inequality
 convex hull
 separation problem
 extended formulation
 computational experiment
Cite this
}
Polyhedral Study of Mixed Integer Sets Arising from Inventory Problems. / Doostmohammadi, Mahdi.
Aveiro, Portugal, 2014. 136 p.Research output: Thesis › Doctoral Thesis
TY  THES
T1  Polyhedral Study of Mixed Integer Sets Arising from Inventory Problems
AU  Doostmohammadi, Mahdi
PY  2014/2/4
Y1  2014/2/4
N2  "Branchandcut" algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branchandbound approach and cutting planes scheme. Branchandcut 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 branchandcut 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 lotsizing with supplier selection, the network design and the vendormanaged inventory routing problems. These sets are variants of the wellknown single node fixedcharge 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 facetdefining 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.
AB  "Branchandcut" algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branchandbound approach and cutting planes scheme. Branchandcut 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 branchandcut 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 lotsizing with supplier selection, the network design and the vendormanaged inventory routing problems. These sets are variants of the wellknown single node fixedcharge 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 facetdefining 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.
KW  mixed integer programming
KW  inventory problems
KW  polyhedral theory
KW  valid inequality
KW  facetdefining inequality
KW  convex hull
KW  separation problem
KW  extended formulation
KW  computational experiment
UR  http://hdl.handle.net/10773/12864
UR  http://www.ua.pt/
M3  Doctoral Thesis
CY  Aveiro, Portugal
ER 