Cutting Stock Problem

Packing

Problem

In the Cutting Stock Problem, we must cut rectangular items of various widths and heights from large rolls (or plates) of fixed dimensions. The cutting follows a structured two-level guillotine pattern:

Bands: Items sharing the same width are grouped side by side along their height, forming horizontal bands. Each band has a fixed width (the common item width) and a total length equal to the sum of the item heights.
Rolls: Bands are then stacked vertically within a roll. The total width of bands in a roll must not exceed the roll width. Similarly, each band’s length must fit within the roll length.

The objective is to minimize the number of rolls used.

Principles learned

Use two levels of set decision variables to model a hierarchical packing structure (items into bands, bands into rolls)
Use the distinct operator with a lambda to enforce that all items in a band share the same width
Guard max over sets with a ternary (count(s) > 0 ? max(s, ...) : 0) to avoid NaN on empty sets

Data

The Cutting Stock instances provided are the A instances from the 2DPackLib. The format of the data files is as follows:

First line: number of item types
Second line: roll width, roll length
For each item type: width, height, demand

Model

The Hexaly model for the Cutting Stock Problem uses two levels of set decision variables. At the first level, for each band, we define a set variable representing the items assigned to this band. At the second level, for each roll, we define a set variable representing the bands assigned to this roll. Both levels use partition constraints to ensure that every item belongs to exactly one band, and every band belongs to exactly one roll.

Within each band, all items must share the same width. This is enforced using the distinct operator with a lambda function: distinct(bands[b], (i) => rawWidth[i]) returns the set of distinct widths in the band, and we constrain its count to be at most 1. We compute the band length as the sum of item heights using a variadic sum operator, and we constrain each band’s length to fit within the roll length. At the roll level, we compute the total width of bands using a variadic sum over the roll’s set of bands with a lambda function returning each band’s width, and we constrain it not to exceed the roll width.

The model computes a simple lower bound on the number of rolls (total item area divided by roll area) and uses hxObjectiveThreshold to stop early when this bound is reached.

Hexaly Modeler
Python
C++
C#
Java

Download

Execution: hexaly cutting_stock.hxm inFileName=instances/A1.txt [hxTimeLimit=] [solFileName=]

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
use io;

function input() {
    local usage =
        "Usage: hexaly cutting_stock.hxm "
        + "inFileName=inputFile [solFileName=outputFile] [hxTimeLimit=timeLimit]";
    if (inFileName == nil) throw usage;

    local inFile = io.openRead(inFileName);
    nbItemTypes = inFile.readInt();
    rollWidth = inFile.readInt();
    rollLength = inFile.readInt();

    // Read item types and expand by demand
    nbItems = 0;
    for [t in 0...nbItemTypes] {
        local weight = inFile.readInt();
        local length = inFile.readInt();
        local demand = inFile.readInt();
        for [i in 0...demand] {
            rawWidth[nbItems] = weight;
            rawLength[nbItems] = length;
            nbItems = nbItems + 1;
        }
    }

    nbMaxBands = nbItems;
    nbMaxRolls = nbItems;

    // Lower bound on total number of rolls: total item area / rollArea
    minNumberOfRolls =
        ceil(sum[i in 0...nbItems](rawWidth[i] * rawLength[i])
            / (rollWidth * rollLength));
}

/* Declare the optimization model */
function model() {
    // Set decisions: bands[b] represents the items assigned to band b
    bands[0...nbMaxBands] <- set(nbItems);
    // Set decisions: rolls[r] represents the bands assigned to roll r
    rolls[0...nbMaxRolls] <- set(nbMaxBands);

    // Each item must be in exactly one band, and each band in exactly one roll
    constraint partition[b in 0...nbMaxBands](bands[b]);
    constraint partition[r in 0...nbMaxRolls](rolls[r]);

    for [b in 0...nbMaxBands] {
        // Length constraint for each band
        bandLength[b] <- sum(bands[b], i => rawLength[i]);
        constraint bandLength[b] <= rollLength;

        // All items in a band must have the same width
        distinctWidths[b] <- distinct(bands[b], i => rawWidth[i]);
        constraint count(distinctWidths[b]) <= 1;

        bandWidth[b] <-
            count(bands[b]) > 0 ? max(bands[b], i => rawWidth[i]) : 0;
    }

    for [r in 0...nbMaxRolls] {
        // The roll's width is the sum of the widths of its bands
        totalWidth[r] <- sum(rolls[r], b => bandWidth[b]);
        constraint totalWidth[r] <= rollWidth;

        rollUsed[r] <- count(rolls[r]) > 0;
    }

    numberOfUsedRolls <- sum[r in 0...nbMaxRolls](rollUsed[r]);
    minimize numberOfUsedRolls;
}

