small MIP with a very bad LP bound

[Archiver]

Dear all,

I have modeled a practical problem in transportation and my MIP models
turns out to report very disappointing results.
In 99% of the cases the convergence is achieved after at least one day
for a very small instance of size 5 when number of constraints and
variables are of O(n^4) and GAMS-CPLEX 11.0 is used to solve such
instances.

I have tried different variants of Benders decomposition which failed
mostly because the master problem rarely generated a feasible solution
adn the number of rays was high. Lagrangian relaxation is also
employed but different master problems are also hard-to-solve atleast
after a few iteration of the subgradient.

I believe all these are due to the weakness of the LP relaxation and I
do not know which method to use for solving instances of such problem.
The root node gap is usually very high and around 90% and also the
proof of the optimality some times take 95% of the computational time.
The problem is modeled using Big-M constrainst and indicator
constraints are used in GAMS to solve the model.


I appreciate any hint and looking forward to hearing from you.

regards,

--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to gamsworld@googlegroups.com
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en
-~----------~----~----~----~------~----~------~--~---

[Archiver]

Is sound as if you tried most of the tricks of the trade, so no
general comment. You might consider posting your model with one
difficult instance to the list or me personally and someone might see
another possibility to speed things up. Bus as you surely know solving
MIPs (even small one) can be a very difficult.

Regards,
Michael Bussieck - GAMSWorld Coordinator

On Dec 20, 5:43 am, "shahin.gela...@gmail.com"
wrote:
> > Dear all,
> >
> > I have modeled a practical problem in transportation and my MIP models
> > turns out to report very disappointing results.
> > In 99% of the cases the convergence is achieved after at least one day
> > for a very small instance of size 5 when number of constraints and
> > variables are of O(n^4) and GAMS-CPLEX 11.0 is used to solve such
> > instances.
> >
> > I have tried different variants of Benders decomposition which failed
> > mostly because the master problem rarely generated a feasible solution
> > adn the number of rays was high. Lagrangian relaxation is also
> > employed but different master problems are also hard-to-solve atleast
> > after a few iteration of the subgradient.
> >
> > I believe all these are due to the weakness of the LP relaxation and I
> > do not know which method to use for solving instances of such problem.
> > The root node gap is usually very high and around 90% and also the
> > proof of the optimality some times take 95% of the computational time.
> > The problem is modeled using Big-M constrainst and indicator
> > constraints are used in GAMS to solve the model.
> >
> > I appreciate any hint and looking forward to hearing from you.
> >
> > regards,
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to gamsworld@googlegroups.com
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en
-~----------~----~----~----~------~----~------~--~---

[Archiver]

Hi,

Perhaps a good alternative is using the Interger Infeasibily Path method (IIP-MINLP) see (Sorsak and Kravanja, Simultaneous MINLP synthesis of heat exchanger networks comprising different exchanger types, 2002), with a multilevel optimization, they use this method with a MINLP problem but probably is usefull in MILP too. In simple words, the method consist in using a relaxation of the binary variables using slack ones, replace this in all the constraints that have binary variables, and use a slack equation for the relaxation:

Original problem:

obj=f(x,y)
s.t.:
g(x,y)=0
h(x,y)>=0
x e R, y e {0,1}

New problem:

obj=f(x,y*) + w(s+p) -- you have to use a penalization term multiplied by a weight coefficient
s.t.:
g(x,y*)=0 -- theese are the constraints with the relaxed variable
h(x,y*)>=0
y=y*+s-p -- this is the relaxation with the slack variables

x e R, y e {0,1}.
y* e [0,1], s>=0, p>=0 -- here you define the slack and the relaxed variables


The authors indicates that you can improve the solution method using an automated way for relaxation:

- First you must solve your model considering all the binary variables equal to one (fix the variables y.fx=1), so the optimization will search for all the options (you give the possibility to all the binary variables to be true),

- The result of the optimization will give you a set of relaxed variables that are one, you must store this information hierachycally, set the corresponding binary variables to zero and solve again the problem (with this you give the oportunity to other variables to be true) and repeat this procedure

- Finally you have a hierarchycally set of feasible solutions for inicialize your solving method.

Hope this help. I can tell you that In my master thesis I had to develop a MINLP algorithm with disjunctive and this method works.


If this method don't work, you can use other ways to formulate de disjunctive problem using the Convex-Hull formulation (Sawaya, N; Grossmann, I.E.; Computational implementation of non-linear convex hull reformulation, Comp. and Chem. Engng. (2007)) instead of Big-M formulation

or trying other solvers like LogMIP, see:
http://www.logmip.ceride.gov.ar/

Hope this helps,

Best Regards!!



2008/12/22 Gamsworld Admin


Is sound as if you tried most of the tricks of the trade, so no
general comment. You might consider posting your model with one
difficult instance to the list or me personally and someone might see
another possibility to speed things up. Bus as you surely know solving
MIPs (even small one) can be a very difficult.

Regards,
Michael Bussieck - GAMSWorld Coordinator

On Dec 20, 5:43 am, "shahin.gela...@gmail.com"
wrote:
> Dear all,
>
> I have modeled a practical problem in transportation and my MIP models
> turns out to report very disappointing results.
> In 99% of the cases the convergence is achieved after at least one day
> for a very small instance of size 5 when number of constraints and
> variables are of O(n^4) and GAMS-CPLEX 11.0 is used to solve such
> instances.
>
> I have tried different variants of Benders decomposition which failed
> mostly because the master problem rarely generated a feasible solution
> adn the number of rays was high. Lagrangian relaxation is also
> employed but different master problems are also hard-to-solve atleast
> after a few iteration of the subgradient.
>
> I believe all these are due to the weakness of the LP relaxation and I
> do not know which method to use for solving instances of such problem.
> The root node gap is usually very high and around 90% and also the
> proof of the optimality some times take 95% of the computational time.
> The problem is modeled using Big-M constrainst and indicator
> constraints are used in GAMS to solve the model.
>
> I appreciate any hint and looking forward to hearing from you.
>
> regards,




--
Daniel Andrés Navia López
Ingeniero Civil Químico
Mg.Sc.Ciencias de la Ingeniería, Mención Ingeniería Química
626752875

--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to gamsworld@googlegroups.com
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en
-~----------~----~----~----~------~----~------~--~---