sci.op-research

mahnam wrote:
> Hi
>
> I have written a GAMS code for solving an MIP. I have been using CPLEX
> to solve it. The code works for small-size problems (n=7). But as the
> number of binary variables increases (e.g. for n=15, 225 binary
> variables) running the code takes a long time to solve it. I have
> brought my code in the following. The model is a scheduling problem
> with considering release time and idle insert.
>
> 1- Can somebody help me with a suggestion for solving this problem.
> 2- Lagrangian Relaxation would be useful for it.
> 3- Does CPLEX provide an implementation of the Langrangian Relaxation
> or ...
> 4- Are there any C/C++ implementation of these techniques that I can
> plug in to my existing C++ code.
>
> Thanks
> Mehdi Mahnam
>
> Jobs i,j=1,2,...,n
> Binary variable x(i,j) means job i precedes job j
> Positive variables Emax, Tmax, s(i)
> M= large number like 9999
> Parameters
> p(i) processing time of job i
> r(i) release time of job i
> d(i) due date of job i
>
> objective.. Z=e=Emax+Tmax;
> S1(i).. s(i)=g=r(i);
> S2(i,j)$(ord(i)<>ord(j)).. s(j)=g=(s(i)+p(i)-(M*(1-x(i,j))));
> L1(i).. x(i,i)=e=0;
> L2(i,j)$(ord(i)<>ord(j)).. x(i,j)+x(j,i)=e=1;
> Earliness(i).. Emax=g=d(i)-s(i)-p(i);
> Tardiness(i).. Tmax=g=s(i)+p(i)-d(i);

This problem is of course NP-hard, and it is typical that solution times
blow up exponentially as problem size increases. I've tried a variation
of Benders Decomposition on somewhat similar problems; sometimes it
works very well, sometimes it bogs down completely. One of the problems
with this type of formulation is that you have to use a relatively large
value of M (roughly equal to the worst-case makespan) to be safe. The
Benders approach avoids M. You can find a good description in

@ARTICLE{codato:2006,
author = {Gianni Codato and Matteo Fischetti},
title = {Combinatorial {B}enders' Cuts for Mixed-Integer Linear
Programming},
journal = {Operations Research},
year = {2006},
volume = {54},
pages = {756-766},
number = {4}
}

CPLEX does not provide an implementation of any sort of relaxation or
decomposition directly.

/Paul