The MPLS-OPS Archive

[nbwaite@attglobal.net]

Hani,

For your

>    It's true that integer programming has modeling and
>    scalability limitations - it's only widely used though
>    because it's easily understood and easily applied.

I believe that you are taking my use of "integer optimization"
too narrowly.  R. Bixby on your advisory board may agree with
me that 'integer optimization' usually refers just to the
problem and not to particular statements of that problem or to
particular solution (or 'search') approaches.  Moreover, much
of the importance of NP-complete theory is in the many problem
transformations where we see problems of wide variety
equivalent to integer optimization.

With this meaning of 'integer optimization', problems in
digital communications network operations and design that are
NP-complete are necessarily also integer optimization.  Or,
again, we can draw on the core results of NP-completeness
theory and the problem transformations there.

Further, problems just in network operations where we are just
looking for flows without regard for costs are often
NP-complete and, thus, also integer optimization:  In such
problems, in the integer optimization problem, all we are
looking for is 'feasibility', but in principle finding a
feasible solution is no easier than finding an optimal
solution.

Just finding a feasible solution is sometimes regarded as
'constraint logic programming', but this, when NP-complete, is
still the same as integer optimization.  It is true that in
practice part of 'constraint logic programming' is a bit
different:  In this part, we are essentially building computer
software for a user interface, e.g., providing a convenient
way for a loading dock foreman to specify what is needed in
truck loading; after this user interface progress, what is
left to do is just integer optimization.  We now have
essentially why ILOG (with emphasis on constraint logic
programming) bought CPLEX (software for solving integer
optimization problems) and why PARC, also with a background in
constraint logic programming, has interest in CPLEX.

Usually in integer optimization, we specify the problem with
constraints of the form Ax + By = b where A and B are
matrices, x, y are vectors >= 0, and the components of y are
integers.  While we can do this, we don't have to do this;
even if we do not specify our problem in this form, we are
still working in integer optimization.

Even if we specify our problem with constraints Ax + By = b,
that still does not limit how we might get solutions.  That
is, we are not forced to start by solving a linear
optimization with the components of y permitted to be real
numbers instead of just integers and then proceed with
traditional branch and bound.  And we are not forced to drop
this formulation into software regarded as a 'solver' of
integer optimization problems,

In particular, any means at all of getting feasible solutions
can help the 'search' or branch and bound process run faster.
Among such means can be common sense, various heuristics, an
approximate formulation in terms of network flows (where often
we can get integer optimization for no extra effort beyond
linear optimization), etc.

However, if we are going to say that solving integer
optimization problems are 'search' problems, then we need
search techniques that have an extra feature:  When some
constraints of the form Ax + By = b where A and B are
matrices, x, y are vectors >= 0, and the components of y are
integers is infeasible, then the search techniques can
discover and report this fact.  In particular, 'genetic'
algorithms and 'simulated annealing' do not provide this extra
feature.  So, if genetic algorithms, etc., do find feasible
solutions, then that can be helpful but cannot tell us that we
are within 1% of the least cost network design.

In general, there is a lot to solution techniques.  Your
remarks confirm the 'most powerful' solution technique:
Select techniques to exploit the special structure of the
given class of problems.  In this way, it is common to run for
a few minutes instead of weeks or more we might get just
dropping a formulation into some software regarded as a
'solver'.

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