Using CPLEX to solve a large manufacturing problem.

Take two

Hi

I have a real-life large scale scheduling problem that can be
formulated as an MIP. I'd like to get an idea as to whether CPLEX can
handle this size and type of problem and what, if anything, I can do
to reduce expected solution times.

Basically I have 340 bins containing roughly 30 items each that are
sorted within each bin. Items from each bin have to removed in the
correct sequence, ie item i+1 of bin p is only removed after item i
etc. 30 time periods, items are chosen from the bins to make 2
products. The making of the products by mixing of items from the bins
in each time period must satisfy 12 very strict grade constraints that
must be correct to 3 decimal places. Weights of each of the items and
their constituent parts for mixing follow no rules (except of course
the sum of parts equals the whole) and may essentially be considered
as random positive integers having values up to 10 billion. There
are also assorted capacity constraints, bounds on how much product
must be made per period etc.

Let binary variable x_{ij} equal one if item i is removed in period j
Let y_{ij} be the proportion of item i removed in period j that is
used to make product 1.

then I have:

340*30*30*2 = 612,000 variables

30*2*12*2 = 1440 mixing constraints, with both lower and upper bounds.
capacity constraints

340*30 = 10,200 constraints specifying an item is only removed once
340*(30-1)*(30-1) = 285,940 precedence constraints
340*30*30 = 306,000 constraints of the form y_{ij}<=x_{ij}

At this stage I'm just interested in solving the LP relaxation. I
figure I'll solved the problem having the 612,000 variables and 1440
mixing constraints and capacity constraints first using a barrier
method then add other constraints as they're found to be violated in a
cutting phase using the dual solver .

the coefficients and density of the mixing and capacity
constraints could cause numerical problems. I guess I'm looking for
some anecdotal evidence that CPLEX can be expected to solve an LP like
this in a reasonable amount of time. If this is the case then the
problem also has an extra property that items can only be removed from
around 8% of the bins in each period and I might be able to solve the
problem, or significantly improve the relaxation, using a hybrid
method. But I certainly don't want to set the problem up and have
CPLEX grind away without giving me anything. Note constraint
programming has been tried for this problem before without success

A parallel version of CPLEX would obviously help. I'd also like to
know what hardware others are using, or know is available, to solve
these large difficult problems. Can I hire time on workstations or
supercomputers to solve the problem?

All help and suggestions much appreciated!

thanks

Stephen

Hi

I have a real-life large scale scheduling problem that can be
formulated as an MIP. I'd like to get an idea as to whether CPLEX can
handle this size and type of problem and what, if anything, I can do
to reduce expected solution times.

Basically I have 340 bins containing roughly 30 items each that are
sorted within each bin. Items from each bin have to removed in the
correct sequence, ie item i+1 of bin p is only removed after item i
etc. 30 time periods, items are chosen from the bins to make 2
products. The making of the products by mixing of items from the bins
in each time period must satisfy 12 very strict grade constraints that
must be correct to 3 decimal places. Weights of each of the items and
their constituent parts for mixing follow no rules (except of course
the sum of parts equals the whole) and may essentially be considered
as random positive integers having values up to 10 billion. There
are also assorted capacity constraints, bounds on how much product
must be made per period etc.

If binary variable x_{ij} is one if item i is removed in period j,
then I have:

340*30*30*2 = 612,000 variables

30*2*12*2 = 1440 mixing constraints, with both lower and upper bounds.
capacity constraints
340*30 = 10,200 constraints specifying an item is only removed once
340*(30-1)*(30-1) = 285,940 precedence constraints

At this stage I'm just interested in solving the LP relaxation. I
figure I'll solved the problem having the 612,000 variables and 1440
mixing constraints and capacity constraints first using a barrier
method then add other constraints as they're found to be violated in a
cutting phase using the dual solver .

the coefficients and density of the mixing and capacity
constraints could cause numerical problems. I guess I'm looking for
some anecdotal evidence that CPLEX can be expected to solve an LP like
this in a reasonable amount of time. If this is the case then the
problem also has an extra property that items can only be removed from
around 8% of the bins in each period and I might be able to solve the
problem, or significantly improve the relaxation, using a hybrid
method. But I certainly don't want to set the problem up and have
CPLEX grind away without giving me anything. Note constraint
programming has been tried for this problem before without success

A parallel version of CPLEX would obviously help. I'd also like to
know what hardware others are using, or know is available, to solve
these large difficult problems. Can I hire time on workstations or
supercomputers to solve the problem?

All help and suggestions much appreciated!

thanks

Stephen