/* Parametrize the solver */
function param() {
    if (hxTimeLimit == nil) hxTimeLimit = 10;

    // Stop the search if the lower threshold is reached
    hxObjectiveThreshold = minNumberOfRolls;
}

/* Write the solution */
function output() {
    if (solFileName == nil) return;
    local solFile = io.openWrite(solFileName);
    solFile.println("Number of rolls used: ", numberOfUsedRolls.value);
    solFile.println("Roll dimensions: ", rollLength, " x ", rollWidth);
    solFile.println();
    local rollIndex = 0;
    for [r in 0...nbMaxRolls] {
        if (rolls[r].value.count() == 0) continue;
        solFile.println(
            "Roll ",
            rollIndex,
            " | width: ",
            totalWidth[r].value,
            "/",
            rollWidth
        );
        for [b in rolls[r].value] {
            if (bands[b].value.count() == 0) continue;
            solFile.print(
                "  Band width=",
                bandWidth[b].value,
                " length=",
                bandLength[b].value,
                " | Items: "
            );
            for [i in bands[b].value] solFile.print(i, " ");
            solFile.println();
        }
        rollIndex = rollIndex + 1;
    }
}

Execution (Windows): set PYTHONPATH=%HX_HOME%\bin\python

python cutting_stock.py instances\A1.txt

Execution (Linux): export PYTHONPATH=/opt/hexaly_15_0/bin/python

python cutting_stock.py instances/A1.txt

# Copyright (c) Hexaly. Permission is hereby granted to use, copy,
# and modify this code for applications developed with Hexaly.
import hexaly.optimizer
import sys
import math


def read_integers(filename):
    with open(filename) as f:
        return [int(elem) for elem in f.read().split()]

def main(instance_file, str_time_limit, output_file):
    #
    # Read instance data
    #
    file_it = iter(read_integers(instance_file))

    nb_item_types = int(next(file_it))
    roll_width = int(next(file_it))
    roll_length = int(next(file_it))

    # Read item types and expand by demand
    raw_width = []
    raw_length = []
    for t in range(nb_item_types):
        width = int(next(file_it))
        length = int(next(file_it))
        demand = int(next(file_it))
        for c in range(demand):
            raw_width.append(width)
            raw_length.append(length)

    nb_items = len(raw_width)

    nb_max_bands = nb_items
    nb_max_rolls = nb_items

    # Lower bound on total number of rolls: total item area / rollArea
    total_area = sum(raw_width[i] * raw_length[i] for i in range(nb_items))
    min_number_of_rolls = int(math.ceil(total_area / (roll_width * roll_length)))
        
    with hexaly.optimizer.HexalyOptimizer() as optimizer:
        #
        # Declare the optimization model
        #
        model = optimizer.model

        # Set decisions: bands[b] represents the items assigned to band b
        bands = [model.set(nb_items) for _ in range(nb_max_bands)]
        # Set decisions: rolls[r] represents the bands assigned to roll r
        rolls = [model.set(nb_max_bands) for _ in range(nb_max_rolls)]

        # Each item must be in exactly one band, and each band in exactly one roll
        model.constraint(model.partition(bands))
        model.constraint(model.partition(rolls))

        # Create model arrays for item data
        widths = model.array(raw_width)
        lengths = model.array(raw_length)

        band_width = [None for _ in range(nb_max_bands)]
        band_length = [None for _ in range(nb_max_bands)]

        for b in range(nb_max_bands):
            # Length constraint for each band
            band_length[b] = model.sum(
                bands[b], model.lambda_function(lambda i: lengths[i])
            )
            model.constraint(band_length[b] <= roll_length)

            # All items in a band must have the same width
            distinct_widths = model.distinct(
                bands[b], model.lambda_function(lambda i: widths[i])
            )
            model.constraint(model.count(distinct_widths) <= 1)

            band_width[b] = model.iif(
                model.count(bands[b]) > 0,
                model.max(bands[b], model.lambda_function(lambda i: widths[i])),
                0,
            )

        # Create array of band width expressions for roll lambdas
        band_width_array = model.array(band_width)

        roll_used = [None for _ in range(nb_max_rolls)]
        total_width = [None for _ in range(nb_max_rolls)]

        for r in range(nb_max_rolls):
            # The roll's width is the sum of the widths of its bands
            total_width[r] = model.sum(
                rolls[r], model.lambda_function(lambda b: band_width_array[b])
            )
            model.constraint(total_width[r] <= roll_width)

            roll_used[r] = model.count(rolls[r]) > 0

        # Minimize the number of used rolls
        number_of_used_rolls = model.sum(roll_used)
        model.minimize(number_of_used_rolls)
        model.close()

        # Parameterize the optimizer
        optimizer.param.time_limit = int(str_time_limit)

        # Stop the search if the lower threshold is reached
        optimizer.param.set_objective_threshold(0, min_number_of_rolls)

        optimizer.solve()

        # Write the solution in a file
        if output_file is not None:
            with open(output_file, "w") as f:
                f.write("Number of rolls used: %d\n" % number_of_used_rolls.value)
                f.write("Roll dimensions: %d x %d\n\n" % (roll_length, roll_width))
                roll_index = 0
                for r in range(nb_max_rolls):
                    if rolls[r].value.count() == 0:
                        continue
                    f.write("Roll %d | width: %d/%d\n"
                        % (roll_index, total_width[r].value, roll_width))
                    for b in rolls[r].value:
                        if bands[b].value.count() == 0:
                            continue
                        f.write("  Band width=%d length=%d | Items: "
                            % (band_width[b].value, band_length[b].value))
                        for i in bands[b].value:
                            f.write("%d " % i)
                        f.write("\n")
                    roll_index += 1

