[AMPL 2594] Re: Running time - ILP

On Jun 13, 5:36 pm, ankit <electronics.an...@...> wrote:
>
> I am using CPLEX to solve ILP, which consists of 40 constraints.

With an ILP, it's typically the number of integer variables, rather
than the number of constraints, that drives execution time.  (That's
an oversimplification; the structure of the constraints also has a lot
to do with it.)

> Solving ILP in cplex, even for a small input to the problem, is taking
> very long time. Is there any other approach to solve the ILP by which
> i can reduce the running time?
>

The short answer is "maybe".  The long answer involves years of study
of ILP models, copious practice, and periodic sacrifices to the Gods
of Optimization.

For some problems, there are multiple valid formulations, and one
formulation may solve much faster than another.  Changing the
formulation is possible within AMPL (assuming you can think of a
better formulation). Adding seemingly redundant constraints sometimes
helps (if they are redundant in the ILP but tighten the LP
relaxation).

Changing solver parameters can also help with some models.  CPLEX's
default settings work pretty well on most problems, but on any
specific problem you may be able to improve performance by tweaking
the parameters.  The documentation for the AMPL/CPLEX combination
should list CPLEX-specific parameters and explain how to change them
in AMPL.

For some problems, there are better algorithmic approaches (Benders
decomposition, Lagrangean relaxation, ...) than simple off-the-shelf
branch-and-cut.  This is something you cannot do easily in AMPL,
although it is possible to script some "master-slave" approaches in
AMPL.  For particularly difficult problems, you may have to write your
own code using one of the APIs (C, C++, Java, C#) to the CPLEX
library.

Unfortunately, there is no one-size-fits-all answer for speeding up
ILPs.  If there were, it would already be built into AMPL or CPLEX.

/Paul
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To post to this group, send email to ampl@...
To unsubscribe from this group, send email to ampl+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/ampl?hl=en
-~----------~----~----~----~------~----~------~--~---