Zurück zu den Preprints des Jahres 2006


2006-18

Separable convex minimization in bounded integers under totally unimodular linear equations

by Gaffke, N., Pukelsheim, F..


Series: 2006-18, Preprints

MSC:
90C10 Integer programming
90B80 Discrete location and assignment

Abstract:
We consider the problem of minimizing a separable convex function of a nonnegative integer vector $x$ and subject to linear equality constraints $Ax = b$, where $A$ is a totally unimodular matrix and $b$ is an integer vector. Also upper bounds for the components of $x$ are prescribed. A characterization of optimal solutions is obtained and a conceptual primal algorithm is stated. A dual problem is established along with a conceptual dual algorithm. The conceptual algorithms are made concrete for two particular cases, the more interesting of which is when $A$ is the vertex-edge incidence matrix of a bipartite graph. Here it turns out that the dual algorithm is related to that of Balinski and Demange (1989) for biproportional (integer) rounding of a nonnegative matrix. In fact, that problem fits into the presend optimization framework. Also, we examine a dual alternating maximization heuristics which requires relatively low computational effort. As a further
alternative, we consider the linear programming approach from the book of Dantzig (1998) to our primal problem. However, the price to be paid is a considerable increase of the number of variables. Besides that, the solution obtained may have non-integer components and the task of appropriate rounding comes in general. Finally, we show the relation to Fenchel duality in convex programming.

Keywords:
Totally unimodular matrix -- Elementary vector -- Bipartite graph -- Compatible Tension Algorithm -- Labelling algorithm -- Transportation polytope -- Theorem of alternatives -- Weak Pareto