if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Usage: python cutting_stock.py inputFile [output_file] [time_limit]")
        sys.exit(1)

    instance_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) > 2 else None
    str_time_limit = sys.argv[3] if len(sys.argv) > 3 else "10"
    main(instance_file, str_time_limit, output_file)

Compilation / Execution (Windows): cl /EHsc cutting_stock.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly15_0.lib

cutting_stock instances\A1.txt

Compilation / Execution (Linux): g++ cutting_stock.cpp -I/opt/hexaly_15_0/include -lhexaly150 -lpthread -o cutting_stock

./cutting_stock instances/A1.txt

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
#include "optimizer/hexalyoptimizer.h"
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>

using namespace hexaly;

class CuttingStock {
private:
    // Number of item types and items (expanded by demand)
    int nbItemTypes;
    int nbItems;

    // Roll dimensions
    int rollWidth;
    int rollLength;

    // Maximum number of bands and rolls
    int nbMaxBands;
    int nbMaxRolls;

    // Minimum number of rolls (lower bound)
    int minNumberOfRolls;

    // Item dimensions (expanded by demand)
    std::vector<hxint> rawWidth;
    std::vector<hxint> rawLength;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    std::vector<HxExpression> bands;
    std::vector<HxExpression> rolls;

    // Band expressions
    std::vector<HxExpression> bandWidth;
    std::vector<HxExpression> bandLength;

    // Roll expressions
    std::vector<HxExpression> rollUsed;
    std::vector<HxExpression> totalWidth;

