[AMPL 2084] Using feasible solutions from heuristic to accerlate the computation of MILP?

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[AMPL 2084] Using feasible solutions from heuristic to accerlate the computation of MILP?

Wenda Ni

Dear all,

We come to the idea of using the heuristic to get the good-enough
feasible solutions (not the optimal) as the initial solutions for AMPL/
CPLEX. We are wondering if such methods are efficient for CPLEX to
solve the mixed integer linear problems, as in the AMPL book (pp. 149
of the book version published in 1993) it is said that the default
values of the variables are effective for the non-linear model.

We are eager to get more information on such approaches, which we
donot find much literature at this moment.


Regards,


Wenda

Research interests: survivabiilty, service differentiation, and
2-layer traffic engineering in backbone networks

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

Reply | Threaded
Open this post in threaded view
|

[AMPL 2087] Re: Using feasible solutions from heuristic to accerlate the computation of MILP?

Paul A. Rubin



On Nov 18, 8:33 am, Wenda <[hidden email]> wrote:

> Dear all,
>
> We come to the idea of using the heuristic to get the good-enough
> feasible solutions (not the optimal) as the initial solutions for AMPL/
> CPLEX. We are wondering if such methods are efficient for CPLEX to
> solve the mixed integer linear problems, as in the AMPL book (pp. 149
> of the book version published in 1993) it is said that the default
> values of the variables are effective for the non-linear model.
>
> We are eager to get more information on such approaches, which we
> donot find much literature at this moment.
>

CPLEX can utilize a good feasible solution to a MIP model, and it will
frequently accelerate the solution process (by allowing CPLEX to prune
nodes earlier than it otherwise would).  However, MIP models are
fickle creatures, so the value of good starting solution varies.
Sometimes it helps tremendously, sometimes it does not help at all.
If CPLEX with no initial incumbent finds a feasible solution quickly
that is as good as or better than what your heuristic finds, the
heuristic probably will not help.  If CPLEX takes a long time to find
a solution as good as what the heuristic finds, it probably will
help.  Note the use of "probably"; there are no guarantees when
dealing with MIPs.

/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 [hidden email]
To unsubscribe from this group, send email to [hidden email]
For more options, visit this group at http://groups.google.com/group/ampl?hl=en
-~----------~----~----~----~------~----~------~--~---