Two simple applications of the unimodularity property

One of the most important and useful properties of Totally Unimodular (TU) matrices is the integrality of all the extreme points of the polyhedron [ x; Ax ⩽ b, x ⩾0, b integer] where A is TU. In this paper we present two applications of this property to situations where integer optimal solutions are...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 1993, Vol.14 (5), p.257-260
Main Authors: Charnes, A., Kress, M.
Format: Article
Language:English
Subjects:
Applied sciences
distribution problem
Exact sciences and technology
Flows in networks. Combinatorial problems
network problem
Operational research and scientific management
Operational research. Management science
totally unimodular matrix
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:One of the most important and useful properties of Totally Unimodular (TU) matrices is the integrality of all the extreme points of the polyhedron [ x; Ax ⩽ b, x ⩾0, b integer] where A is TU. In this paper we present two applications of this property to situations where integer optimal solutions are generated from noninteger ones. The first applications relates to a manpower distribution problem where one wishes to maximize the number of nonzero (integer) assignments. The second model is applied to a network problem with flow separation side constraints.
ISSN:0167-6377
1872-7468
DOI:10.1016/0167-6377(93)90090-4