    // Objective
    HxExpression numberOfUsedRolls;

public:
    /* Read instance data */
    void readInstance(const std::string& fileName) {
        std::ifstream infile;
        infile.exceptions(std::ifstream::failbit | std::ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> nbItemTypes;
        infile >> rollWidth;
        infile >> rollLength;

        // Read item types and expand by demand
        for (int t = 0; t < nbItemTypes; ++t) {
            int width, length, demand;
            infile >> width >> length >> demand;
            for (int c = 0; c < demand; ++c) {
                rawWidth.push_back(width);
                rawLength.push_back(length);
            }
        }

        nbItems = rawWidth.size();

        nbMaxBands = nbItems;
        nbMaxRolls = nbItems;

        // Lower bound on total number of rolls: total item area / rollArea
        double totalArea = 0;
        for (int i = 0; i < nbItems; ++i) {
            totalArea += (double)rawWidth[i] * rawLength[i];
        }
        minNumberOfRolls = (int)ceil(totalArea / ((double)rollWidth * rollLength));
    }

    void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        bands.resize(nbMaxBands);
        rolls.resize(nbMaxRolls);
        bandWidth.resize(nbMaxBands);
        bandLength.resize(nbMaxBands);
        rollUsed.resize(nbMaxRolls);
        totalWidth.resize(nbMaxRolls);

        // Set decisions: bands[b] represents the items assigned to band b
        for (int b = 0; b < nbMaxBands; ++b) {
            bands[b] = model.setVar(nbItems);
        }
        // Set decisions: rolls[r] represents the bands assigned to roll r
        for (int r = 0; r < nbMaxRolls; ++r) {
            rolls[r] = model.setVar(nbMaxBands);
        }

        // Each item must be in exactly one band, and each band in exactly one roll
        model.constraint(model.partition(bands.begin(), bands.end()));
        model.constraint(model.partition(rolls.begin(), rolls.end()));

        // Create model arrays for item data
        HxExpression widths = model.array(rawWidth.begin(), rawWidth.end());
        HxExpression lengths = model.array(rawLength.begin(), rawLength.end());

        for (int b = 0; b < nbMaxBands; ++b) {
            // Length constraint for each band
            bandLength[b] = model.sum(bands[b],
                model.createLambdaFunction([&](HxExpression i) { return lengths[i]; }));
            model.constraint(bandLength[b] <= rollLength);

            // All items in a band must have the same width
            HxExpression distinctWidths = model.distinct(bands[b],
                model.createLambdaFunction([&](HxExpression i) { return widths[i]; }));
            model.constraint(model.count(distinctWidths) <= 1);

            bandWidth[b] = model.iif(
                model.count(bands[b]) > 0,
                model.max(bands[b],
                    model.createLambdaFunction([&](HxExpression i) { return widths[i]; })),
                0);
        }

        // Create array of band width expressions for roll lambdas
        HxExpression bandWidthArray = model.array(bandWidth.begin(), bandWidth.end());

        for (int r = 0; r < nbMaxRolls; ++r) {
            // The roll's width is the sum of the widths of its bands
            totalWidth[r] = model.sum(rolls[r],
                model.createLambdaFunction([&](HxExpression b) { return bandWidthArray[b]; }));
            model.constraint(totalWidth[r] <= rollWidth);

            rollUsed[r] = model.count(rolls[r]) > 0;
        }

        // Minimize the number of used rolls
        numberOfUsedRolls = model.sum(rollUsed.begin(), rollUsed.end());
        model.minimize(numberOfUsedRolls);

        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(limit);

        // Stop the search if the lower threshold is reached
        optimizer.getParam().setObjectiveThreshold(0, (hxint)minNumberOfRolls);

        optimizer.solve();
    }

    /* Write the solution in a file */
    void writeSolution(const std::string& fileName) {
        std::ofstream outfile;
        outfile.exceptions(std::ofstream::failbit | std::ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << "Number of rolls used: " << numberOfUsedRolls.getValue() << std::endl;
        outfile << "Roll dimensions: " << rollLength << " x " << rollWidth << std::endl;
        outfile << std::endl;

        int rollIndex = 0;
        for (int r = 0; r < nbMaxRolls; ++r) {
            HxCollection rollCollection = rolls[r].getCollectionValue();
            if (rollCollection.count() == 0)
                continue;
            outfile << "Roll " << rollIndex << " | width: " << totalWidth[r].getValue() << "/"
                    << rollWidth << std::endl;
            for (int bi = 0; bi < rollCollection.count(); ++bi) {
                int b = rollCollection[bi];
                HxCollection bandCollection = bands[b].getCollectionValue();
                if (bandCollection.count() == 0)
                    continue;
                outfile << "  Band width=" << bandWidth[b].getValue()
                        << " length=" << bandLength[b].getValue() << " | Items: ";
                for (int ii = 0; ii < bandCollection.count(); ++ii) {
                    outfile << bandCollection[ii] << " ";
                }
                outfile << std::endl;
            }
            rollIndex++;
        }
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "Usage: cutting_stock inputFile [outputFile] [timeLimit]" << std::endl;
        return 1;
    }

    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "10";

    try {
        CuttingStock model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const std::exception& e) {
        std::cerr << "An error occurred: " << e.what() << std::endl;
        return 1;
    }
}

Compilation / Execution (Windows): copy %HX_HOME%\bin\Hexaly.NET.dll .

csc CuttingStock.cs /reference:Hexaly.NET.dll

CuttingStock instances\A1.txt

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using Hexaly.Optimizer;

public class CuttingStock : IDisposable
{
    // Number of item types and items (expanded by demand)
    int nbItemTypes;
    int nbItems;

