CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Aspects of Duality in Integer Programming

Tuomo Takkula (Institutionen för datavetenskap)
Göteborg : Chalmers University of Technology, 2003. ISBN: 91-7291-256-1.- 212 s.
[Doktorsavhandling]

This thesis deals with various problems arising when dualizing integer programs and combinatorial optimization problems. On the one hand, the corresponding dual functions are piecewise linear, calling for approaches from nondifferentiable optimization; on the other hand, the problems have special structures which can be exploited.

Line searches along the dual function of integer programs are an example of when the latter is the case. We introduce efficient specialized line search procedures for the dual functions of binary programs, the Lagrangian-surrogate dual of the TSP and the p-median problem, and for the dual function of the shortest path problem with a knapsack constraint.

A specialized line search is also used for a conditional epsilon-ascent bundle method for the dual function of binary programs. There the line search has a different role than before: instead of finding the maximum of a one-dimensional function, the line search must deliver a conditional epsilon-subgradient. We show how this can be done efficiently and exactly.

We employ duality theory to the satisfiability problem (SAT) in order to prove unsatisfiability. In order to do this, the SAT problem is converted into an equivalent binary program modeling the "minimum unsatisfiable clauses" problem. We approach this problem by dualizing the problem, yielding a lower bound on the number of unsatisfiable clauses. If this value is strictly positive, then the instance is nonsatisfiable. Two dualizations are tested, namely the Lagrangian dual (with very moderate success) and the split dual from Lagrangian decomposition (variable splitting), with encouraging results.

In a final note we discuss possibilities to extend the usual notion of piecewise linear in order to capture functions which "look" piecewise linear, but wouldn't fit the usual definition. We comment on certain difficulties one encounters when doing this.



Denna post skapades 2006-08-25. Senast ändrad 2013-09-25.
CPL Pubid: 279

 

Institutioner (Chalmers)

Institutionen för datavetenskap (2002-2004)

Ämnesområden

Information Technology

Chalmers infrastruktur

Ingår i serie

Technical report D - School of Computer Science and Engineering, Chalmers University of Technology 15


Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie 1938