A serious problem facing the manufacturer of many industrial products is to cut from one large roll of material, a number of shapes which are used as components in the finished product. A recent customer contract for IF Computer GmbH involved optimising the usage of a material roll. Regular perpendicular objects should be placed on the surface, so that when cut, minimal wastage remained.

The approach taken was especially efficient through the usage of IF/Prolog's Constraint Technology. Constraints are specified so that objects do not overlap for different object orientations and surface positions.

The illustration above shows how these perpendicular shapes might be arranged on the roll of material to minimise the wastage.. Optimising such a general situation is not trivual; many algorithms have been developed for similar specific problems in operations research.

In the following we show how such a general purpose optimisation problem can be tackled using constraint logic programming in IF/Prolog. The approach we take is to define constraints which guarentee that rectangles do not overlap and feed these constraints into a builtin branch-and-bound solver to assign positions to the shapes' corners, mimimising the end positions of every rectangle and therefore reducing the total wastage of material.

The high-level programming constructs provided by IF/Prolog allow such a problem to be tackled in a small amount of code; under 1000 lines.

Traditional operations research approaches to such problems would require considerable investment in re-engineering basic optimisation algorithms using perhaps ten times as much code. Also, some of the aspects of the problem we tackle, cannot be used with standard operations research approaches; for example: integer linear programming or simplex solvers. Reducing this problem to 0/1 linear programming problem, does mean that the problems can be tackled, but in so doing the number of variables is significantly increased and efficiency is lost.

Our approach is therefore not only more cost effective software engineering, it also produces a more efficient solution which can be modified easily to take on new ideas or restrictions.

A number of four and six sided objects are to be placed on a roll of material to minimise the wastage of material. Objects have all sides perpendicular to one-another and may optionally, be placed in different orientations, either along or across the material. Each orientation must also lie perpendicular to the material. Therefore, there are two possible orientations for four sided objects and four possible orientations for six-sided objects. The material itself is sufficiently long but has one fixed end and one end which should be minimised.

It is also desirable that the order in which objects are placed on the material nears to some extent the order in which objects are initially specified, to give an approximate ``first in first out'' behaviour of orders.

The problem is very combinatorial in nature; when considering for example, the efficient placement of some 100 four sided objects there are some 10^375 possible combinations of object and orientation. When considering six-sided objects the complexity rises still further.

In tackling this problem we are looking to reduce this complexity in several ways: by removing symmetry from the problem and by making sensible heuristic decisions to limit the possible placements that are considered.

The real power of constraint logic programming when approaching such a problem is being able to incrementally develop algorithms, by building up layers of constraints. Constraints themselves act on several variables to build a complex network of inter-dependencies which are used to constrain the search space for a solution. The solution is then computed using a builtin branch-and-bound algorithm which assigns values to variables ensuring that no constraints are violated and at the same time optimising the end-positions of all objects.

Decomposing the problem shows how different builtin constraint procedures can be combined to producing inter-dependencies between variables. These variables are mapped onto objects in the conceptual model and refer to concrete positions in the eventual solution.

In our description we refer to `slots' as a position on the material which may be filled by any of the rectangular objects in any of its possible orientations. Slots are constrained not to overlap but their dimensions and position vary as different objects and orientations are considered in the branch-and-bound search for a solution. A slot holds a four-sided object, a rectangle. Six-sided objects therefore occupy two slots which are additionally constrained to lie in relation to one-another, depending on the orientation of the object.

The following constraints are sufficient to describe the problem. Later we shall see how these conditions are mapped onto concrete pieces of code. A separate layer of constraint application is then incrementally developed to build up the complex mesh of inter-dependencies between variables.

• Layer 1: Each slot must be placed on the material.
• Layer 2: Each slot may be occupied by any one rectangular object in an orientation.
• Layer 3: Each slot must not overlap another slot in 2 dimensions.
• Layer 4: When a slot forms part of a six-sided object the neighboring slot is used and further constraints are applied to ensure that orientations and edges align.

In the implementation a slot is represented as a Prolog structure with four variables denoting the edges of the rectangle:

rectangle(Left,Right,Top,Bottom)
 

The order in which all the constraints are applied does not matter. We can use simple data-structure traversal routines to apply the constraints and incrementally develop and test the code to ensure that the constraints perform as they should.

Each of the following routines applies a layer of constraints; together all layers specify the problem to be passed to the solver.

So called `hard constraints' are used to delimit the outer range of possible values assignable to each slot variable. Given a list of all slots and the Length and Width of the material we can apply the following constraints that all slot variables lie on the surface:

