Cutting Stock Problem

[ccorcos]

Hey there, I'm trying to figure out how to use this library to help me with a cutting stock problem.

I can get 96 inch boards from the store, but I need to cut:

• 21x 7 inch pieces
• 17x 76 inch pieces
• 7x 80 inch pieces

I've set up the solver in a way that I think works:

const results = solver.Solve({
    optimize: "count96",
    opType: "min",
    variables: {
        // This is the stock board
        board96: {
            count96: 1,
            length: 96,
        },
        // These are the cuts, with negative length
        board7: {
            count7: 1,
            length: -7,
        },
        board76: {
            count76: 1,
            length: -76,
        },
        board80: {
            count80: 1,
            length: -80,
        },
    },
    // All counts must be integers
    int: {
        board7: 1,
        board76: 1,
        board80: 1,
        board96: 1,
    },
    constraints: {
        // Number of boards of each size we need.
        count7: { min: 21 },
        count76: { min: 17 },
        count80: { min: 7 },
        // We should have some wood left over.
        length: { min: 0 },
    },
})

And I get a solution:

{ feasible: true,
  result: 20.82291667,
  bounded: true,
  board7: 21,
  board76: 17,
  board80: 7,
  board96: 20.82291667 }

So I need 21 boards from the store.... but how do I cut them? I've been noodling around inside solver.lastSolvedModel to try to find my answer but I can't find anything that looks relevant. Where can I find this information from the solver?

[ccorcos]

Oh wow, my program doesn't account for the fact that you can'y compose board7 out of two board96s... 20.82291667 * 96 = 17*76 + 7*80 + 21 * 7. Ugh. This is hard!

[ccorcos]

LOL this problem is NP-Hard! I still have a solution that leverages this library. I will post it once I clean it up and close the issue.

[ccorcos]

Alright, here's my code!

/**
 * Given a board of `size` and a list of `cuts` you
 * can make out of the board, how many unique ways of cutting the board
 * are there?
 */
function howManyWays(
    size: number,
    cuts: Array<number>,
    state: Array<number> = []
): Array<Array<number>> {
    return _.flatten(
        cuts.map(cut => {
            const remainder = size - cut
            if (remainder >= 0) {
                return _.uniqWith(
                    howManyWays(remainder, cuts, [...state, cut].sort()),
                    (x, y) =>
                        _.difference(x, y).length === 0 || _.difference(y, x).length === 0
                )
            } else {
                return [state]
            }
        })
    )
}

type RequiredCuts = Array<{ size: number; count: number }>
type ResultCuts = Array<{ count: number; cuts: Array<number> }>

/**
 * Given a stock side of wood you and buy, how many do I need and how do I cut it
 * in order to make enough pieces of with at the given sizes.
 */
function howToCutBoards1D(
    stockSize: number,
    requiredCuts: RequiredCuts
): ResultCuts {
    const cutSizes = requiredCuts.map(({ size }) => size)

    const waysOfCutting = howManyWays(stockSize, cutSizes)

    // Transform [1,1,2,3] into {cut1: 2, cut2: 1, cut3: 3}.
    // Each will be the different versions of cutting the stock board.
    const stockVersions = waysOfCutting.map(way => {
        const stockCut = {}
        for (const cut of cutSizes) {
            stockCut["cut" + cut] = 0
        }
        for (const cut of way) {
            stockCut["cut" + cut] = stockCut["cut" + cut] + 1
        }
        return stockCut
    })

    // Create a variable for each version with a count: 1 which we will minimize.
    const variables = stockVersions
        .map((cut, index) => ({ ["version" + index]: { ...cut, count: 1 } }))
        .reduce((acc, next) => ({ ...acc, ...next }))

    // We can't puchase part of a board, so the result but me an int, not a float.
    const ints = stockVersions
        .map((cut, index) => ({ ["version" + index]: 1 }))
        .reduce((acc, next) => ({ ...acc, ...next }))

    // Create constraints from the required cuts with a min on the count required.
    const constraints = requiredCuts
        .map(({ size, count }) => ({ ["cut" + size]: { min: count } }))
        .reduce((acc, next) => ({ ...acc, ...next }))

    // Create out model for the simplex linear programming solver.
    // https://github.com/JWally/jsLPSolver
    const model = {
        optimize: "count",
        opType: "min",
        variables: variables,
        int: ints,
        constraints: constraints,
    }

    // Run the program
    const results = solver.Solve(model)

    if (!results.feasible) {
        throw new Error("Didn't work")
    }

    const resultCuts: ResultCuts = []

    for (let i = 0; i < waysOfCutting.length; i++) {
        const number = results["version" + i]
        if (number) {
            resultCuts.push({ count: number, cuts: waysOfCutting[i] })
        }
    }

    return resultCuts
}

And using it:

howToCutBoards1D(12 * 8,  [ { size: 7, count: 21 }, { size: 76, count: 17 }, { size: 80, count: 7 } ])
> [ { count: 17, cuts: [ 7, 7, 76 ] },
  { count: 7, cuts: [ 7, 7, 80 ] } ]

[ccorcos]

Here's the model and result from this library

{ optimize: 'count',
  opType: 'min',
  variables:
   { version0: { cut7: 13, cut76: 0, cut80: 0, count: 1 },
     version1: { cut7: 2, cut76: 1, cut80: 0, count: 1 },
     version2: { cut7: 2, cut76: 0, cut80: 1, count: 1 } },
  int: { version0: 1, version1: 1, version2: 1 },
  constraints: { cut7: { min: 21 }, cut76: { min: 17 }, cut80: { min: 7 } } }
{ feasible: true,
  result: 24,
  bounded: true,
  version1: 17,
  version2: 7 }