Cutting Stock Problem

Question

Hello, I'm new to Solver Foundation. I would like to use it to solve my Cutting Stock Problem.

I have a set of wood bars in different lengths. These bars must be cut in small cuts of given length. I must find the best cut combination in order to minimize the total waste of wood.

Can anyone give me a hit on how to model this problem with Foundation Services?

Best regards.

Answer 1

This sounds like a standard integer programming exercise.  You can do this in a straightforward way with the Solver Foundation Excel Plug In.  But you need to understand how to formulate integer programmes.  Look at the shipped examples.

---

Dr Michael F

Answer 2

Thank you for your interest. I've read the documentation and the examples provided. I was able to create a model that is able to optimize the cuts for each bar (treating the problem as a Knapsack problem) but I cannot formulate a goal to optimise the total waste for all the stock.

Can you give me a hint?

Thank you.

Answer 3

You can set up the constraints so that only legal combinations will be cut from each bar:  variables representing the number of pieces of each length cut from each bar and constraints ensuring the total length of the bar is respected.  The objective function is then just the total length of the pieces cut (relevant variables multiplied by the length of the pieces).  If you maximise this, then you minimise the waste (as the stock is constant).

---

Dr Michael F

Answer 4

My code follows:

            // ....
            SolverContext context = SolverContext.GetContext();

            Model model = context.CreateModel();

            Set cuts = new Set(Domain.Any, "cuts");
            Set bars = new Set(Domain.Any, "bars");

            Parameter length = new Parameter(Domain.RealNonnegative, "length", cuts);
            length.SetBinding(cutList, "Length", "Code");

            model.AddParameters(length);

            Decision assigned = new Decision(Domain.Boolean, "assigned", cuts);
            assigned.SetBinding(cutList, "Assigned", "Code");
            model.AddDecisions(assigned);

            model.AddConstraints("barlength",
                                 Model.Sum(Model.ForEach(cuts, item => length[item]*assigned[item])) <=
                                 barLength);

            model.AddGoal("waste", GoalKind.Minimize,
                          barLength - Model.Sum(Model.ForEach(cuts, item => length[item]*assigned[item])));

            SimplexDirective directive = new SimplexDirective();

            Solution solution = context.Solve(directive);

            context.PropagateDecisions();

            Report r = solution.GetReport();
            log.Debug(r.ToString());

            context.ClearModel();
            
            // ....

Could you give me a hint on how to implement your solution?

Best regards

Answer 5

Your problem here is that your decision variables are one dimensional.  They need to be two dimensional - you assign each cut to a bar.

This looks suspiciously like homework, so I don't really want to give more hints than that.

---

Dr Michael F

Answer 6

You are right. This is really my homework. I believe that Solver Foundation is a great product with really lacking documentation.

I think that, in the and, I'll move to another product.

Thank you for you time.