    // Roll dimensions
    int rollWidth;
    int rollLength;

    // Maximum number of bands and rolls
    int nbMaxBands;
    int nbMaxRolls;

    // Minimum number of rolls (lower bound)
    int minNumberOfRolls;

    // Item dimensions (expanded by demand)
    long[] rawWidth;
    long[] rawLength;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression[] bands;
    HxExpression[] rolls;

    // Band expressions
    HxExpression[] bandWidth;
    HxExpression[] bandLength;

    // Roll expressions
    HxExpression[] rollUsed;
    HxExpression[] totalWidth;

    // Objective
    HxExpression numberOfUsedRolls;

    public CuttingStock()
    {
        optimizer = new HexalyOptimizer();
    }

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] allTokens = input.ReadToEnd().Split(
                new char[] { ' ', '\t', '\n', '\r' },
                StringSplitOptions.RemoveEmptyEntries);
            int idx = 0;
            nbItemTypes = int.Parse(allTokens[idx++]);
            rollWidth = int.Parse(allTokens[idx++]);
            rollLength = int.Parse(allTokens[idx++]);

            // Read item types and expand by demand
            List<long> widthList = new List<long>();
            List<long> lengthList = new List<long>();
            for (int t = 0; t < nbItemTypes; ++t)
            {
                int width = int.Parse(allTokens[idx++]);
                int length = int.Parse(allTokens[idx++]);
                int demand = int.Parse(allTokens[idx++]);
                for (int c = 0; c < demand; ++c)
                {
                    widthList.Add(width);
                    lengthList.Add(length);
                }
            }

            nbItems = widthList.Count;
            rawWidth = widthList.ToArray();
            rawLength = lengthList.ToArray();

            nbMaxBands = nbItems;
            nbMaxRolls = nbItems;

