Problem SteelMillSlab

From CSPLib (Problem 038):. ``Steel is produced by casting molten iron into slabs. A steel mill can produce a finite number of slab sizes. An order has two properties, a colour corresponding to the route required through the steel mill, and a weight. Given a set of orders, the problem is to assign the orders to slabs, the number and size of which are also to be determined, such that the total weight of steel produced is minimised. This assignment is subject to two further constraints:

• colour constraints: each slab can contain at most p colours (p is usually 2);
• capacity constraints: the total weight of orders assigned to a slab cannot exceed the slab capacity. The colour constraints arise because it is expensive to cut up slabs in order to send them to different parts of the mill.’’

Slabbing and Blooming Mills. Image from commons.wikimedia.org

To build a COP (Constraint Optimization Problem) model, we need first to import the library PyCSP$^3$:

from pycsp3 import *

Then, we need some data. Here, we consider that we have 6 sizes of slabs (including 0), and 20 orders whose colors ans sizes are given.

slabSizes = [0, 7, 12, 15, 18, 22]
colors= [0, 1, 2, 3, 1, 0, 3, 1, 2, 1, 1, 0, 2, 1, 3, 3, 0, 2, 2, 1]
sizes= [4, 12, 9, 5, 8, 3, 3, 4, 7, 7, 3, 2, 2, 8, 5, 7, 4, 7, 5, 7]


nOrders, nColors = len(colors), len(set(colors))
nSlabs, slabSizeLimit = nOrders, max(slabSizes) + 1

It will be useful to know the gap between each possible required size s and the closest slab with a size greater than s. This is something we will use when expressing the objective.

gaps = cp_array(min(c - s for c in slabSizes if c >= s) for s in range(slabSizeLimit))

Note that we need to call cp_array() here on the list gaps (to specialize its type), because of the expression we will write later when posting the objective.

We can display the computed gaps:

print(gaps)

[0, 6, 5, 4, 3, 2, 1, 0, 4, 3, 2, 1, 0, 2, 1, 0, 2, 1, 0, 3, 2, 1, 0]

The two things we need to know are: which slab (type) is used for dealing with an order, and what is the part (load) used for each slab. This is why we introduce two arrays of variables $x$ and $y$.

# x[k] is the slab for the kth order
x = VarArray(size=nOrders, dom=range(nSlabs))

# y[i] is the size (load) of the ith slab
y = VarArray(size=nSlabs, dom=range(slabSizeLimit))

We can display the structure of the array, as well as the domain of the first variable (note that all variables have the same domain).

print("Array x: ", x)
print("Domain of any variable in x: ", x[0].dom)

print("Array y: ", y)
print("Domain of any variable in y: ", y[0].dom)

Array x:  [x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17], x[18], x[19]]
Domain of any variable in x:  0..19
Array y:  [y[0], y[1], y[2], y[3], y[4], y[5], y[6], y[7], y[8], y[9], y[10], y[11], y[12], y[13], y[14], y[15], y[16], y[17], y[18], y[19]]
Domain of any variable in y:  0..22

To start, we need to impose the colour constraints. Note that Exist is equivalent to a constraint Count, ensuring that at least one elment evaluates to True.

satisfy(
    # each slab can contain at most 2 colors
    Sum(Exist(x[k] == i for k in range(nOrders) if colors[k] == c) for c in range(nColors)) <= 2 
       for i in range(nSlabs)
);

Note that Exist corresponds to a global constraint Count being satisfied iff at least one involved term (variable or tree epression) is true (i.e., equal to 1). We have Exist(x[k] == i for k in range(nOrders) if colors[k] == c) which is equivalent to Count(x[k] == i for k in range(nOrders) if colors[k] == c, value=1) >= 1

Interestingly, by calling the function solve(), we can check that the problem is satisfiable (SAT). We can also display the found solution. Here, we call the function values() that collects the values assigned to a specified list of variables.

if solve() is SAT:
    print("x:", values(x))
    print("y:", values(y))

x: [0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0]
y: [*, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *]

The interested reader will be able to check that for the two slabs 0 and 1, at most two colours are used. However, nothing concerns the loads of slabs (this is why we have *).

To compute loads of slabs, we just need a constraint BinPacking:

satisfy(
    # computing loads of slabs
    BinPacking(x, sizes=sizes, loads=y)
);

Let us run again the solver, while computing the wasted gaps:

if solve() is SAT:
    print("x:", values(x))
    print("y:", values(y))
    print(f"waste: {sum(gaps[value(y[i])] for i in range(nSlabs))}")

x: [0, 0, 1, 1, 2, 0, 1, 2, 2, 3, 0, 3, 1, 3, 4, 4, 3, 4, 5, 5]
y: [22, 19, 19, 21, 19, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
waste: 10

This time, we have a solution with 6 slabs (numbered from 0 to 5). However, the waste is 10.

The last thing to do is to post the objective, so as to reduce the waste:

minimize(
    # minimizing total weight of steel produces
    Sum(gaps[y[i]] for i in range(nSlabs))
);

We can run the solver, with this optimization task. Note that we need to check that the status returned by the solver is now OPTIMUM.

if solve() is OPTIMUM:
    print("x: ", values(x))
    print("y: ", values(y))
    print(f"objective value: {bound()}")

x:  [0, 0, 9, 1, 1, 0, 5, 2, 2, 4, 0, 9, 5, 3, 1, 5, 3, 9, 4, 2]
y:  [22, 18, 18, 12, 12, 12, 0, 0, 0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
objective value: 0

Great! We have 0 waste.

However, it seems that we have a lot of symmetries concerning the way slabs are numbered. This is why we propose to post a constraint Precedence.

satisfy(
    # tag(symmetry-breaking)
    Precedence(x)
);

Let us run again the solver, and let us observe the role of Precedence:

if solve() is OPTIMUM:
    print("x: ", values(x))
    print("y: ", values(y))
    print(f"objective value: {bound()}")

x:  [0, 0, 1, 1, 2, 0, 1, 2, 3, 3, 0, 4, 4, 3, 1, 5, 4, 4, 5, 6]
y:  [22, 22, 12, 22, 15, 12, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
objective value: 0

Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line).

from pycsp3 import *

slabSizes, orders = data
colors, sizes = zip(*orders)
nOrders, nColors = len(orders), len(set(colors))
nSlabs, slabSizeLimit = nOrders, max(slabSizes) + 1

# gaps between each possible required size s and the closest slab with a size greater than s
gaps = cp_array(min(c - s for c in slabSizes if c >= s) for s in range(slabSizeLimit))

# x[k] is the slab for the kth order
x = VarArray(size=nOrders, dom=range(nSlabs))

# y[i] is the size (load) of the ith slab
y = VarArray(size=nSlabs, dom=range(slabSizeLimit))

satisfy(
    # each slab can contain at most 2 colors
    [Sum(Exist(x[k] == i for k in range(nOrders) if colors[k] == c) for c in range(nColors)) <= 2 
       for i in range(nSlabs)],

    # computing loads of slabs
    BinPacking(x, sizes=sizes, loads=y),

    # tag(symmetry-breaking)
    Precedence(x)
)

minimize(
    # minimizing total weight of steel produces
    Sum(gaps[y[i]] for i in range(nSlabs))
)