const_material([],_Length,_Width).
const_material([rectangle(L,R,T,B)|RTail],Length,Width) :-
        [L,R] in 0:Length,
        [T,B] in 0:Width,
        const_material(RTail,Length,Width).

The predicate in/2 specifies the finite domain of variables. Domains may be specified as either intervals, as above, (where range checking is performed internally), enumerations (a sorted list of integers) or as a sequence. The different domain types are handled transparently by IF/Prolog.

The builtin predicate relation/2 is used to constrain slot variables to belong to each of the possible sets of values defined in the list Orientations. The slot edge variables L, R, T and B have their values propogated from the object dimensions X and Y specified in the relation.

The list Orientations also contains fields for the rectangle identifier (Id) and orientations (Or).

The builtin global constraint all_distinct/1 is used to ensure that an individual rectangle identifier is used only once.

const_orientations([],[],[],_Orientations).
const_orientations([rectangle(L,R,T,B)|RTail],[Id|RIdTail],
		   [Or|ROrTail],Orientations) :-
        R ?= L + X, T ?= B + Y,
        relation([Id,Or,X,Y],Orientations),
        const_orientations(RTail,RIdTail,ROrTail,Orientations).

const_ids(RectangleIds,No) :-
        RectangleIds in 0..No,
        all_distinct(RectangleIds).

The following comparison constraints between two slots is made:

const_no_overlap_rectangle(rectangle(LA,RA,TA,BA),rectangle(LB,RB,TB,BB)) :-
        cardinality(1, 2, [LA ?>= RB, RA ?=< LB, BA ?>= TB, TA ?=< BB]).

The builtin predicate cardinality/3 is used to ensure that at least 1 and at most 2, of the comparisons in the list apply. The comparisons ensure that rectangle A is either to the right-of, left-of, above or below rectangle B.

A six-sided object is represented as two slots which are dynamically constrained to be next-to one another. Applying this constraint is complicated by the fact that the edges which should be constrained next-to one another, change as the orientation of the rectangles in the slots change.

The constraint can be implemented by suspending a conditional goal on the rectangle Id variable and then once the Id variable is assigned due to placing a rectangle, the neighboring slot is forced to become the partner slot to comprise the six-sided object. A conditional on the slots orientation variable, will then ensure the correct constraints between edges are applied.

The two edge comparisons that should be performed, depending on the orientation of the slots within the six-sided object are passed to this predicate in the form:

 (up -> (right = left), (down = down))

The following code then decodes this structural information and generates the conditional constraint, in this case using the domain_if/3 predicate.

const_linkage([],_RId,_ROrA,_ROrB,_RectA,_RectB).
const_linkage([constraint(Id,Tests)|LTail],RId,ROrA,ROrB,RectA,RectB) :-
        const_link_constraints(Tests,ROrA,RectA,RectB,Constraints),
        domain_if(RId ?= Id,(ROrA ?= ROrB,Constraints)),
        const_linkage(LTail,RId,ROrA,ROrB,RectA,RectB).

