Originally posted by: SystemAdmin

[pierre schaus said:]

Hello,

I have some questions avout IloBox and its related constraints.
My problem is to pack (small) rectangles into a rectangle surface.
Small rectangles are of fixed size but can take the two orientations.

I wanted to use IloBox but the problem is that the sizes are fixed values in each dimensions.
I would be very useful to have to possibility to speficy sizes  also as variables so that we could completely fix sizes when the orientation of a box is known.

Another feature that would be very useful with this constraint is to extend getNotOverlapConstraint() with arguments to speficy the dimensions
in which boxes are not allowed to overlap.
Of course I could use notOverlapInDimension(IloBox box1, IloBox box2, IloInt dimension) on every pair of boxes and in every dimensions where the overlap is not allowed but would the pruning be the same?

My final question is: What is the usual way in Ilog to pack rectangles into a same rectangle when the small rectangles don't have their orientation fixed?

Thank you,

Pierre.


#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[rdumeur said:]

Hi Pierre,

In ILOG CP, using IloBoxes, you need to write a specific search that tries to place boxes vertically or horizontally. As you end up with 2^N ways to rotate the boxes,  you need a good heuristic.
Concerning pruning when using notOverlapInDimension on each box, the answer is that it shouldn't be the exactly the same, but similar.

In CP Optimizer, we don't have IloBox but you can write a simple model where, given N box width and height values, you have N decision variables that model, for each box:

- the X coordinate
- the Y coordinate
- the rotation status (boolean)

You can then define the rotated width and height of each box.  For instance, if box i is rotated, then its width and height are exchanged. In OPL, you would write something like:
    rwidth[i] == rotated[i]*height[i] + (1 - rotated[i])*width[i];
    rheight[i] == rotated[i]*width[i] + (1 - rotated[j])*height[i];

Eventually, you need to specify non overlap constraints for two i,j boxes:
  x[j] >= (x[i] + rwidth[i]) || (x[j] + rwidth[j]) <= x[i] || y[j] >= (x[i] + rheight[i]) || (y[j] + rheight[j]) <= y[i]<br />
You can use  the length of the longest side of the smallest rectangle containing all the boxes as objective.

You can even add redundant constraints to express the fact that between two boxes, for a given axis, the distance is greater or equal to the smallest side you can find in the two boxes (for boxes can be rotated).

Using CP Optimizer's default search with such a simple model should already give you some interesting results.

I hope it helps.

          Cheers!
   



#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[rdumeur said:]

Hi Pierre,

In my previous email, I forgot to specify indices when specifying rotated widths & heights:

    rwidth[i]== rotated[i]*height[i] + (1 - rotated[i])*width[i];
    rheight[i] == rotated[i]*width[i] + (1 - rotated[j])*height[i];

Sorry about that.

    Cheers!

            Renaud

#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[rdumeur said:]

Oh my!
Array subscripts conflicts with formatting directives (italic).
Using "code" markup will help:


rwidth[i]== rotated[i]*height[i] + (1 - rotated[i])*width[i];
rheight[i] == rotated[i]*width[i] + (1 - rotated[i])*height[i];


is much more understandable now.

Cheers!

        Renaud
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[pierre schaus said:]

Hello Renaud,

Unfortunately, I don't have CP Optimizer but solver 6.3, so no default search.
I wanted to avoid the formulation you give
x[j] >= (x + rwidth) || (x[j] + rwidth[j]) <= x || y[j] >= (x + rheight) || (y[j] + rheight[j]) <= y<br />and prefer to use IloBox only to have a stronger filtering and avoid posting n^2 non overlapping constraints.

Thank you very much for the redundant constraints! It will probably help a lot.

Pierre.



#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[JFPuget said:]

You can use capacity constraints as redundant constraints.

Let's think of x as the time axis and y as a capacity.

A rectangle is an activity, whose length on the x axis (width) is the duration, and whose length on the y axis (height) is the capacity.

The enclosing rectangle is a finite capacity resource.  Its width is the time horizon, and its height is the capacity of the resource.

So, you create one activity per rectangle, whose start variable is the x corrdinate of the left side of the rectangle, whole duration is the x-size of the rectangle.  This activity consumes the height of the rectangle of theresource.

You should also state the constraints obtained by interverting the x and y axis.

These extra constraints are useful if the problem is tight.
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[pierre schaus said:]

Thank you Mr Puget,

My problem is quite tight (large squares) so  cumulative constraints should indeed have a positive effect.
By capacity constraints, do you mean using an IloDiscreteRessource from Ilog Scheduler ?

Pierre.

#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[boergi said:]

Hello,

Interesting topic!

@Pierre: Did you try to use IloDiscreteRessource from Ilog Scheduler?

I was wondering how the channel between the redundant constraints can be established? I am familiar with Ilog Solver but never used Ilog Scheduler. Reading the documentation of Ilog Scheduler, I came up with an idea (didnt try it yet):


x ... coordinate of the rectangle (IloIntVar)
jobX ... activity representing the rectangle (IloActivity)



channel constraint: model.add(x == jobX.getStartExpr())

@all: Does this work?

Cheers!
#CPOptimizer
#DecisionOptimization