Augmented Lagrangian Method for Solving Multistage Cutting Stock Problems via Quantum Annealing

The work aims to bring the problem in a QUBO form. For this one has to make use of the tree structure of the problem. One sets up binary variables $x_{i,j}, y_{i,j}$ indicating that piece j is cut out in a vertical or horizontal way directly after piece i. While the demand equality can be included easily as additional terms in the QUBO matrix, the large amount of size inequalities is problematic. These inequalities are addressed in an iterative way by using Augmented Lagrangian methods. In the numeric experiments the individual QUBOs are solved via a Simulated Annealing sampler. This approach is much more resource efficient than using slack variables to reformulate the inequalities. Unbalanced penalization is also investigated in this context [2].

Since the main novel contribution is developing the QUBO formulation for this class of cutting stock problems there is not much focus put in the quantum simulation. Instead the experiments are done with a Simulated Annealing sampler. However, information about compiling QAOA or Quantum Annealing like algorithms on ion trap hardware in the Magnetic Gradient Induced Coupling (MAGIC) setup can easily be added to the presentation or poster. In this case the problem of synthesizing GZZ gates will be presented. Furthermore also some information about possible error sources in ion traps can be presented. Experiments on real hardware are still in the planning stage.  

There will be some scaling analysis about the number of qubits. Since slack variables are avoided at all cost the number of logical qubits equals the number of physical qubits at least for systems with high connectivity like e.g. ion traps. There are several arguments why the developed algorithm may not be a practical application. The large amount of inequalities is difficult to deal with in a QUBO form and MILP formulations in classical computing are very mature. Typically the SOTA algorithms make use of dynamic programming and recursion wich is hard to recreate on a quantum annealer. Nevertheless we did make huge advances in dealing with 2D cutting stock problems. The previous modells only dealt with 2 stage cuts [1]. Furthermore the linear programming formulation we developed has two shortcomings that may motivate quadratic terms. On the one hand, one can better modell the scenario with usable leftovers and on the other hand the non-restricted cases may require quadratic terms.