Cutting Stock Problem : Mixed Integer Programming

Question

I am asked to solve the following problem:

The problem:

You were asked to repair a farm house with sheets of plywood.

• You were given thirty sheets of plywood. (each size = 10ft x 10ft)

• The house requires 20 circles (radius = 2.5ft ) and 15 rectangles (size = 6ft x 4ft)

• It costs 20 dollars to cut a circle and 15 dollars to cut a rectange. And there are three ways to cut the sheets as shown below:

(I set these into x,y,z: numbers of sheets cut in the way)

• You can also buy 1 single circle with 45 dollars and 1 rectangle with 30 dollars.

• You CANNOT waste more than 30% of the material. (Assuming total unused area <= 30%)

Here is how I solve the problem:

$x,y,z$ - numbers of sheets cut in the ways shown above

Objective function:

$M = 80x + 60y + 55z \tag{1}$

Constraints:

$$4x + 2z \le 20 \tag{2}$$ $$4y + z \le 15 \tag{3}$$ $$x + y + z \le 30 \tag{4}$$ $$0.215x + 0.04y + 0.367z \le 0.3(x+y+z) \tag{5}$$

It seems that I am getting all zero but I cannot figure out how to set the constraints.

I am asked to solve this with ortools in Python.

But it doesn't make any sense to do it with the incorrect equations.

Answer 1

Economically speaking, if there is no cost of reprogramming your cutter (be it a CNC machine or a bearded handyman), there is no reason to go on and cut out all four rectangles from the next plywood sheet, if you only need one more.

In this realistic scenario, you need a bit more control variables, than specified in the first attempt: 12 vs 3.

If we allow for more variety in possible cuts we have the following control variables:

• $x_i$ - number of plywood sheets out of which we only cut out $i=1,..4$ circles.
  • the cost is $\sum_{i=1}^{4} 20i x_i$
  • wasted surface is $100 - 25\frac{\pi}{4}i $ per sheet
• $y_i$ - number of plywood sheets out of which we only cut out $i=1,..4$ rectangles
  • the cost is $\sum_{i=1}^{4} 15i y_i$
  • wasted surface is $100 - 24i$ per sheet
• $z_i$ - number of plywood sheets out of which we cut out a single rectangle and $i=1,2$ circles.
  • the cost is $\sum_{i=1}^{2} (15+20i)z_i$
  • wasted surface is $76 - 25\frac{\pi}{4}i $ per sheet
• $q$ - number of circular shapes we purchase additionally
  • the cost is $45 q$
• $r$ - number of rectangular shapes we purchase additionally
  • the cost is $30 r$

The total cost is given by

$$ M = \sum_{i=1}^{4} 20i x_i + \sum_{i=1}^{4} 15i y_i + \sum_{i=1}^{2} (15+20i)z_i + 45 q + 30 r,$$

the total number of plywood sheets used is

$$ \sum_{i=1}^{4} (x_i+ y_i) + \sum_{i=1}^{2} z_i \leq 30,$$

and total unused area is

$$ \sum_{i=1}^{4} (100 - 25\frac{\pi}{4}i) x_i + \sum_{i=1}^{4} (100 - 24i) y_i + \sum_{i=1}^{2} (76 - 25\frac{\pi}{4}i)z_i \leq 30 \left( \sum_{i=1}^{4} (x_i+ y_i) + \sum_{i=1}^{2} z_i\right).$$

The constraints regarding the required number of shapes are:

$$ \sum_{i=1}^{4} i x_i + \sum_{i=1}^{2} i z_i + q\geq 20$$ $$ \sum_{i=1}^{4} i y_i + \sum_{i=1}^{2} z_i + r\geq 15 $$

Allowing for more flexible cuts, you can reduce the cost from 640 ($x=5, y=4$) to 625 ($x_4=5, y_4=3, y_3=1$).

Answer 2

Your objective function doesn't include the cost of buying singles, so you are only minimizing the cost of doing cuts, not the total cost to acquire 20 circles and 15 rectangles (so of course, making no cuts at all gives you the minimal solution). For any potential x,y,z solution point, you will actually need to buy 20-(4x+2z) single circles at 45 each and 15-(4y+z) single rectangles at 30 each. If I've done my arithmetic correctly, the objective function should be 1350-100x-60y-65z.