Algebraic and Combinatorial Methods in Operations Research (Mathematics Studies)
By Rainer E. Burkard
(November 1984)
* Publisher: Elsevier
* Number Of Pages: 390
* ISBN-10 / ASIN: 0444875719
* ISBN-13 / EAN: 9780444875716
FOREWORD
A recurring theme in operations research (O.R.) is that of optimization, and over the
last 35 years the subjects of O.R. and mathematical programming have developed
side by side and enriched one another.
Much traditional 0.R has been concerned with the behaviour of continuous real
variables representing e.g. material stocks, time or money, and the corresponding
Optimization theory is one in which real linear algebra, inequalities and the differential
calculus have played important roles. However, many systems with which O.R. is
concerned incorporate discrete structures for which the optimization questions are
combinatorial rather than continuous: one thinks of sequencing, scheduling and
flow-problems and of the great variety of questions which can be reformulated as
path-finding circuit-finding or sub-graph-finding problems on an abstract graph.
Correspondingly, we have witnessed a vigorous growth in the theory and practice of
combinatorial optimization.
A related, but perhaps less well-known, development has been in the application of
ordered algebraic structures to optimization problems. This application is made relevant
by the fact that many optimization questions depend essentially on the presence
of two features: an algebraic language within which a system can be modelled and an
algorithm articulated; and an ordering among the elements which enables a significance
to be given to the concept of minimization or maximization.
By adopting this slightly abstract point of view, we can make useful reformulations:
certain bottleneck problems become algebraic linear programs; certain machinescheduling
problems reduce to finding eigenvectors and eigenvalues of a matrix over
a semiring; certain path-finding problems reduce to the solution of linear equations
over an ordered structure.
Many optimization problems of the kind which have arisen in O.R. assume, under
such reformulation, the appearance of problems of linear algebra over an ordered system
of scalars. Hence we may look to the highly-developed classical theory of linear
algebra over the real field to give us hints as to how we might approach these problems
or, if appropriate adaptations of classical techniques cannot be found, we have a
well-defined research program to elucidate the theory of linear algebra over such
ordered structures, and to see how far the algorithms and duality principles, familiar
to us from linear and combinatorial optimization over the real field, extend to more
general structures
These questions have stimulated a good deal of research over the last twenty-five
years. From a few isolated publications by one or two researchers in the late 1960’s
the subject has matured into an identifiable branch of applicable mathematics, with
an international following. We invited a number of those who have contributed to
this development, to participate in the production of a publication featuring some
of their more recent work. It is the result of their enthusiastic acceptance of this invk
tation which we are now pleased to present as this volume in the series of Annals of
Discrete Mathematics.
R.E. Burkard
R.A. Cuninghame-Green
U. Zimmermann
Acknowle&ement: I should like to add a personal note of gratitude to Tricia Carr,
who made such a beautiful job of preparing the manuscript.
R.A. Cunjnghame-Green
CONTENTS
Foreword
J. ARAOZ, Packing problems in semigroup programming
P. BRUCKER, A greedy algorithm for solving network flow problems
in trees
P. BRUCKER, W. PAPENJOHANN, and U. ZIMMERMANN, A dual
optimality criterion for algebraic linear programs
P. BUTKOVIC, On properties of solution sets of extremal linear programs
R.A. CUNINGHAME-GREEN, Using fields for semiring computations
R.A. CUNINGHAME-GREEN and W.F. BORAWITZ, Scheduling by
non-commutative algebra
Ck EBENEGGER, P.L. HAMMER, and D. DE WERRA, Pseudo-boolean
functions and stability of graphs
R. EULER, Independence systems and perfect k-matroid-intersections
U. FAIGLE, Matroids on ordered sets and the greedy algorithm
A. FRANK and E. TARDOS, An algorithm for the unbounded matroid
intersection polyhedron
A.M. FRIEZE, Algebraic Flows
M. GONDRAN, and M. MINOUX, Linear algebra in dioids: a survey of
recent results
H.W. HAMACHER and S. TUFEKCI, Algebraic flows and time-cost
tradeoff problems
H.W. HAMACHER, J.-C. PICARD, and M. QUEYRANNE, Ranking the
cuts and cut-sets of a network
P. HANSEN, Shortest paths in signed graphs 201
B.L HULME, A.W. SHIVER, and P.J. SLATER, A boolean algebraic
analysis of fae protection 215
B. MAHR, Iteration and summability in semirings 229
RH. MOHRING, and F.J. RADERMACHER, Substitution decomposition
for discrete structures and connections with combinatorial
optimization 25 7
K. ZIMMERMA", On max-separable optimization problems 357
U. ZIMMERMA", Minimization of combined objective functions on
integral submolar flows 363
http://ifile.it/k4jgd01/273974___0444875719_algebraic_and_combinatorial.rar
