How to calculate array elements in or-tools solver?

Question

I had used or-tools for optimizing the cutting stock planner problem in which it cut the rolls as per customer requirements but in the current program, the issue is it cuts n number of cuts but in reality, it's not possible for every hardware machine that cut the rolls has some limited blades for cutting so at that time it not giving output as expected.

My problem is I want to apply the limit on cuts which is currently managed using a solver I am unable to debug the solver function as it can not print values if anyhow I can set a limit on the number of values that are added using the solver.add() then I can set a limit on cut Code and problem reference: https://github.com/emadehsan/csp

from ortools.linear_solver import pywraplp
    # x[i][j] = 3 means that small-roll width specified by i-th order
        # must be cut from j-th order, 3 tmies
        x = [[solver.IntVar(0, b[i], f'x_{i}_{j}') for j in range(k[1])]
             for i in range(num_orders)]
    
        unused_widths = [solver.NumVar(0, parent_width, f'w_{j}')
                         for j in range(k[1])]
    
        # will contain the number of big rolls used
        nb = solver.IntVar(k[0], k[1], 'nb')
    
        # consntraint: demand fullfilment
        for i in range(num_orders):
            # small rolls from i-th order must be at least as many in quantity
            # as specified by the i-th order
            solver.Add(sum(x[i][j] for j in range(k[1])) >= demands[i][0])
    
        # constraint: max size limit
        for j in range(k[1]):
            # total width of small rolls cut from j-th big roll,
            # must not exceed big rolls width
            solver.Add(
                sum(demands[i][1]*x[i][j] for i in range(num_orders))
                <= parent_width*y[j]
            )
    
            # width of j-th big roll - total width of all orders cut from j-th roll
            # must be equal to unused_widths[j]
            # So, we are saying that assign unused_widths[j] the remaining width of j'th big roll
            solver.Add(parent_main_width*y[j] - sum(demands[i][1]*x[i][j]
                       for i in range(num_orders)) == unused_widths[j])
    
    if j < k[1]-1:  # k1 = total big rolls
                # total small rolls of i-th order cut from j-th big roll must be >=
                # totall small rolls of i-th order cut from j+1-th big roll
                solver.Add(sum(x[i][j] for i in range(num_orders))
                           >= sum(x[i][j+1] for i in range(num_orders)))

So if anyone has any idea how can I set this or calculate a number of elements in the solver.add() then please help me to resolve this

For better understanding, I had attached a screenshot. As per the current code count of cuts is increased when the size is smaller but I want to set fix number of cuts whatever the length is there the number of cuts should not increase more than 7. So anyone has any idea how to achieve this?

Answer 1

Since my experience with OR-Tools is using c#, not Python, I attach an example here in c# of how to realize the constraint on the number of cuts. It is effectively the constraint I mentioned in my comment for j in range (k[1]) solver.Add(sum(x[i][j] for i in range(num_orders)) <= number_of_blades) except formulated in c# notation. I don't know why that didn't work for you.

I extended that concept to include the case that the last "leftover" piece in a big roll could be used for an order, i.e. when the unused width for a roll turns out to be 0. In that case you would have 7 cuts but get 8 rolls usable for orders since the last piece matches the width required for an order.

As the objective, I minimize the number of big rolls needed.

Here's my c# code, I hope you can make the Python equivalent.

using Google.OrTools.Sat;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