            // Lower bound on total number of rolls: total item area / rollArea
            long totalArea = 0;
            for (int i = 0; i < nbItems; ++i)
                totalArea += rawWidth[i] * rawLength[i];
            minNumberOfRolls = (int)Math.Ceiling((double)totalArea / ((double)rollWidth * rollLength));
        }
    }

    public void Dispose()
    {
        if (optimizer != null)
            optimizer.Dispose();
    }

    void Solve(int limit)
    {
        // Declare the optimization model
        HxModel model = optimizer.GetModel();

        bands = new HxExpression[nbMaxBands];
        rolls = new HxExpression[nbMaxRolls];
        bandWidth = new HxExpression[nbMaxBands];
        bandLength = new HxExpression[nbMaxBands];
        rollUsed = new HxExpression[nbMaxRolls];
        totalWidth = new HxExpression[nbMaxRolls];

        // Set decisions: bands[b] represents the items assigned to band b
        for (int b = 0; b < nbMaxBands; ++b)
            bands[b] = model.Set(nbItems);

        // Set decisions: rolls[r] represents the bands assigned to roll r
        for (int r = 0; r < nbMaxRolls; ++r)
            rolls[r] = model.Set(nbMaxBands);

        // Each item must be in exactly one band, and each band in exactly one roll
        model.Constraint(model.Partition(bands));
        model.Constraint(model.Partition(rolls));

        // Create model arrays for item data
        HxExpression widths = model.Array(rawWidth);
        HxExpression lengths = model.Array(rawLength);

        for (int b = 0; b < nbMaxBands; ++b)
        {
            // Length constraint for each band
            bandLength[b] = model.Sum(bands[b],
                model.LambdaFunction(i => lengths[i]));

            model.Constraint(bandLength[b] <= rollLength);

            // All items in a band must have the same width
            HxExpression distinctWidths = model.Distinct(bands[b],
                model.LambdaFunction(i => widths[i]));
            model.Constraint(model.Count(distinctWidths) <= 1);
            
            bandWidth[b] = model.If(
                model.Count(bands[b]) > 0,
                model.Max(bands[b], model.LambdaFunction(i => widths[i])),
                0);
        }

        // Create array of band width expressions for roll lambdas
        HxExpression bandWidthArray = model.Array(bandWidth);

        for (int r = 0; r < nbMaxRolls; ++r)
        {
            // The roll's width is the sum of the widths of its bands
            totalWidth[r] = model.Sum(rolls[r],
                model.LambdaFunction(b => bandWidthArray[b]));
            model.Constraint(totalWidth[r] <= rollWidth);

            rollUsed[r] = model.Count(rolls[r]) > 0;
        }

        // Minimize the number of used rolls
        numberOfUsedRolls = model.Sum(rollUsed);
        model.Minimize(numberOfUsedRolls);

        model.Close();

        // Parametrize the optimizer
        optimizer.GetParam().SetTimeLimit(limit);

        // Stop the search if the lower threshold is reached
        optimizer.GetParam().SetObjectiveThreshold(0, minNumberOfRolls);

        optimizer.Solve();
    }

    /* Write the solution in a file */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine("Number of rolls used: " + numberOfUsedRolls.GetValue());
            output.WriteLine("Roll dimensions: " + rollLength + " x " + rollWidth);
            output.WriteLine();
            int rollIndex = 0;
            for (int r = 0; r < nbMaxRolls; ++r)
            {
                HxCollection rollCollection = rolls[r].GetCollectionValue();
                if (rollCollection.Count() == 0)
                    continue;
                output.WriteLine("Roll " + rollIndex + " | width: "
                    + totalWidth[r].GetValue() + "/" + rollWidth);
                for (int i = 0; i < rollCollection.Count(); ++i)
                {
                    int b = (int)rollCollection[i];
                    HxCollection bandCollection = bands[b].GetCollectionValue();
                    if (bandCollection.Count() == 0)
                        continue;
                    output.Write("  Band width=" + bandWidth[b].GetValue()
                        + " length=" + bandLength[b].GetValue() + " | Items: ");
                    for (int ii = 0; ii < bandCollection.Count(); ++ii)
                        output.Write(bandCollection[ii] + " ");
                    output.WriteLine();
                }
                rollIndex++;
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: CuttingStock inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "10";

        using (CuttingStock model = new CuttingStock())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}

Compilation / Execution (Windows): javac CuttingStock.java -cp %HX_HOME%\bin\hexaly.jar

java -cp %HX_HOME%\bin\hexaly.jar;. CuttingStock instances\A1.txt

Compilation / Execution (Linux): javac CuttingStock.java -cp /opt/hexaly_15_0/bin/hexaly.jar

