sci.op-research

On Mon, 18 Feb 2008 08:29:30 -0500, Paul Rubin wrote:

>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.
[...]
>
>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.
>

However, ILOG had a library named Scheduler that was sitting on the
top of ILOG Solver. I don't know what is the current state of ILOG
products.

A.L.