The MPLS-OPS Archive

[Hani El Sakkout <hani.el-sakkout@parc-technologies.com>]

The discussion's moved offline in the interest of your mailboxes.  If you're
interested in following, please let me or Norman know.

Hani

-----Original Message-----
From: nbwaite@attglobal.net
To: mpls-ops@mplsrc.com
Sent: 30/11/03 04:34
Subject: RE: [MPLS-OPS]: CR algorithm

Hani,

Glad to go offline for a more technical discussion.

For your:

>    1) Integer programming (IP).
>
>    IP was created a specific way to model and solve certain
>    classes of NP-complete problems using LP solvers.  IP
>    makes the restrictive assumptions that all the problem
>    "disjuncts" are captured by the integrality constraint
>    (e.g. integer(X)).  Also, there is a problem modeling and
>    solving non-linear constraints and objective criteria on
>    continuous variables (e.g. P*Q*R = Z). These restrictions
>    make it difficult to model well many NP-Complete routing
>    problems (when written on paper, the model is not easy to
>    understand, and when used to model the problem within a
>    program, scalability is usually an issue, as measured by
>    numbers of variables and constraints).
>
>    However, LP and IP as modeling languages and classes of
>    solver deal very well with certain types of routing
>    sub-problem, especially when coupled with "column
>    generation".  That's the reason we do have a relationship
>    with CPLEX, among others, and we integrate various LP/MIP
>    solvers including CPLEX into our hybridization platform.

it might be good for other readers of this forum to see where
we are giving different descriptions.

For a definition of 'mixed integer optimization' ('integer
programming'), I would say that we are given

     positive integers m, n, and p,

     m column row vector c,

     p column row vector d,

     m x n matrix A,

     m x p matrix B,

     m row column vector b,

and asked for

     n row column vector x and

     p row column vector y

so that the 'objective function'

     cx + dy

is as small as possible while

     Ax + By = b

(where the products are matrix products) and all the
components of x and y are >= 0 and all the components of y are
integers.  'Integer' optimization is the same except we do not
have c, A, and x.  'Linear optimization' is the same except we
do not have d, B or y.

The long standard 'shorthand' description is:  Find x, y to
solve

          min  cx + dy

     subject to

               Ax + By = b
               x, y >= 0
               y integer

Next -- and this is a huge step -- I would include in 'mixed
integer optimization' all problems that can be put into the
shorthand form above.  For example, the 'traveling salesman
problem' gives us some n cities and asks that we find a route
from city 1 that visits each of the other n - 1 cities exactly
once and returns to city 1 and has least total travel
distance.  As is now known (but not immediately obvious), this
problem is integer optimization.  Indeed, in the theory of
NP-completeness, as in, say,

     Michael R. Garey and David S. Johnson, 'Computers and
     Intractability:  A Guide to the Theory of
     NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San
     Francisco, 1979.

we learn that there is some huge collection of problems that
are also mixed integer optimization.  This discovery was a
major surprise in the research.  Moreover, we discover that
all the problems in the class of NP-complete where 'NP'
abbreviates 'non-deterministic polynomial' are mixed integer
optimization.

So, this would be my definition of mixed integer optimization.

This definition does not require that all the problems be
posed or handled only in the shorthand description above.
E.g., we regard the traveling salesman problem as integer
optimization without writing out the matrices in the shorthand
description.  In particular, we have said nothing about
'modeling'.

Further, this definition says nothing about how we might get
solutions, make approximations, etc.  In particular, the
shorthand description need not be part of getting solutions.
We have said nothing about 'solvers' or any of the methods
they might use.  E.g., for traveling salesman problems in
finite dimensional Euclidean spaces, we can start with just
the coordinates of the n cities.  For a solution, we can start
by finding a spanning tree of these cities.  For an
approximate solution, we can do a depth-first traversal of
this tree but without visiting any cities more than once.  As
we know from, say,

     Richard M. Karp, "The Probabilistic Analysis of Some
     Combinatorial Search Algorithms," pages 1-19, 'Algorithms
     and Complexity:  New Directions and Recent Results',
     edited by J. F. Traub, Academic Press, New York, 1976.

this simple approach has some remarkably good properties.

You are correct that for large and complicated problems in
practice the shorthand description is often clumsy.  The
typing alone, say, in D. Knuth's TeX, can be challenging.
It's easy to run short of letters of the alphabet for
mathematical symbols, etc.

This description of mixed integer optimization has an
important point for this forum:  It is known that commonly
problems in the design and operation of digital communications
networks are in the class NP-complete.  It is known from
experience that usually large practical NP-complete problems
are challenging to solve but have solutions valuable in
practice.  Thus, in the design and operation of digital
communications networks, either the communications industry
takes these NP-complete problems seriously or must waste a
significant fraction of what it spends on network growth and
operations -- one or the other, no third choices.  As the
theory shows, these NP-complete problems are necessarily also
problems in mixed integer optimization.  Moreover, the most
powerful means of attacking such NP-complete problems are the
techniques from the field of integer optimization.

For this important point, whether we write these NP-complete
problems in network design and operations explicitly in the
shorthand form above is not very relevant.

You mentioned nonlinear relationships:  My definition of mixed
integer optimization assumes linearity, both in cx + dy and in
the Ax + By = b.  There is a bag of tricks that often permits
handling some nonlinear relationships well within integer
optimization or even linear optimization.  Further, many cases
of nonlinearity are convexity (quasi-convexity,
pseudo-convexity) that can be handled reasonably well within
linearity.  If some problem seems at first glance to have some
nonlinear relationships but we are told, somehow, that the
problem really is in the class NP-complete, then we know from
NP-completeness theory that the problem can be written as
mixed integer optimization -- somehow.  Finding how to do this
may be challenging; we can question if we want or need to do
it.  Net, it is not always clear how much difficulty some
nonlinear relationships provide.  My view is that in practice,
usually nonlinear relationships are not particularly
troubling.

Still, if nothing can be done with linearity, then we could
have nonlinear integer optimization, and that is a different
subject.

You mentioned modeling:  For that, we should back off a bit
and consider the practical context.  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 in optimization, 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).

With this approach, we start with a real problem and end up
with a real answer.  In the middle we exploit some
mathematics, optimization, software, and computing, and this
work in the middle can help us get a better real answer for
the real problem.

When we do this work, we start with the real problem.  We need
to describe this problem in its aspects relevant to our
mathematical work.  Here we are starting on the 'modeling'.
There is no royal road here.  We need to be clear and precise,
both within our own work and in our documentation for others,
but otherwise our techniques and tools are very broad and
certainly not fixed.  In particular, we are not limited to
particular software packages (e.g., AMPL), and integer
optimization is not a core part of our 'modeling methodology'.

For more in modeling, to get a mathematical problem we can
solve, sometimes we have to be clever, include details from
the real problem in ways that keep us faithful to the real
problem, will let our results be close to the real answer
needed, and will still give us a mathematical problem we can
handle.  For example, in scheduling the fleet at FedEx, which
was my start in such things, one question was splitting the
package load at some one city between two airplanes.
Intuitively we have to suspect that such splitting should
rarely be advantageous.  Also, permitting such splitting could
enormously complicate the work in the mathematics,
optimization, software, and computing.  So, for a first-cut,
we just looked for schedules without such splitting.

Hopefully these discussions will help the MPLS community
better understand optimization.

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

-------
The MPLS-OPS Mailing List
Subscribe/Unsubscribe:  http://www.mplsrc.com/mplsops.shtml
Archive: http://www.mplsrc.com/mpls-ops_archive.shtml