The MPLS-OPS Archive

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

Norman, 

Perhaps this discussion is getting too algorithmic for this forum, but
anyway here's some feedback.  I advise non-algorithmic people to ignore my
email !

(Norman, please feel free to email me if you'd like to continue this
discussion directly - I think it could be very useful for us to have a more
technical discussion).

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.



2) Other Solvers 

There are a number of other solver categories that are at least as important
as IP solvers for network routing.  Two other well known solver classes are
consistency methods, and local search.  Consistency solvers greatly improve
algorithm efficiency when the problem has disjunctive constraints.  Local
search (LS) solvers such as GA's and simulated annealing are also a critical
component inside many hybrid algorithms.  BTW it's worth noting that it's
possible to build efficient "Sat-complete" hybrids containing a core LS
module, i.e. hybrids that guarantee to generate solutions or prove none
exist; while "opt-complete" hybrids based on LS additionally guarantee to
generate an optimal solution and prove optimality.  

Best regards, 

Hani 
Parc Technologies 



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

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

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