java -cp /opt/hexaly_15_0/bin/hexaly.jar:. CuttingStock instances/A1.txt

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class CuttingStock {
    // Number of item types and items (expanded by demand)
    private int nbItemTypes;
    private int nbItems;

    // Roll dimensions
    private int rollWidth;
    private int rollLength;

    // Maximum number of bands and rolls
    private int nbMaxBands;
    private int nbMaxRolls;

    // Minimum number of rolls (lower bound)
    private int minNumberOfRolls;

    // Item dimensions (expanded by demand)
    private long[] rawWidth;
    private long[] rawLength;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Decision variables
    private HxExpression[] bands;
    private HxExpression[] rolls;

    // Band expressions
    private HxExpression[] bandWidth;
    private HxExpression[] bandLength;

    // Roll expressions
    private HxExpression[] rollUsed;
    private HxExpression[] totalWidth;

    // Objective
    private HxExpression numberOfUsedRolls;

    private CuttingStock(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            input.useLocale(Locale.ROOT);
            nbItemTypes = input.nextInt();
            rollWidth = input.nextInt();
            rollLength = input.nextInt();

            // Read item types and expand by demand
            ArrayList<Long> widthList = new ArrayList<>();
            ArrayList<Long> lengthList = new ArrayList<>();
            for (int t = 0; t < nbItemTypes; ++t) {
                int width = input.nextInt();
                int length = input.nextInt();
                int demand = input.nextInt();
                for (int c = 0; c < demand; ++c) {
                    widthList.add((long) width);
                    lengthList.add((long) length);
                }
            }

            nbItems = widthList.size();
            rawWidth = new long[nbItems];
            rawLength = new long[nbItems];
            for (int i = 0; i < nbItems; ++i) {
                rawWidth[i] = widthList.get(i);
                rawLength[i] = lengthList.get(i);
            }

            nbMaxBands = nbItems;
            nbMaxRolls = nbItems;

            // Lower bound on total number of rolls: total item area / rollArea
            long totalArea = 0;
            for (int i = 0; i < nbItems; ++i) {
                totalArea += rawWidth[i] * rawLength[i];
            }
            minNumberOfRolls = (int) Math.ceil((double) totalArea / ((double) rollWidth * rollLength));
        }
    }

    private void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        bands = new HxExpression[nbMaxBands];
        rolls = new HxExpression[nbMaxRolls];
        bandWidth = new HxExpression[nbMaxBands];
        bandLength = new HxExpression[nbMaxBands];
        rollUsed = new HxExpression[nbMaxRolls];
        totalWidth = new HxExpression[nbMaxRolls];

        // Set decisions: bands[b] represents the items assigned to band b
        for (int b = 0; b < nbMaxBands; ++b) {
            bands[b] = model.setVar(nbItems);
        }
        // Set decisions: rolls[r] represents the bands assigned to roll r
        for (int r = 0; r < nbMaxRolls; ++r) {
            rolls[r] = model.setVar(nbMaxBands);
        }

        // Each item must be in exactly one band, and each band in exactly one roll
        model.constraint(model.partition(bands));
        model.constraint(model.partition(rolls));

        // Create model arrays for item data
        HxExpression widths = model.array(rawWidth);
        HxExpression lengths = model.array(rawLength);

        for (int b = 0; b < nbMaxBands; ++b) {
            // Length constraint for each band
            bandLength[b] = model.sum(bands[b],
                model.lambdaFunction(i -> model.at(lengths, i)));
            model.constraint(model.leq(bandLength[b], rollLength));

            // All items in a band must have the same width
            HxExpression distinctWidths = model.distinct(bands[b],
                model.lambdaFunction(i -> model.at(widths, i)));
            model.constraint(model.leq(model.count(distinctWidths), 1));

            bandWidth[b] = model.iif(
                model.gt(model.count(bands[b]), 0),
                model.max(bands[b],
                    model.lambdaFunction(i -> model.at(widths, i))),
                0);
        }

        // Create array of band width expressions for roll lambdas
        HxExpression bandWidthArray = model.array(bandWidth);

        for (int r = 0; r < nbMaxRolls; ++r) {
            // The roll's width is the sum of the widths of its bands
            totalWidth[r] = model.sum(rolls[r],
                model.lambdaFunction(b -> model.at(bandWidthArray, b)));
            model.constraint(model.leq(totalWidth[r], rollWidth));

            rollUsed[r] = model.gt(model.count(rolls[r]), 0);
        }

        // Minimize the number of used rolls
        numberOfUsedRolls = model.sum(rollUsed);
        model.minimize(numberOfUsedRolls);
        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(limit);

        // Stop the search if the lower threshold is reached
        optimizer.getParam().setObjectiveThreshold(0, minNumberOfRolls);

        optimizer.solve();
    }

    /* Write the solution in a file */
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            output.println("Number of rolls used: " + numberOfUsedRolls.getValue());
            output.println("Roll dimensions: " + rollLength + " x " + rollWidth);
            output.println();
            int rollIndex = 0;
            for (int r = 0; r < nbMaxRolls; ++r) {
                HxCollection rollCollection = rolls[r].getCollectionValue();
                if (rollCollection.count() == 0)
                    continue;
                output.println("Roll " + rollIndex + " | width: "
                    + totalWidth[r].getValue() + "/" + rollWidth);
                for (int bi = 0; bi < rollCollection.count(); ++bi) {
                    int b = (int) rollCollection.get(bi);
                    HxCollection bandCollection = bands[b].getCollectionValue();
                    if (bandCollection.count() == 0)
                        continue;
                    output.print("  Band width=" + bandWidth[b].getValue()
                        + " length=" + bandLength[b].getValue() + " | Items: ");
                    for (int ii = 0; ii < bandCollection.count(); ++ii) {
                        output.print(bandCollection.get(ii) + " ");
                    }
                    output.println();
                }
                rollIndex++;
            }
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java CuttingStock inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "10";

        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            CuttingStock model = new CuttingStock(optimizer);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}

Problem

Principles learned

Data

Model

Explore templates