06-17
Separable convex minimization in bounded integers under totally unimodular linear equations
Preprint series: 06-18, Preprints
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 optimality -- Alternating optimization method -- Fenchel duality
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.