const_link_constraints([],_ROrA,_RectA,_RectB,true).
const_link_constraints([(Orient -> (RectAM1 = RectBM1),(RectAM2 = RectBM2))
                        |LinkTail], ROrA,RectA,RectB,Constraint) :-
        const_match(RectAM1,RectA,EdgeAM1), const_match(RectBM1,RectB,EdgeBM1),
        const_match(RectAM2,RectA,EdgeAM2), const_match(RectBM2,RectB,EdgeBM2),
        Constraint = (  ROrA = Orient
                     -> EdgeAM1 ?= EdgeBM1,
                        EdgeAM2 ?= EdgeBM2
                     ;  ConTail),
        const_link_constraints(LinkTail,ROrA,RectA,RectB,ConTail).

const_match(left, rectangle(L,_,_,_),L).
const_match(right,rectangle(_,R,_,_),R).
const_match(up,   rectangle(_,_,T,_),T).
const_match(down, rectangle(_,_,_,B),B).

The four layers of constraints are sufficient to specify the non-overlaping objects:

• Layer 1: determined hard constraints for the outer bounds of slot variables.
• Layer 2: describes the relation constraints to assign one object to one slot and propogate the slot edges, identifiers and orientations.
• Layer 3: applied constraints to ensure that slots do not overlap using the slot variables propogated from the relation constraints in layer 2.
• Layer 4: deals with the special case when an object is a six-sided object. Here additional constraints align the two slots for different orientations.

We can apply these constraint routines in any order, the final result will in every case be the same. There are now several lists of variables where variables are bound into program structures like rectangle(L,R,T,B) and also into constraints like R ?= X + L. Constraints are used to propogate the search, as soon as any two of the variables in the constraint R ?= X + L are known, then a value can be assigned to the third variable. When a variable is assigned, all other constraints dependent on that variable are fired, in this way no onconsistency is allowed in the search and much of the search-space is pruned away.

The final step in solving the constraint logic program is to invoke the branch-and-bound optimisation routine. For this problem it is most apropriate to use the minimize_maximum/2 predicate. In this case there are such a large number of solutions, that it is sensible to time-out the labelling process after MaxTime seconds.

	minimize_maximum(label_tb(Vars,MaxTime,[]), Ends),
	label(Orientations)

The list Vars contains all the variables in the slots together with the slot IDs. Orientations and other intermediate variables are only assigned by constraint propogation. Therefore, it is usual to find that not all variables have been assigned a value although it is known that a solution exists. In our example it is necessary to label the Orientations variables to assign values where only a single orientation exists after the optimisation step is complete.

The program as described works well for small numbers of objects but as soon as more than 12 objects with 16 slots are specified the complexity of the problem starts to exceed both memory and time limits of our 32Mb Pentium PC.

Clearly it is irrelevant what hardware we use to run this program. Every machine that exists will have some, relatively small number of objects, that exceeds the capacity of the machine.

Our best approach to remedeeing the situation is to work with the problem. We aim to design new ways to reduce the complexity and apply new layers of constraints to reduce the search space still further. We need to remove symmetry from the problem and add a new layer of constraints to do so.

To avoid constraining each and every slot not to overlap each and every other slot we placed an ordering on groups of slots over the materials length. We define a number of slots as a segment of slots. All slots within neighboring pairs of segments are constrained not to overlap as before. Additionally, all slots within two alternate non-neighboring segments are constrained to be to the right-of all slots in the other segment. For segments 1 to N the following segment ordering constraints ensure a complete ordering over segments.

1  <  3  <  5  <  7  <  9  <  11  <   . . .
   2  <  4  <  6  <  8  <  10  < 12   . . .
1    <   4    <   7    <   10   <     . . .
   2    <   5    <   8    <   11  <   . . .
      3    <   6   <    9    <   12   . . .

Again, the cardinality/3 predicate can be used to ensure that a single slot is to the right-of all slots in the two segments. All constraints hold when both the at-least and at-most values equal the number of constraints. A single cardinality/3 constraint is built for each slot to determine ordering constraints on other slots in other segments.

const_segment_ordered([]).
const_segment_ordered([_Segment1]).
const_segment_ordered([_Segment2,_Segment1]).
const_segment_ordered([Segment3,_Segment2,Segment1]) :-
        const_segment_right_of(Segment3,Segment1).
