MatMod logo

Pack Umbrellas (umbrella)

Run LPL Code  ,  PDF Document


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.


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 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;; 
  Write('makespan %3.1f' n', max{i} (x+a/2) - min{i} (x-a/2)); 
  parameter b{i}; 
  {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); 


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.


Figure 2: A solution with 15 umbrellas


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


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


[1]   MatMod. Homepage for Learning Mathematical Modeling :

[2]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version.