Analysis of Linear Constraints
Prof. Dr. A. Schweikard, F. Schwarzer

The analysis of linear constraint sets has a large number of applications. We have investigated this analysis in the context of

Solution of Cutting Stock Problems

The goal is to find a placement of given star-shaped polygons that has a minimum enclosing rectangle (with horizontal and vertical edges). We consider applications where parts must have an initially specified orientation. This condition is given e.g. in the stock cutting domain when the cloth has an oriented pattern. The above algorithm that tests for removability can be easily adopted for simple instances of this minimization problem: We perform a complete analysis (visit all reachable D-nodes), omit the test for unboundedness, and perform a minimization of x1 + y1 + x2 + y2 + ... + xk + yk for each D-node. The D-point (simultaneous placement of all parts) with minimum enclosing rectangle is the solution.

With this approach we can determine the global optimum, which is not possible with other methods such as simulated annealing, etc. However, currently the number of parts and vertices per part is very limited.

Example:
For the human it is nearly impossible to prove optimality even in this simple example.

initial placement
optimal placement

Running time15sec.
Nodes in search tree1137
Min. whitespace51.15%