sci.op-research

On Feb 18, 2:46 am, 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

One problem is your use of a "large" number, You should use a value of
M that is as small as you can get. For example, in your problem no
start time can exceed the sum of all the processing times, so the
total of all processing times would be a good M value to use. Using an
un-neccessarily large M can lead to serious problems. I am surprised
your textbook or your lecture notes did not warn you about this.

Aside from that, the scheduling problem can grow difficult very
quickly. For example, in the job-shop scheduling literature there was
a 10-job, 10-machine problem that defeated the best algorithms on the
largest, fastest computers for many years. I believe the problem has
finally been solved to provable optimality, but it took about 20 years
or more to do it (NOT 20 yrs CPU time; just 20 years of different
people trying). Often, people /avoid/ standard MIP formulations of
scheduling problems for just the reason you are finding; instead, they
develop special-purpose methods for separate problems, often using
known structural results about the solution to speed up the search
process. Typically, a straight MIP formulation will not know anything
about such structural properties, so will spend most of its time
searching over useless portions of the solution space.

R.G. Vickson



> 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);