The MPLS-OPS Archive[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index][Thread Index][Author Index][Subject Index] RE: Topology to LP converter
Manoj,
For your
> Thank you for explaining in great detail. Sorry for not
> being clear in my question. I am a student and thus
> looking for open source solutions. OSL is a good option
> but it also requires the input in MPS format.
>
> You are right that for MPLS design, shortest paths are
> not sufficient. I am working on developing an algorithm
> which will use these paths for load balancing. I have
> mathematically found that this should work and now I am
> simulating it for different topologies.
>
> If you can suggest some other package which can be used
> just for giving shortest path so as to use with LP
> solver, that would be really helpful for me.
>
> Thank you for your time and letting me know about OSL.
The OSL is just one of several options for software.
Also, the OSL does not require MPS input: I have used the OSL
frequently and have usually not used anything about MPS for
the input. The OSL is essentially just a collection of
subroutines. One of the first versions was written to be
called from a Fortran compiler from Watcom. Now the OSL is to
be called from C. Using the OSL just as a collection of
subroutines, the user writes some code in Fortran or C; that
code handles the input of the problem specification, calls the
OSL routines, and, possibly, generates the output to files,
graphs, the screen, other software, the Internet, whatever.
The subroutines want their input in arrays in Fortran or C as
in the OSL documentation, but, since you would be writing your
own code for reading the input, you have essentially complete
flexibility in the form of the input from files and need make
no use of the MPS input definitions.
There is some question about how to find all shortest paths in
a network. The broad division is between (1) Dijkstra's
algorithm (essentially a dynamic programming algorithm) and
related algorithms (e.g., Floyd's short algorithm), the work
of Ford and Fulkerson and (2) linear optimization on networks,
usually with the network simplex algorithm although possibly
with an algorithm with guaranteed polynomial performance.
Background Note (crash course!): Here we are in the
subject 'optimization' in applied mathematics. For
connections with practice, we have some work to do and
some freedom in how we do the work and want to know how
to exploit the freedom to get the work done for the least
possible total cost (or, it turns out, equivalently, the
greatest possible total profit). Here we convert the
real problem to a mathematical one, solve the
mathematical problem (usually with software and
computers), and apply the results in practice. In this
way, we can (1) save money on the work to be done and (2)
know that there is little or no more money to be saved
(can move on to something else being confident that there
is no more to be done). The field consists of
definitions, theorems, proofs, algorithms, heuristics,
software, computational experience, and applications
history. While it is possible to argue that the field
goes back to the ancient Greeks, the topics of greatest
interest now go back to the late 1940s with the work of
G. Dantzig at Rand. We could also mention L. Kantorovich
in the USSR. The field has played a major role in a
large fraction of the Nobel Prizes in Economic Sciences
(e.g., Kantorovich won in 1975). US business schools
have long had a standard introductory course in
optimization. Mostly the academic research has been done
in various departments of engineering. There are
connections with calculus of variations, optimal control
theory, stochastic optimal control theory, filtering,
statistical estimation, etc.
The research had some successes and discovered some
challenges. Some of the challenges were in computer
execution time, and one result was the criterion of an
algorithm being 'good' or 'polynomial' if it ran in time
that grew no faster than some polynomial in the size
(say, measured in bytes) of the input data. This
definition has also been of interest in the topic of
'computational complexity' in computer science.
A general problem statement in optimization would be: We
are given a function f that takes n variables and gives
one real value and a function g that takes n variables
and gives m real values. Then we ask for values of n
variables x to make 'objective function' f(x) as small as
possible while maintaining g(x) >= 0 (each of the m
values of g(x) >= 0). This form is quite general but
still less general than optimal control theory or
stochastic optimal control theory. If g(x) >= 0, then x
and the problem are 'feasible'. If there is no feasible
x, then the problem is said to be 'infeasible'. If there
exist feasible x to make f(x) as small as we please, then
the problem is 'unbounded'. If x is feasible and if, for
any feasible y, f(x) <= f(y), then x is 'optimal'. This
problem statement is commonly called 'nonlinear
optimization'.
Part of optimization is 'linear optimization' (or 'linear
programming' where here 'programming' is in the English
sense of 'operational planning'), and this is a special
case of the nonlinear formulation above. With linear
optimization, we are given a matrix A with m rows and n
columns, a vector c with n columns, and a vector b with m
rows and asked to find a vector x with n rows so that cx
is made a small as possible while maintaining both Ax = b
and x >= 0 (each component of x is >= 0). The first
effective means for attacking linear optimization was G.
Dantzig's simplex algorithm. This algorithm will tell if
a problem is feasible or infeasible, if feasible,
determine if problem is unbounded or not ('bounded'), and
if feasible and bounded, find an optimal solution. Since
Ax = b is a system of simultaneous linear equations, we
might guess that the standard elementary row operations
could be useful; indeed, Dantzig's simplex algorithm is
just elementary row operations done with a purpose in
mind -- save money. Experience showed that the simplex
algorithm is shockingly fast, in practice commonly
requiring about 2 to 3 times m 'iterations' (where each
iteration takes about m**3 arithmetic operations) for a
solution. Alas, the work of
V. Klee and G. J. Minty, "How Good Is the Simplex
Algorithm?", 'Inequalities III', edited by O.
Shisha, pages 159-175, Academic Press, New York,
1972.
showed that one specific version of the simplex algorithm
was not polynomial (and the more general conclusion was
that there could be similar examples for other versions).
The work of
K. H. Borgwardt, "The Average Number of Pivot Steps
Required by the Simplex Algorithm is Polynomial,"
'Zeitschrift fur Operations Research', volume 26,
pages 157-177, 1982.
essentially explained the fast performance observed in
practice. The work of
L. G. Khachian, "A Polynomial Algorithm in Linear
Programming", 'Soviet Mathematics Doklady', Volume
20, pages 191-194, 1979.
showed a polynomial algorithm (slow in practice) based on
some shrinking ellipsoids. The work of
N. Karmarkar, "A New Polynomial Time Algorithm for
Linear Programming", 'Combinatorica', Volume 4,
pages 375-395, 1984.
showed a polynomial algorithm often competitively fast in
practice and related to Khachian's work.
More recent work is in
Y. E. Nesterov and A. S. Nemirovsky, 'Interior Point
Polynomial Algorithms in Convex Programming: Theory
and Algorithms,' SIAM Publications, SIAM,
Philadelphia, 1994.
based on stabilization of Newton iteration.
In linear optimization, geometrically, the collection of
all feasible points is a convex set and an intersection
of finitely many closed half spaces (a hyperplane and all
of some one side of it). Thus there are finitely many
extreme points that are joined with a network of edges
between adjacent points. In looking for an optimal
solution, we can restrict ourselves to just the extreme
points. One iteration of the simplex algorithm moves
from one extreme point to an adjacent extreme point. So,
the simplex algorithm moves on the boundary of the
feasible region. It is also possible to move in the
(topologically relative) interior of the feasible region;
'interior point' methods do this.
It is fair to say that the two pillars of mathematics are
continuity and linearity, and linear optimization stands
on both. Thus, we will expect that, for problems that
are not linear optimization, one of the best approaches
will be to make linear approximations and apply linear
optimization. Net, linear optimization is one of the
most powerful tools we have for problems that are not
linear.
For example, for the nonlinear problem given above, that
form is too general to say very much. To say more, if
all the partial derivatives of f and g exist, then we can
try to use these to meet local necessary conditions for
optimality. The main topic here is the Kuhn-Tucker
conditions which really specify a problem in linear
optimization. With some assumptions of convexity (and
some generalizations), we can have the Kuhn-Tucker
conditions provide global sufficient conditions for
optimality.
With all details covered in full, the above is a
challenging one semester graduate course.
In practice, first-cut, we try to build on what we already
have available and not reinvent the wheel. So, you may want
to emphasize software you have or can readily get.
>From part of your question, I concluded that you wanted to get
a solution via linear optimization. Why I drew this
conclusion: Your question mentioned AMPL (A Mathematical
Programming Language, originally done at Bell Labs), MPS
(IBM's Mathematical Programming System) input format (long
something of an industry standard but clumsy and in some ways
costly), LP (linear programming) and LP solvers (e.g., OSL,
CPLEX). So, your question mentioned topics from software for
linear optimization.
You are correct that your problem of finding shortest paths
can be solved with linear optimization. I went on to point
out that the simplex algorithm applied to such network flow
problems takes on an especially simple form and is then called
the 'network simplex algorithm' and mentioned Cunningham's
paper with an anti-cycling rule for the network simplex
algorithm.
If you want to use the network simplex algorithm, then you
can: E.g., if you have access to the OSL, it has subroutines
for the network simplex algorithm.
One alternative is just to write your own code for the network
simplex algorithm. I would recommend:
Vasek Chvatal, 'Linear Programming', ISBN
0-7167-1587-2, W. H. Freeman, New York, 1983.
Dimitri P. Bertsekas, 'Linear Network Optimization:
Algorithms and Codes', ISBN 0-262-02334-2, MIT Press,
Cambridge, MA, 1991.
Mokhtar S. Bazaraa and John J. Jarvis, 'Linear
Programming and Network Flows', ISBN 0-471-06015-1, John
Wiley and Sons, New York, 1977.
The first has nearly all you will need including Cunningham's
anti-cycling rule. The second has some useful details not in
the first. The third mentions an important point: How to
handle upper bounds on arc capacities; it's easy to do once
you see how.
Note: The most interesting applications of the network
simplex algorithm are where all the arc capacities are
integers. In this case, if the problem is feasible and
bounded, then there exists an optimal solution with all
integer values. Using the simplex algorithm, we can get
an initial feasible solution with all integer values;
then the simplex algorithm will do only integer
arithmetic and, for a feasible problem, yield an optimal
solution with only integer values. In the software,
however, likely we should go ahead and use floating point
variables and arithmetic. For one, on most computers,
floating point arithmetic is exact for integers within
the limits of the floating point precision. For another,
for most programming languages, the longest precision
integer arithmetic accomplished directly with computer
hardware is available via the longest precision float
point arithmetic, not the longest precision integer
arithmetic. Of course, if we want to 'drop into
assembler', then we could make use of the longest
precision integer arithmetic supported by the computer
hardware which typically has a little more precision than
the longest such floating point precision. This point
about integer optimal solutions is important: We are
getting 'integer optimization' essentially for free; it
is fair to say that a large fraction of cases where we
can solve problems in integer optimization easily are
because the problems are actually network flow problems
or closely related. Also this subject generalizes in the
topic of 'integral polyhedra'.
Exercise (war story): There are n signals and two
satellites, A and B. Satellite A is in the sky, and
satellite B is being planned. There is an n x n matrix X
= [x(i,j)] where x(i,j) is the angle (in degrees) in the
sky between the two satellites where interference will
begin if on satellite B signal i is assigned to channel
j. Now, assign the n signals to the n channels of
satellite B so that the largest angle used is as small as
possible. Find a solution in terms of a 'bottleneck'
assignment problem. Or, have a network of arcs from
signals to channels. An 'assignment' of signal i to
channel j is a flow of unit 1 on the arc from signal i to
channel j. Guess at the crucial angle; assign cost 1 per
unit of flow for all arcs with angle less than this
critical angle and 0 for the rest, and solve the min cost
flow problem for total flow amount n and with no more
than 1 unit of flow on each arc. If the total cost is
positive, then guess a larger angle; else guess a smaller
one. Do a binary search on the size of the angle,
selecting the angles to be searched from matrix X.
Observe that the flow problem is linear programming.
Someone, then, takes this solution and drops the problem
into their favorite integer linear programming package
and reports very fast execution. Question: Why did
their favorite integer optimization package give such
fast results?
Reasons to write your own code: (1) Have software that is
small -- don't have to drag in some huge package just for your
much more narrowly focused problem; (2) have software you own
and can distribute and/or sell (modulo any restrictions on the
published information) without getting 'run-time' licenses
from third parties; (3) have software appropriate for your
problems, without a lot of complexity you do not need; (4)
have software you can tune for performance for your particular
problems (there are some tuning issues in the network simplex
algorithm); (5) have software you thoroughly understand; (6)
save money; and, best of all, (7) possibly make money!
There are other alternatives:
(1) Polynomial Algorithm. Since a polynomial algorithm
for network flows is available, you might want to
use it (the simplex algorithm may still be better in
various respects). One source is Bertsekas above.
Another is:
J. B. Orlin, "A Faster Strongly Polynomial
Minimum Cost Flow Algorithm," 'Proceedings of
the 20th ACM Symposium on Theory of Computing',
ACM Press, 1988, pp. 377-387.
(2) The code from the Bertsekas reference has been
available on diskette for $25 as RELAX-IV.
(3) Given your location in TX, you should consider
J. L. Kennington and R. V. Helgason,
'Algorithms for Network Programming', ISBN
0-471-06016-X, Wiley-Interscience, 1980.
and some associated software NETFLO. Of course,
those authors are at SMU. Also at SMU, you may want
to ask R. Barr.
(4) There is the package NETFLOW for network
optimization. Consider
http://www-fp.mcs.anl.gov/
or
ftp://dimacs.rutgers.edu
(5) There is FCNO (FORTRAN Codes for Network
Optimization). Consider
ftp://ftp.bilkent.edu.tr
The above five are just short extractions from my notes; some
of the URLs may have changed. A good Google search may show
more. You should be able to get some Fortran or C code for
min cost network flows for free or nearly so.
For your original question, "Topology to LP converter",
basically the 'topology' is all a network simplex algorithm
will want as input -- no additional 'conversion' required!
For such things, the most difficult parts are (1)
understanding optimization (e.g., as above), (2) finding what
you need from optimization (e.g., essentially just the network
simplex algorithm), (3) getting some suitable software (e.g.,
from alternatives mentioned above), (4) getting the software
running (compiled, linked, etc.), and (5) getting the software
running correctly on some toy problem, say, a network with
three nodes and five arcs. After that, the rest is typically
easier, shorter, and more fun!
And, really, you don't need AMPL or MPS!
Go for it!
Norman B. Waite, Ph.D.
Founder
Network Architectonics
9 Fox Run
Wappingers Falls, NY 12590
nbwaite@attglobal.net
845-227-7821
-------
The MPLS-OPS Mailing List
Subscribe/Unsubscribe: http://www.mplsrc.com/mplsops.shtml
Archive: http://www.mplsrc.com/mpls-ops_archive.shtml
|
|