const_segment_ordered([Segment4,Segment3,Segment2,Segment1|SegmentTail]) :-
        append(Segment1,Segment2,Segment12),
        const_segment_right_of(Segment4,Segment12),
        const_segment_ordered([Segment3,Segment2,Segment1|SegmentTail]).

const_segment_right_of([],_Segment12).
const_segment_right_of([rectangle(L,_R,_T,_B)|RTail],Segment12) :-
        const_right_of_const(Segment12,L,Constraints),
        list_length(Constraints,ConstraintLength),
        cardinality(ConstraintLength, ConstraintLength, Constraints),
        const_segment_right_of(RTail,Segment12).

const_right_of_const([],_Var,[]).
const_right_of_const([rectangle(_L,R,_T,_B)|RTail],Var,[R ?=< Var|CTail]) :-
        const_right_of_const(RTail,Var,CTail).

For example, for a segment size of 4 slots and 100 rectangles the space requirement is reduced by a significant factor from 4950 to 676 constraints.

By decomposing the problem though, restrictions are placed on the eventual solution. No more than twice the number of slots in a single segment may be placed across the material, so the size of the segment must be adjusted to suit possible solutions to the problem.

So far any slot may be assigned any rectangular shape and therefore, in constraint Layer 2 a relation/3 constraint is generated for each slot with as many relational elements as there are slots. The space requirement for these realtions is therefore N squared in the number of slots.

As a slot may be placed in any position relative to other slots on the material there exists a symmetry which can be removed, as each slot within a segment need not take every possible rectangular object, but only all slots combined in a segment need consider each rectangular object.

We partitioned the list of rectangular objects into groups of segment size length. The number of possible rectangular objects assignable to a slot is therefore reduced by a factor of the segment size.

We evaluated this problem in two ways: to assess both how good the solution is and the time and space requirements to find the solution.

For this kind of NP complete problem it is not possible to calculate whether the optimal solution has been attained; we can only measure subjectively, how good the solution is.

By using test-cases where it is know that an optimal fit does exist for a given length of material and number of slots, we see how close the solution obtained is to one of the many optimal solutions.

We consider a test case for 12 slots with an optimal fit in a surface 8 x 16, the following results were obtained:

Ends [2,4,6,2,4,6,8,10,10,12,10,14,14,18,16,18]
Max End 18 after 0.13 secs.
Ends [2,4,6,2,4,6,8,10,12,14,8,12,16,14,17,17]
Max End 17 after 2.35 secs.
Ends [2,6,8,2,4,4,6,8,10,12,12,16,10,16,11,16]
Max End 16 after 6.78 secs.
Result placements :- (max end 16)

This is a very encouraging result, it shows that an initial solution is obtained quickly and that the optimization is then able to improve on this until one of the many optimal placements is found after 6.78 seconds.

We then executed a similar optimal fit for some 112 slots for a surface 8 x 128, the following result was obtained:

Ends [2,4,8,6,9,11,11, ... 127,128,130,132,130,130,132,132]
Max End 132 after 10.3 secs.
Result placements :- (max end 132)

Which shows that an initial solution is obtained quickly, but no further optimization is made in the maximum 130 seconds allowed for the execution.

The maximum space requirement for a 100 slot problem was under 8Mb and all timings were performed on a Pentium 90 PC.

We hope we have convinced you that IF/Prolog's Constraint Technology Package offeres a serious alternative to traditional operations research software engineering.

The flexibility of a high level programming language combined with the power of inbuilt solvers allows you to tackle this and similar resource allocation or scheduling problems by working with the problem, rather than with the solver.

Programmers can incrementally build up layers of constraints working around the symmetry of the problem. This incremental development benefits the software development cycle considerably as each layer is only a small piece of code that can be thoroughly tested. Good re-use is also made of the data-structure traversal algorithms and code size is kept to a minimum.

Shorter IF/Prolog programs are both more readable and more maintainable, and combined with constraint technology a whole range of real problems can be tackled effectively.