Go to the content. | Move to the navigation | Go to the site search | Go to the menu | Contacts | Accessibility

| Create Account

Di Summa, Marco (2008) Formulations of mixed-integer sets defined by totally unimodular constraint matrices. [Ph.D. thesis]

Full text disponibile come:

Documento PDF

Abstract (english)

A mixed-integer program is an optimization problem where one is required to minimize a linear function over a subset defined by a system of linear inequalities, with the additional restriction that some of the variables must take an integer value. Many real-world problems can be formulated as mixed-integer programs.

Solving mixed-integer programs is difficult in general. A common approach to tackle this kind of problems exploits the fact that (under mild assumptions) the convex hull of feasible solutions is a polyhedron. When the inequalities describing such a polyhedron are known explicitly, the mixed-integer program reduces to a linear program, which is a tractable problem. Unfortunately it is usually very hard to find a linear inequality description of the convex hull of feasible solutions of a mixed-integer program. However in some cases the introduction of additional variables allows one to give a simple description of such a convex hull by means of linear inequalities in a higher dimensional space. Such a description is called an extended formulation. If an extended formulation is known that is compact (i.e. it uses a polynomial number of variables and constraints), the original mixed-integer programming problem can be solved in polynomial time by means of linear programming algorithms.

In this dissertation we study the family of mixed-integer programs whose feasible regions are defined by linear systems with totally unimodular matrices (i.e. all subdeterminants are 0, 1 or -1) having at most two nonzero entries per row. This class of problems is interesting because many instances arising e.g. in the context of production planning can be formulated as mixed-integer programs of this type.

We illustrate a technique to construct an extended formulation for any problem in this family. The approach is based on the enumeration of all possible fractional parts that the variables take at the vertices of the convex hull of the feasible region.

We then discuss the compactness of our extended formulation: we give sufficient conditions ensuring that the formulation is compact. When one of these conditions holds, the mixed-integer program can be solved in polynomial time. We also show how our technique can be successfully applied to some interesting practical problems.

Next we consider the possibility of describing the convex hull of the feasible region in the original space of definition of the problem (i.e with no additional variables). Such a formulation is found explicitly for some special cases.

Finally a possible extension is discussed: we show how a generalization of our technique can lead to a compact extended formulation for a problem that does not belong to the family introduced above.

Statistiche Download - Aggiungi a RefWorks
EPrint type:Ph.D. thesis
Tutor:Conforti, Michele
Ph.D. course:Ciclo 20 > Scuole per il 20simo ciclo > SCIENZE MATEMATICHE > MATEMATICA COMPUTAZIONALE
Data di deposito della tesi:January 2008
Anno di Pubblicazione:January 2008
Key Words:Mixed-integer programming, compact extended formulations.
Settori scientifico-disciplinari MIUR:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Struttura di riferimento:Dipartimenti > Dipartimento di Matematica
Codice ID:399
Depositato il:07 Oct 2008
Simple Metadata
Full Metadata
EndNote Format

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record