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 time | 15sec. |
| Nodes in search tree | 1137 |
| Min. whitespace | 51.15% |