// Implementation for https://stackoverflow.com/questions/68848210/how-to-calculate-array-elements-in-or-tools-solver
namespace SO68841210
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Google.OrTools.Sat.CpModel model = new CpModel();
                ORModel myModel = new ORModel();
                myModel.initModel(model);
                IntVar[] decisionVariables = myModel.decisionVariables;

                // Creates a solver and solves the model.
                CpSolver solver = new CpSolver();
                VarArraySolutionPrinter solutionPrinter = new VarArraySolutionPrinter(myModel.variablesToPrintOut);
                solver.SearchAllSolutions(model, solutionPrinter);
                Console.WriteLine(String.Format("Number of solutions found: {0}",
                    solutionPrinter.SolutionCount()));
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                Console.WriteLine(e.StackTrace);
                throw;
            }

            Console.WriteLine("OK");
            Console.ReadKey();
        }
    }

    class ORModel
    {
        // Orders
        int num_orders;
        long[] width;
        long[] quantity;

        int max_big_rolls;
        long parent_width ;

        long max_cutters;

        // x[i][j] = number of cuts from roll j for order i
        // x[i][j] = 3 means that small-roll width specified by i-th order
        // must be cut from j-th big roll, 3 times
        IntVar[][] x;

        // Is roll j used or not?
        IntVar[] y;

        // widths_for_roll[i][j] = total width cut from big roll j for order i
        IntVar[][] widths_for_roll;

        // Unused width of each roll; unused_widths[j] = unused width for roll j
        IntVar[] unused_widths;

        // Number of big rolls actually used
        IntVar number_of_big_rolls_used;

        // Number of cuts; cuts[j] = number of cuts for roll j
        IntVar[] cuts;

        // Is the last piece usable for roll j?
        IntVar[] last_piece_usable;


        public ORModel()
        {
            // Order data
            num_orders = 2;
            width = new long[] { 4, 10 };
            quantity = new long[] { 10, 2 };

            // Solution domain 
            max_big_rolls = 4;

            // Cutting machine data
            parent_width = 100;
            max_cutters = 7;
        }

        public void initModel(CpModel model)
        {
            // Create variable number of small rolls cut from big roll j for order i
            x = new IntVar[num_orders][];
            for (int i = 0; i < num_orders; i++)
            {
                x[i] = new IntVar[max_big_rolls];
                for (int j = 0; j < max_big_rolls; j++)
                {
                    x[i][j] = model.NewIntVar(0, quantity[i], string.Format("Small rolls cut from big roll {0} for order {1}", j, i));
                }
            }

            // Is the roll used or not?
            // y[j] = 1 when the roll is used, otherwise 0
            y = new IntVar[max_big_rolls];
            for (int j = 0; j < max_big_rolls; j++)
            {
                y[j] = model.NewBoolVar(string.Format("Big roll {0} is used", j));
            }

            // Symmettry breaking: use the first rolls first
            for (int j = 0; j < (max_big_rolls - 1); j++)
            {
                model.Add(y[j] >= y[j + 1]);
            }

            // Constraint: demand fulfillment; the number of small rolls for order i must equal the order quantity
            for (int i = 0; i < num_orders; i++)
            {
                model.Add(LinearExpr.Sum(x[i]) == quantity[i]);
            }

            // Constraint: Max size limit. The total width of small rolls cut from jth big roll may not exceed big roll's width

            // First construct total width of all rolls cut from big rolls per order
            // widths_for_roll[i][j] = total width cut from big roll j for order i
            widths_for_roll = new IntVar[num_orders][];
            for (int i = 0; i < num_orders; i++)
            {
                widths_for_roll[i] = new IntVar[max_big_rolls];
                for (int j = 0; j < max_big_rolls; j++)
                {
                    widths_for_roll[i][j] = model.NewIntVar(0, parent_width, string.Format("Total width cut from roll {0} for order {1}", j, i));
                    model.Add(widths_for_roll[i][j] == (x[i][j] * width[i]));
                }
            }

            // Unused widths of each roll
            unused_widths = new IntVar[max_big_rolls];
            for (int j = 0; j < max_big_rolls; j++)
            {
                unused_widths[j] = model.NewIntVar(0, parent_width, string.Format("Unused width for roll {0}", j));
                IntVar[] widths_per_order = new IntVar[num_orders];
                for (int i = 0; i < num_orders; i++)
                {
                    widths_per_order[i] = widths_for_roll[i][j];
                }
                // Unused width is total width of roll minus sum of orders cut from it
                model.Add(unused_widths[j] == (parent_width  - LinearExpr.Sum(widths_per_order)));
                // Total width cut may not exceed width of big roll (unused width must be >= 0).
                model.Add(unused_widths[j] >= 0);
            }

            // Number of big rolls actually used
            number_of_big_rolls_used = model.NewIntVar(0, max_big_rolls, "Number of big rolls used");
            model.Add(number_of_big_rolls_used == LinearExpr.Sum(y));

            // Don't add this constraint for the time being
            //if j < k[1] - 1:  # k1 = total big rolls
            //    # total small rolls of i-th order cut from j-th big roll must be >=
            //    # totall small rolls of i-th order cut from j+1-th big roll
            //    solver.Add(sum(x[i][j] for i in range(num_orders))
            //               >= sum(x[i][j + 1] for i in range(num_orders)))

            // Maximum number of cuts per roll must be <= number of cutters
            // Number of cuts; cuts[j] = number of cuts for roll j
            // We need to consider that an order could be fulfilled with no leftover piece. When
            // the last piece cut results in unused_widths[j] == 0, then there would be 8 usable small rolls
            // but only 7 cuts. If the last piece is not used for an order (unused_widths[j] > 0), there are 7 usable small rolls
            // and 7 cuts, and an unused piece left over.
            cuts = new IntVar[max_big_rolls];
            last_piece_usable = new IntVar[max_big_rolls];
            for (int j = 0; j < max_big_rolls; j++)
            {
                cuts[j] = model.NewIntVar(0, max_cutters, string.Format("Number of cuts for roll {0}", j));
                IntVar[] small_rolls_per_order_for_this_big_roll = new IntVar[num_orders];
                for (int i = 0; i < num_orders; i++)
                {
                    small_rolls_per_order_for_this_big_roll[i] = x[i][j];
                }
                last_piece_usable[j] = model.NewBoolVar(string.Format("Last piece usable for roll {0}", j));
                // We want last_piece_usable[j] to be equivalent to unused_widths[j] == 0
                // See https://developers.google.com/optimization/cp/channeling example:
                // Implement b == (a >= 5).
                // model.Add(a >= 5).OnlyEnforceIf(b);
                // model.Add(a < 5).OnlyEnforceIf(b.Not());
                model.Add(unused_widths[j] > 0).OnlyEnforceIf(last_piece_usable[j].Not());
                model.Add(unused_widths[j] == 0).OnlyEnforceIf(last_piece_usable[j]);

                // If we can use the last small roll for an order, the number of cuts is one less than the number of small rolls
                // But if we can't use the last piece, the number of cuts is equal to the number of small rolls from the big roll
                model.Add(cuts[j] == (LinearExpr.Sum(small_rolls_per_order_for_this_big_roll) - last_piece_usable[j]));

                // The number of cuts is limited by the machine
                model.Add(cuts[j] <= max_cutters);

                // A roll is considered used only if there are small rolls for orders being cut from it
                model.Add(LinearExpr.Sum(small_rolls_per_order_for_this_big_roll) != 0).OnlyEnforceIf(y[j]);
                model.Add(LinearExpr.Sum(small_rolls_per_order_for_this_big_roll) == 0).OnlyEnforceIf(y[j].Not());
            }

            // Objective: minimize the number of big rolls needed
            model.Minimize(number_of_big_rolls_used);
        }

        public IntVar[] variablesToPrintOut
        {
            get
            {
                return decisionVariables;
            }
        }

        public IntVar[] decisionVariables
        {
            get
            {
                List<IntVar> decisionVariables_ = new List<IntVar>();
                for (int i = 0; i < num_orders; i++)
                {
                    for (int j = 0; j < max_big_rolls; j++)
                    {
                        decisionVariables_.Add(x[i][j]);
                        decisionVariables_.Add(widths_for_roll[i][j]);
                    }
                }
                for (int j = 0; j < max_big_rolls; j++)
                {
                    decisionVariables_.Add(y[j]);
                    decisionVariables_.Add(unused_widths[j]);
                    decisionVariables_.Add(last_piece_usable[j]);
                    decisionVariables_.Add(cuts[j]);
                }
                decisionVariables_.Add(number_of_big_rolls_used);
                return decisionVariables_.ToArray();
            }
        }
    }
    public class VarArraySolutionPrinter : CpSolverSolutionCallback
    {
        private int solution_count_;
        private IntVar[] variables;

        public VarArraySolutionPrinter(IntVar[] variables)
        {
            this.variables = variables;
        }
        public override void OnSolutionCallback()
        {
            // using (StreamWriter sw = new StreamWriter(@"C:\temp\GoogleSATSolverExperiments.txt", true, Encoding.UTF8))
            using (TextWriter sw = Console.Out)
            {
                sw.WriteLine(String.Format("Solution #{0}: time = {1:F2} s;",
                solution_count_, WallTime()));
                foreach (IntVar v in variables)
                {
                    sw.Write(
                    String.Format(" {0} = {1}\r\n", v.ShortString(), Value(v)));
                }
                solution_count_++;
                sw.WriteLine();
            }
            if (solution_count_ >= 10)
            {
                StopSearch();
            }
        }
        public int SolutionCount()
        {
            return solution_count_;
        }
    }
}

