Polyhedral Study of Mixed Integer Sets Arising from Inventory Problems

Research output: ThesisDoctoral Thesis

Abstract

"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.
LanguageEnglish
QualificationPhD
Awarding Institution
  • University of Aveiro
Supervisors/Advisors
  • Agra, Agostinho, Supervisor, External person
Award date4 Feb 2014
Place of PublicationAveiro, Portugal
Publication statusPublished - 4 Feb 2014
Externally publishedYes

Fingerprint

Integer
Branch-and-cut
Cutting Planes
Valid Inequalities
Supplier Selection
Mixed Integer Program
Vehicle routing
Vertex of a graph
Linear programming
Cutting Plane Algorithm
Vehicle Routing
Linear Programming Relaxation
Binary Variables
Lot Sizing
Search Trees
Routing Problem
Branch-and-bound
Substructure
Network Design
Facet

Keywords

  • mixed integer programming
  • inventory problems
  • polyhedral theory
  • valid inequality
  • facet-defining inequality
  • convex hull
  • separation problem
  • extended formulation
  • computational experiment

Cite this

@phdthesis{d7407d007a7e4cf5a97a76caca60ec40,
title = "Polyhedral Study of Mixed Integer Sets Arising from Inventory Problems",
abstract = "{"}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.",
keywords = "mixed integer programming, inventory problems, polyhedral theory, valid inequality, facet-defining inequality, convex hull, separation problem, extended formulation, computational experiment",
author = "Mahdi Doostmohammadi",
year = "2014",
month = "2",
day = "4",
language = "English",
school = "University of Aveiro",

}

Polyhedral Study of Mixed Integer Sets Arising from Inventory Problems. / Doostmohammadi, Mahdi.

Aveiro, Portugal, 2014. 136 p.

Research output: ThesisDoctoral 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 - "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.

AB - "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.

KW - mixed integer programming

KW - inventory problems

KW - polyhedral theory

KW - valid inequality

KW - facet-defining 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 -