MatMod logo

Pack Umbrellas (umbrella)

Run LPL Code  ,  PDF Document

Problem

A number n of “umbrellas” () (2-dimensional spanned “umbrellas”) is given. Their heights can be modified arbitrarily. The problem is to push these umbrellas together as closely as possible such that the total span is as minimal as possible. A small example with four umbrellas is given in Figure 1 with their widths 6, 8, 11, and 22. The idea of this model is from Ivo Blöchliger.


PIC

Figure 1: Solution of four Umbrellas


Modeling Steps

Define the umbrellas as a set i,j ∈{1,,n}. The spanning width of an umbrella is given as ai.

  1. Introduce a variable xi 0 for each umbrella i defining the position.

  2. For every pair (i,j) of umbrellas either i is beneath j or j is beneath i. Hence, there must be enough width for either case :

    |xj - xi| ≥ min(ai∕2,aj∕2 )  forall i > j ” class=”math-display” src=”/blog/wp-content/uploads/umbrella0x.svg”/></div>
</li>
<li class=

    Minimize the total spanning width, that is :

    min  (maxi (xi + ai∕2) - mini (xi - ai∕2))
  3. After the solution we calibrate the positions such that the smallest xi ai2 is zero:

    x  = x  - d   ,  d = min (x) - a  ∕2   i i      i   i argminixi
  4. To draw the solution, we make the height dependent of the width, the wider an umbrella the larger its height. Hence, the umbrellas are sorted according to their width. The sorted permutation is given in bi.

Listing 1: The Complete Model implemented in LPL [2]

model umbrella "Pack Umbrellas"; 
  --set i,j:=1..4; parameter a{i}:=[6,8,11,22]; 
  set i,j := 1..15; 
  parameter a{i}:=Trunc(Rnd(2,30)); 
  variable x{i} [0..50]; 
  constraint A{i,j|i<j}: x[j]-x[i] >= Min(a[i]/2,a[j]/2) or 
                         x[i]-x[j] >= Min(a[i]/2,a[j]/2); 
  minimize obj: max{i} (x+a/2) - min{i} (x-a/2); 
  parameter d:=min{i}x-a[argmin{i} x]/2;; 
  x{i}:=x-d; 
  Write('makespan %3.1f' n', max{i} (x+a/2) - min{i} (x-a/2)); 
  parameter b{i}; 
  Sort(a,b,1); 
  Draw.Scale(15,20); 
  Draw.DefFont('Verdana',12); 
  {i} Draw.Text(a[b]&'', x[b],i-.1); 
  {i} Draw.Line(x[b]-a[b]/2,i,x[b]+a[b]/2,i); 
  {i} Draw.Line(x[b],i,x[b],#i+1); 
  {i} Draw.Text(Round(x[b],-1)&'',x[b],#i+1.5); 
end

Solution

The solution for a problem with n = 15 is given in Figure 2. The total width is 54.5. It is difficult to solve larger problems using this modeling approach. I have no idea whether this problem is easy or not. Maybe their exists a polynomial algorithm to find a solution.


PIC

Figure 2: A solution with 15 umbrellas


Questions

  1. Find a polynomial algorithm for the problem or show that none exists.

Answers

  1. Sorry, I do not have the answer. I would be glad to hear the answer from a reader.

References

[1]   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

[2]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.