This was the solution found:

Solution #0: time = 0,01 s;
 Small rolls cut from big roll 0 for order 0 = 5
 Total width cut from roll 0 for order 0 = 20
 Small rolls cut from big roll 1 for order 0 = 5
 Total width cut from roll 1 for order 0 = 20
 Small rolls cut from big roll 2 for order 0 = 0
 Total width cut from roll 2 for order 0 = 0
 Small rolls cut from big roll 3 for order 0 = 0
 Total width cut from roll 3 for order 0 = 0
 Small rolls cut from big roll 0 for order 1 = 0
 Total width cut from roll 0 for order 1 = 0
 Small rolls cut from big roll 1 for order 1 = 2
 Total width cut from roll 1 for order 1 = 20
 Small rolls cut from big roll 2 for order 1 = 0
 Total width cut from roll 2 for order 1 = 0
 Small rolls cut from big roll 3 for order 1 = 0
 Total width cut from roll 3 for order 1 = 0
 Big roll 0 is used = 1
 Unused width for roll 0 = 80
 Last piece usable for roll 0 = 0
 Number of cuts for roll 0 = 5
 Big roll 1 is used = 1
 Unused width for roll 1 = 60
 Last piece usable for roll 1 = 0
 Number of cuts for roll 1 = 7
 Big roll 2 is used = 0
 Unused width for roll 2 = 100
 Last piece usable for roll 2 = 0
 Number of cuts for roll 2 = 0
 Big roll 3 is used = 0
 Unused width for roll 3 = 100
 Last piece usable for roll 3 = 0
 Number of cuts for roll 3 = 0
 Number of big rolls used = 2

Number of solutions found: 1