Exact Methods for Recursive Circle Packing
Ambros Gleixner Stephen Maher Benjamin Müller João Pedro Pedroso


Ambros Gleixner

           Stephen J. Maher

           Benjamin Müller

           João Pedro Pedroso

Exact Methods for Recursive Circle Packing
This work has been supported by the Research Campus MODAL
  Mathematical Optimization and Data Analysis Laboratories funded by the
  Federal Ministry of Education and Research (BMBF Grant 05M14ZAM).  All
  responsibilty for the content of this publication is assumed by the authors.
17-07
January
2018
This report has been published in Annals of Operations Research. Please cite as:
 Gleixner et al., Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition. Annals of Operations Research, 2018, http://dx.doi.org/10.1007/s10479-018-3115-5DOI:10.1007/s10479-018-3115-5





Exact Methods for Recursive Circle Packing
    Ambros GleixnerZuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany, 
   Stephen J. Maher^*
   Benjamin Müller^*
   João Pedro PedrosoFaculdade de Ciências, Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal, 
    December 30, 2023
===========================================================================================================================================================================================================================================





  Packing rings into a minimum number of rectangles is an optimization problem
which appears naturally in the logistics operations of the tube industry. It
encompasses two major difficulties, namely the positioning of rings in
rectangles and the recursive packing of rings into other rings. This problem is
known as the Recursive Circle Packing Problem ().
We present the first dedicated method for solving that provides strong dual bounds based on an exact Dantzig-Wolfe
reformulation of a nonconvex mixed-integer nonlinear programming
formulation. The key idea of this reformulation is to break symmetry on each
recursion level by enumerating one-level packings, i.e., packings of circles
into other circles, and by dynamically generating packings of circles into
rectangles.
We use column generation techniques to design a “price-and-verify” algorithm
that solves this reformulation to global optimality.
Extensive computational experiments on a large test set show that
our method not only computes tight dual bounds, but often produces primal
solutions better than those computed by heuristics from the literature.
 



§ INTRODUCTION


Packing problems appear naturally in a wide range of real-world
applications. They contain two major difficulties. First, complex geometric
objects need to be selected, grouped, and packed into other objects, e.g.,
warehouses, containers, or parcels. Second, these objects need to be packed in a
dense, non-overlapping way and, depending on the application, respect some
physical constraints. Modeling packing problems mathematically often leads to
nonconvex mixed-integer nonlinear programs (). Solving them to global
optimality is a challenging task for state-of-the-art solvers.
In this paper, we will study exact algorithms for solving a particularly complex
version involving the recursive packing of 2-dimensional rings.
This variant has real-world applications in the tube industry.



The Recursive Circle Packing Problem () has been introduced recently by
Pedroso et al. <cit.>. The objective of is to select a minimum
number of rectangles of the same size such that a given set of rings can be
packed into these rectangles in a non-overlapping way. A ring is characterized
by an internal and an external radius. Rings can be put recursively into larger
ones or directly into a rectangle. A set of rings packed into a rectangle is
called a feasible packing if and only if all rings lie within the
boundary of the rectangle and do not intersect each
other. Figure <ref> gives two examples of a feasible packing.


Pedroso et al. <cit.> present a nonconvex formulation for
. The key idea of the developed is to use binary variables in order
to indicate whether a ring is packed inside another larger ring or directly into
a rectangle. Due to a large number of binary variables and nonconvex quadratic
constraints, the model is not of practical relevance and can only be used to
solve very small instances. However, the authors present a well-performing local
search heuristic to find good feasible solutions.



The purpose of this article is to present the first exact column generation
algorithm for based on a Dantzig-Wolfe decomposition, for which, so far,
only heuristics exist. The new method is able to solve small- and medium-size
instances to global optimality and computes good feasible solutions
  and tight dual bounds for larger ones.
We first develop a reformulation, which is similar to the classical
reformulation for the Cutting Stock Problem <cit.>, however,
featuring nonlinear and nonconvex sub-problems. This formulation breaks the
symmetry between equivalent rectangles.
As a second step, we combine this reformulation with an enumeration scheme
for patterns that are characterized by rings packed inside other rings. Such
patterns only allow for a one-level recursion and break the symmetry between
rings with the same internal and external radius in each rectangle.
Finally, we present how to solve the resulting reformulation with a
column generation algorithm.

Finally, we present how to solve the resulting reformulation with a specialized
column generation algorithm that we call price-and-verify. The
algorithm does not only generate new patterns but also verifies
patterns that are found during the enumeration scheme dynamically, i.e., only when required for
solving the continuous relaxation of the reformulation.



§ BACKGROUND


The problem of finding dense packings of geometric objects has a rich history
that goes back to Kepler's Conjecture in 1611, which has been proven recently by
Hales et al. <cit.>. Packing identical or diverse objects into
different geometries like circles, rectangles, and polygons remains a relevant
topic and has been the focus of much research during the last decades.
The survey by Hifi and M'Hallah <cit.> reviews the most relevant
results for packing 2- and 3-dimensional spheres into regions in the Euclidean
space. Applications, heuristics, and exact strategies of packing arbitrarily
sized circles into a container are presented by Castillo et
al. <cit.>.
Costa et al. <cit.> use a spatial branch-and-bound algorithm to find
good feasible solutions for the case of packing identical circles. They propose
different symmetry-breaking constraints to tighten the convex relaxation and
improve the success rate of local nonlinear programming algorithms.

Closely related to packing problems are plate-cutting problems, in which convex
objects, e.g., circles, rectangles, or polygons, are cut from different convex
geometries <cit.>. Modeling these problems leads typically to nonlinear
programs, for which exact mathematical programming solutions are described by
Kallrath <cit.>.
Minimizing the volume of a box for an overlap-free placement of ellipsoids was
studied by Kallrath <cit.>. His closed, non-convex nonlinear
programming formulation uses the entries of the rotation matrix as variables and
can be used to get feasible solutions for instances with up to 100 ellipsoids.

The general type of the problem finds application in the tube industry, where
shipping costs represent a large fraction of the total costs of product
delivery. Tubes will be cut to the same length of the container in which they
may be shipped. In order to reduce idle space inside containers, smaller tubes
might be placed inside larger ones. Packing tubes as densely as possible reduces
the total number of containers needed to deliver all tubes and thus has a large
impact on the total cost.

is a generalization of the well-known,
𝒩𝒫-hard <cit.> Circle Packing Problem () and
therefore is also 𝒩𝒫-hard. Reducing an instance of to can
be done by setting all internal radii to zero, i.e., by forbidding to pack rings
into larger rings. Typically, problems like contain multiple sources of
symmetry. Any permutation of rectangles, i.e., relabeling rectangles,
constitutes an equivalent solution to . Even worse, there is also
considerable symmetry inside a rectangle. First, rotating or reflecting a
rectangle gives an equivalent rectangle since both contain the same set of
rings. Second, two rings with same internal and external radius can be exchanged
arbitrarily inside a rectangle, again resulting in an equivalent rectangle
packing.

One possible way to break the symmetry of is to add symmetry-breaking
constraints, which have been frequently used for scheduling problems, e.g.,
lot-sizing problems <cit.>.
An alternative approach is the use of decomposition techniques. These techniques
aggregate identical sub-problems in order to reduce symmetry and typically
strengthen the relaxation of the initial formulation. A well-known decomposition
technique is the Dantzig-Wolfe decomposition <cit.>. It is an
algorithm to decompose Linear Programs () into a master and, in general,
several sub-problems. Column generation is used with this decomposition to
improve the solvability of large-scale linear programs. Embedded in a
branch-and-bound algorithm, it can be used to solve mixed-integer linear
programs (), e.g., bin packing <cit.>, two dimensional bin
packing <cit.>, cutting stock <cit.>,
multi-stage cutting stock <cit.>, and many other problems.
Fortz et al. <cit.> applied a Dantzig-Wolfe decomposition to a
stochastic network design problem with a convex nonlinear objective function.
While most implementations of Dantzig-Wolfe are problem-specific, a number of
frameworks have been implemented for automatically applying a Dantzig-Wolfe
decomposition to a compact formulation,
see <cit.>.

In this paper we apply a Dantzig-Wolfe decomposition to an formulation of
and present the first exact solution method that is able to solve
practically relevant instances.
The rest of the paper is organized as follows. In Section <ref>,
we introduce basic notation and discuss the limitations of a compact formulation for . Section <ref> presents a first Dantzig-Wolfe
decomposition of the formulation. After introducing the concept of
circular and rectangular patterns, we extend the formulation from
Section <ref> in Section <ref> to our final formulation
for . Afterwards, we present a column generation algorithm to solve this
formulation, which uses an enumeration scheme introduced in
Section <ref>. Section <ref> shows how
to prove valid dual and primal bounds, even when difficult sub-problems cannot
be solved to optimality. Finally, in Section <ref>, we
analyze the performance of our method on a large test set containing 800
synthetic instances and nine real-world instances from the tube
industry. Section <ref> gives concluding remarks.




§ PROBLEM STATEMENT



Consider a set := {1, …, } for 
different types of rings and an infinite number of rectangles. In what follows,
we consider each rectangle to be of size ∈_+ times
∈_+ and to be placed in the Euclidean plane such that the corners
are (0,0), (0,), (,0), and (, ).

For each ring type t ∈ we are given an internal radius
_t ∈_+ and an external radius _t ∈_+ such that

    _t ≤_t ≤min{,}.

Also, each ring type t ∈ has a demand _t ∈_+.
We assume without loss of generality that  is sorted such that
_1 ≤…≤_. To simplify the notation, we denote by
:= ∑_t ∈_t the total number of individual
rings and denote by := {1, …, } the corresponding index
set. The function : → maps each individual
ring to its corresponding type.
By a slight abuse of notation, we identify with _i and _i the
internal and external radius of ring i ∈, i.e.,
_i = _(i) and _i = _(i).

The task in is to pack all rings in  into the smallest number of
rectangles. Rings must lie within the boundary of a rectangle and must not
intersect each other.
More precisely, a feasible solution to can be encoded as a 3-tuple
(c,x,y) ∈{1,…,k}^n ×^n ×^n where (x_i,y_i) denotes
the center of ring i ∈ inside rectangle c_i ∈{1,…,k},
and an upper bound on the number of rectangles needed is given by k ≤ n. The
number of used rectangles is equal to the cardinality of
{c_1,…,c_}, i.e., the number of distinct integer values. Rings
must not intersect the boundary of the rectangle, i.e.,

    _i ≤ x_i ≤ - _i      i ∈, 
    _i ≤ y_i ≤ - _i     i ∈.

For a given 3-tuple (c,x,y) we denote by

    A(i) := {(x̃, ỹ) ∈^2 |_i < x̃-x_iỹ-y_i_2 < _i }

the area occupied by ring i in rectangle c_i. The non-overlapping condition
between different rings is equivalent to

    A(i) ∩ A(j) = ∅

for all i ≠ j with c_i = c_j.

can be equivalently formulated as an , see Pedroso et
al. <cit.>. The formulation consists of four different types of
variables:


  * (x_i,y_i) ∈^2, the center of ring i ∈,

  * z_c ∈{0,1}, a decision variable whether rectangle c ∈{1,…,k} is used,

  * w_i,c∈{0,1}, a decision variable whether ring i is directly placed in rectangle c, and

  * u_i,j∈{0,1}, a decision variable whether ring i is directly placed in ring j.

We say that a ring i ∈ is directly placed in another ring
j or rectangle c if it is not contained in another, larger ring inside j
or c, respectively. Condition (<ref>) can be modeled by the
constraints

    x_iy_i - x_jy_j_2^2    ≥ (_i + _j)^2(w_i,c + w_j,c -1)        i, j ∈ : i ≠ j,   c ∈{1,…,k}, 
          x_iy_i - x_jy_j_2^2    ≥ (_i + _j)^2(u_i,h + u_j,h -1)        i,j,h ∈: i ≠ j ∧ i ≠ h ∧ j ≠ h, 
          x_iy_i - x_jy_j_2    ≤_j - _i + M_i,j (1-u_i,j)        i, j ∈ : _i ≤_j,

which are nonconvex nonlinear inequality
constraints. Inequality (<ref>) guarantees that no two
rings i,j ∈ overlap when they are directly placed inside the same
rectangle c, i.e., if w_i,c = w_j,c = 1. Similarly,
inequality (<ref>) ensures that no two rings intersect
inside another ring.
Constraint (<ref>) ensures that if u_i,j = 1, then ring
i is directly placed inside j and does not intersect its
boundary. Otherwise, the constraint is disabled. An appropriate value for
M_i,j to guarantee that the conditions of (<ref>) are
satisfied is

    M_i,j := √(( - _i - _j)^2 + ( - _i - _j)^2),

which is the maximum distance between two rings i,j ∈ in a 
times  rectangle that do not overlap.

The full model for reads as follows:
 

    min    ∑_c = 1^k z_c 
          s.t.      w_i,c≤ z_c        i ∈,   c ∈{1,…,k}
             ∑_c =1^k w_i,c + ∑_j ∈ u_i,j = 1        i ∈
             (<ref>), (<ref>), (<ref>), (<ref>), (<ref>)
              (x_i,y_i) ∈^2        i ∈
              z_c ∈{0,1}       c ∈{1,…,k}
              w_i,c∈{0,1}       i ∈,   c ∈{1,…,k}
              u_i,j∈{0,1}       i,j ∈: i ≠ j


Finally, the objective function (<ref>) minimizes the total number
of rectangles used. Constraint (<ref>) guarantees that we can pack
a ring inside a rectangle if and only if the rectangle is used. Each ring needs
to be packed into another ring or a rectangle, which is ensured
by (<ref>).

Formulation (<ref>) can be adapted for maximizing the load of a
  single rectangle. Roughly speaking, we need to fix z_c = 0 for each c > 1
  and replace each variable w_i,c by w_i, which then turns into an
  indicator whether ring i ∈ has been packed or not. The objective
  function (<ref>) changes to

    max ∑_i ∈α_i w_i,

where α_i ∈_+ is a non-negative weight for each ring i∈.


Unfortunately, general solvers require a considerable amount of time to
solve Formulation (<ref>) because it contains a large number of
variables, many nonconvex constraints, and much symmetry.
Even the smallest instance of our test set, containing 54 individual rings,
could not be solved within several hours by  3.2.1 <cit.> nor by
 16.8.24 <cit.>. A common method used to improve
the solvability of geometric packing problems is to add symmetry breaking
constraints. However, strengthening (<ref>) by adding the constraints

    z_c       ≥ z_c+1       c ∈{1,…,k-1}, 
           u_i,j   ≥ u_h,j       j ∈,   i < h: (i) = (h),  and
           w_i,c   ≥ w_j,c       c ∈{1,…,k},   i < j: (i) = (j),

which break symmetry by ordering rectangles and rings of the same type, had no
impact on the solvability of .

The reason for the poor performance is that (<ref>) contains
O(kn^2 + n^3) many difficult nonconvex constraints of the
form (<ref>) and (<ref>). Even worse,
the binary variables in those constraints appear with a big-M, which is known to
result in weak linear programming relaxations.
Another difficulty is the symmetry in the model that is not eliminated
by (<ref>), (<ref>),
or (<ref>). Each reflection or rotation of a feasible packing
of a rectangle and rings inside a ring yields another, equivalent, solution.

In the following, we present two formulations based on a Dantzig-Wolfe
decomposition to break the remaining symmetry in (<ref>). The first
formulation breaks the symmetry between rectangles. The second is an extension
of the first one and additionally breaks symmetry between rings of the same type
inside the rectangles and other rings.

To overcome the difficulty of the exponential number of variables in the
Dantzig-Wolfe decompositions, we use column generation to solve the continuous
relaxations of both formulations. The pricing problem of the first formulation
is the maximization version of (<ref>). The pricing problem of the
second formulation is a maximization version of the .
 


§ CUTTING STOCK REFORMULATION


Dantzig-Wolfe decomposition <cit.> is a classic solution approach
for structured . It can be used to decompose an into a master
  problem and one or several sub-problems. Advantages of the
decomposition are that it yields stronger relaxations if the sub-problems are
nonconvex and can aggregate equivalent sub-problems to reduce
symmetries <cit.>.

In this section, we apply a Dantzig-Wolfe decomposition to (<ref>) and
obtain a reformulation that is similar to the one of the one-dimensional Cutting
Stock Problem <cit.>. The key idea is to reformulate in order to
not assign rings explicitly to rectangles, but rather choose a set of feasible
rectangle packings to cover the demand for each ring type. The resulting
reformulation is a pure integer program () containing exponentially many
variables. We solve this reformulation via column generation.

We call a vector F∈_+^ packable
if it is possible to pack F_t many rings for all types t ∈ together (and thus a
total number of ∑_t ∈F_t many rings) into a × rectangle.
A packable F∈_+^ corresponds to a feasible solution
of (<ref>) when considering only a single rectangle.
Denote by

    := { F ∈_+^  :   F  is packable}

the set of all feasible packings of rings into a rectangle. Note that
without loss of generality, we can bound F_t by the demand _t for
each t ∈. After applying Dantzig-Wolfe decomposition
to (<ref>), we obtain the following formulation, ():
 

    min    ∑_F ∈ z_F 
          s.t.     ∑_F ∈ F_t · z_F ≥_t        t ∈
              z_F ∈_+       F ∈


This formulation contains an exponential number of integer variables with
respect to . Each variable z_F counts how often F is
chosen. Minimizing the total number of rectangles is equivalent
to (<ref>). Inequality (<ref>) ensures that
each ring of type t is packed at least _t many times.
In the following, we call the relaxation of () for
⊆ the restricted master problem of ().

An advantage of (<ref>) is that we do not explicitly assign rings to
positions inside some rectangles, like in (<ref>), nor distinguish
between rings of the same type. This breaks symmetry that arises from simply
permuting rectangles.  However,  is a priori unknown and its size is
exponential in the input size of an instance.


A column generation algorithm is used to solve the LP relaxation of () by
iteratively updating () with improving columns corresponding to feasible
rectangular packings.  A feasible rectangular packing F ∈ is an improving
column if the corresponding constraint

    ∑_t ∈ F_t π^*_t ≤ 1

is violated by the dual solution π^* of the restricted master problem
(). The relaxation of () is solved to optimality when
∑_t ∈ F_t π^*_t ≤ 1 holds for all F ∈ \. Otherwise, an
F ∈ \ with ∑_t ∈ F_t π^*_t > 1 is
added to  and the process iterates until () is solved to
optimality.

The most violated dual constraint is found by solving

    min{ 1 - ∑_t ∈π^*_t F_t : F ∈_+^,   F  is packable}.

This problem is a maximization variant of for which we need to find a
subset of rings such that they can be packed into a single rectangle, see
Remark <ref>. The objective gain of each ring of type t is
exactly π^*_t. The relaxation of (<ref>) is solved to
optimality if the solution value of (<ref>) is
non-negative. Otherwise, we find an improving column that, after it has been
added, might decrease the objective value of the restricted master problem
().

As explained in Remark <ref>, (<ref>) can be
modeled as a nonconvex that contains the selection and positioning of
rings in a rectangle. Unfortunately, solving this problem is very difficult for
a general solver. In our experiments none of the resulting pricing
problems (<ref>) could be solved to optimality
or even generate an improving column for () in two hours. For this
reason, Formulation (<ref>) is not suitable for solving to
global optimality.
 


§ PATTERN-BASED DANTZIG-WOLFE DECOMPOSITION USING ONE-LEVEL PACKINGS



The main drawback of (<ref>) is that the resulting pricing
problems (<ref>) are intractable. This is due to two major
difficulties, i) the positioning of rings inside a rectangle and ii) the
combinatorial decisions of how to put rings into other rings. Together, they
make the sub-problems much more difficult to solve than the master
problem. The recursive decisions of packing rings into each other introduces
much symmetry to (<ref>). Rings of the same type, and all rings
packed inside those, can be swapped inside a rectangle and yield an equivalent
solution. This symmetry appears in each recursion level of the sub-problems. See
Figure <ref> for an example of this kind of symmetry.



The main idea of the following reformulation is to break this type of symmetry
and shift the recursive decisions from the sub-problem to the master
problem. This helps balance the complexity of both problems, which is crucial when
using a column generation algorithm.

In the following, we introduce the concept of circular and
rectangular patterns. These patterns describe possible packings of
circles into rings or rectangles. The circles act like
placeholders. Specifically, the circles just describe what type of rings might
be placed in the circles, but not how these rings are filled with other
rings. After choosing one pattern we are able to choose other patterns that fit
into the circles of the selected one. The recursive part of boils down to
a counting problem of patterns and minimizing the total number of rectangles.




 §.§ Circular Patterns



A circle of type t ∈ is a ring with external radius
_t and inner radius _t = 0. This means that neither circles nor
rings can be put into a circle.
Similarly to the definition of elements in , we call a tuple (t,P)∈×_+^ a circular pattern if it is possible to
pack P_1 many circles of type 1, P_2 many circles of type 2, …,
P_ many circles of type  into a larger ring of type t.
As an example, (3,(2,1,0)) is a circular pattern with an outer ring
of type three which contains two circles with external radius _1 and one
circle with radius _2. Since _3 can not be pack within any ring, the final index will
always be 0.  However, it is included in the definition of circular patterns for
completeness.
Figure <ref> shows all possible packings for three different ring
types.



Using the definition of circular patterns we decompose a packing of rings into a
ring R. Each ring that is directly placed into R, i.e., is not contained in
another larger ring, is replaced by a circle with the same external radius. We
apply the decomposition to each replaced ring recursively. As a result, ring R
decomposes into a set of circular patterns. Starting from these circular
patterns, we can reconstruct R by recursively replacing circles in a pattern
with other circular patterns. We denote by

    := { (t,P) ∈×_+^| (t,P)  is a circular pattern}

the set of all possible circular patterns. The previously described
decomposition shows that any recursive packing of rings can be constructed by
using circular patterns of .

In general, the cardinality of  is exponential in  and depends on
the internal and external radii of the rings. For example, increasing the inner
radius of the largest ring will lead to many more possibilities to pack circles
into this ring. In contrast, decreasing external radii results in fewer circular
patterns.

Figure <ref> shows that there are circular patterns that are
dominated by others, e.g., the third pattern dominates second one. Using
dominated circular patterns would leave some unnecessary free space in some
rectangles, which can be avoided in an optimal solution. In
Section <ref> we discuss this domination relation and
present an algorithm to compute all non-dominated circular patterns.




 §.§ Rectangular Patterns



In the following reformulation of , we use circular patterns to shift the
decisions of how to put rings into other rings to the master problem. Similar to
a circular pattern, we call P ∈_+^ a rectangular pattern
if and only if P_t many circles with radius _t for each
t ∈ can be packed together into a rectangle of size  times
. Let

    := { P ∈_+^| P  is a rectangular pattern}

be the set of all rectangular patterns. As in Formulation (<ref>),
only the number of packed circles matters, not their position in the rectangular
pattern.



In contrast to verifying if (t,P) ∈×_+^ is a
circular pattern, checking whether P ∈_+^ is a rectangular
pattern—a classical —can be much more difficult. Typically, many more
circles fit into a rectangle than into a ring.  This results in a large number
of circles that need to be considered in a verification problem, which is in
practice difficult to solve.



 §.§ Exploiting Recursion



Using the circle and rectangle patterns described above, we develop a
pattern-based Dantzig-Wolfe decomposition for with nonlinear sub-problems.
Instead of placing rings explicitly into each other, we use patterns to remodel
the recursive part. The key idea is that circles, inside rectangular or circular
patterns, are replaced by circular patterns with the same external radius. These
circular patterns contain circles that can be replaced by other circular
patterns.
More precisely, after choosing a rectangular pattern P ∈, it is possible
to choose P_t circular patterns of the form (t,P') ∈, which can be
placed into P. Again, for each P' we can choose P'_t' many circular
patterns of the form (t', P”), which can be placed in P'. This process can
continue until the smallest packable circle is considered. The recursive
structure of the —the placement of rings into other rings—is modeled by
counting the number of used rectangular and circular patterns.

Figure <ref> illustrates this idea. A circular pattern
replaces a circle if there is an arrow from the pattern to the circle. Each
circle of a pattern can be used as often as the pattern is used. It follows that
the number of outgoing edges of a circular pattern is equal to the number of
uses of the pattern. The combinatorial part of reduces to adding edges
from circular patterns to circles.



Following this idea, we introduce integer variables


  * z_C∈_+ for each circular pattern C ∈ and

  * z_P∈_+ for each rectangular P ∈

in order to count the number of used circular and rectangular patterns (in the
pattern-based formulation). We reformulate by the following formulation (), which is similar to the multi-stage cutting stock
formulation that has been presented by Muter et al. <cit.>.
 

    min∑_P ∈ z_P    
          s.t.∑_C = (t,P) ∈ z_C    ≥_t        t ∈
          ∑_P ∈ P_t · z_P + ∑_C = (t',P) ∈ P_t · z_C    ≥∑_C = (t,P) ∈ z_C        t ∈
           z_C    ∈_+       C ∈
           z_P    ∈_+       P ∈


Objective (<ref>) minimizes the total number of used
rectangles. Constraint (<ref>) ensures that the demand for
each ring type is satisfied. The recursive decisions how to place rings into
each other are implicitly modeled by (<ref>).
Each selection of a pattern P ∈ or (t',P) ∈ allows us to choose
P_t circular patterns of the type t.
Note that at least one rectangular pattern needs to be selected before circular
patterns can be packed. This is true because the largest ring only fits into a
rectangular pattern.
To aid in understanding the formulation of (), a small
example based on the circular and rectangular patterns in Figures
<ref> and <ref> respectively is presented in
Example <ref>.

Let {C_1,…,C_7} be the set of circular patterns of
  Figure <ref> and {P_1,P_2,P_3} be the subset of rectangular
  patterns of Figure <ref>. The patterns are labeled from left
  to right. Problem (<ref>) then reads as
  
  
    min z_P_1 + z_P_2 + z_P_3
    s.t.       z_C_1   ≥ D_1 
                        z_C_2 + z_C_3   ≥ D_2 
                        z_C_4 + z_C_5 + z_C_6 + z_C_7   ≥ D_3 
                        z_C_3 + z_C_5 + 2 z_C_6 + 9 z_P_1 + 4 z_P_2 + 2 z_P_3   ≥ z_C_1
                        z_C_7 + 5 z_P_3   ≥ z_C_2 + z_C_3
                        z_P_1 + 2 z_P_2   ≥ z_C_4 + z_C_5 + z_C_6 + z_C_7
                        z_C_i   ∈_+   i ∈{1,…,7}
                        z_P_i   ∈_+   i ∈{1,2,3}

  
  Constraints (<ref>)–(<ref>) ensure that
  the demand for each ring type is satisfied. The left-hand side of constraints
  (<ref>)–(<ref>) only contain columns
  corresponding to the circular patterns of ring type 1 to 3 respectively. The
  constraints (<ref>)–(<ref>)
  model the recursive structure of the problem. Columns corresponding to
  circular patterns for ring types 1 to 3 are observed on the right-hand side of
  constraints (<ref>)–(<ref>)
  respectively. The left-hand side of constraints
  (<ref>)–(<ref>) contain columns
  corresponding to rectangular and circular patterns that pack the ring type
  represented on the right-hand side of the respective constraints.


A drawback of (<ref>) is the exponential number of rectangular and
circular pattern variables.
To address this difficulty, we develop a column enumeration algorithm to compute
all (relevant) circular patterns used in (<ref>), which is presented
in Section <ref>.
We observed in our experiments that for many instances this algorithm
successfully enumerates all circular patterns in a reasonable amount of time.

Since the size of the rectangles is much larger than the external radii ,
it is intractable to enumerate all rectangular patterns. To overcome this
difficulty, we use a column generation approach to solve the relaxation
of (<ref>) that dynamically generates rectangular patterns
variables. We call the relaxation of (') the restricted master
problem of (<ref>) for a subset of rectangular patterns '
⊆. In order to find an improving column for ('), we solve
a weighted for a single rectangle.

More precisely, let λ∈_+^ be the non-negative vector of
dual multipliers for Constraints (<ref>) after solving the
relaxation of (') for the current set of rectangular patterns
'⊂. To compute a rectangular pattern with negative reduced cost
we solve

    min_P ∈ \ '{1 - ∑_t ∈λ_t P_t},

which can be modeled as a weighted for a single rectangle. Let P^* be an
optimal solution to (<ref>).  If 1 - ∑_t ∈λ_t P^*_t is negative, then P^* is an improving rectangular pattern,
whose corresponding variable needs to be added to the restricted master problem
of ('). Otherwise, the relaxation of (<ref>) is solved
to optimality.

The pricing problem is 𝒩𝒫-hard <cit.> and difficult to
solve in practice. The number of variables in this problem depends on the number
of different ring types  and on the demand vector . When
solving (<ref>) we need to consider the index set of
individual circles

    { i^1_1, …, i^1__1, i^2_1, …, i^2__2, …, i^_1, …, i^__}

containing _t indices that correspond to circles with radius _t
for each t ∈. The number of copies for type t can be reduced to
min{_t, π (_t)^2/}, which is
an upper bound on the number of rings of type t in a  times 
rectangle.
For simplicity, denote with  the index set of all
individual circles.  Let _i be the external radius and (i) the
type of circle i ∈. The circle packing problem formulation
of (<ref>) reads then as
 

    min     1 - ∑_i ∈λ_(i) z_i 
    s.t.      x_iy_i - x_jy_j_2^2    ≥ (_i + _j)^2(z_i + z_j -1)        i, j ∈ : i ≠ j 
          _i    ≤ x_i ≤ - _i        i ∈
          _i    ≤ y_i ≤ - _i        i ∈
           z_i    ∈{0,1}       i ∈


where (x_i,y_i) is the center of circle i ∈ and z_i the
decision variable whether circle i has been packed, i.e., z_i = 1.

After solving the continuous relaxation of (<ref>), it might happen
that z_P^* is fractional for a rectangular pattern P ∈'. In this case
branching is required to ensure global optimality.
A general branching strategy has been introduced by <cit.>, which
has been successfully used in a branch-and-price algorithm for the
one-dimensional cutting stock problem <cit.>. This branching rule can
be applied when solving (<ref>), however, it increases
the complexity of the pricing problems (<ref>).
Since (<ref>) is very difficult to solve—the vast majority of
pricing problems cannot be solved to optimality in the root node—employing
branch-and-price is deemed impractical. As such, Section <ref> presents a price-and-verify algorithm,
which builds upon price-and-branch, as a practical method for
solving the .  With techniques discussed in
  Section <ref> this results in an algorithm that is able to
  prove global optimality for many instances.




 §.§ Strength of Dantzig-Wolfe reformulations



In the following, we show that the two presented formulations (<ref>)
and (<ref>) provide the same bound.

  Let (DW) and (PDW)
  be the value of the relaxation of (<ref>)
  and (<ref>), respectively. Then (PDW) = (DW).


  To show the equality of the bounds, we consider an “extended”
  Dantzig-Wolfe reformulation.  As a generalization of the variables z_F from
  (<ref>), where F∈ encodes a rectangle of recursively packable
  rings, and z_P from (<ref>), where P∈ encodes
  a rectangular pattern,
  we introduce variables for “mixed” rectangles that may contain both rings and circles. Let z_(F,P) be the number of such
  “mixed” rectangles, and denote with
  
    = { (F,P) ∈_+^×_+^ : (F,P)  is packable }

  the set of mixed rectangles.  Here, (F,P) is packable if
  F_t rings of type t and P_t circles of type t can be packed into one
  rectangle without overlap, collectively over all t. A ring may contain smaller rings and circles, but
  circles cover their full interior, see Figure <ref> for an
  example.

  

  Then define the  
    
    min∑_(F,P) ∈ z_(F,P)   
          s.t.∑_(F,P) ∈ F_t · z_(F,P) + ∑_C = (t,P) ∈ z_C    ≥_t        t ∈
          ∑_(F,P) ∈ P_t · z_(F,P) + ∑_C ∈ P_t · z_C    ≥∑_C = (t,P) ∈ z_C        t ∈
           z_C    ≥ 0        C ∈
           z_(F,P)   ≥ 0        (F,P) ∈

  
  and let Z^* be its optimal objective value. By construction,
  (<ref>) contains the feasible solutions of (<ref>)
  (setting z_C=0 and z_(F,P)=0 for all P≠0) and (<ref>)
  (setting z_(F,P)=0 for all F≠0). Hence, Z^* ≤(DW) and Z^*
  ≤(PDW). We prove the converse by optimality-preserving exchange
  arguments. First, given a solution with rectangles that contain rings, these
  rings can gradually be replaced by circles and circular patterns. Second,
  given a solution with rectangles that contain circles, we are guaranteed to
  find a circular pattern that can take its place. Formally, the proof reads as
  follows.

  1. Suppose (PDW) > Z^* and let z^* be an optimal solution to
  (<ref>) such that the total number of rings used in the rectangles
  of the support,
  
    μ(z) = ∑_ (F,P) ∈∑_t=1^ F_t · z_(F,P)

  is minimal.  By assumption, μ(z^*) > 0, and we can choose (F̃, P̃) and t̃ such that z^*_(F̃,P̃) >0 and F̃_t̃≥ 1.  Choose ring type t̃ to have smallest external radius _t̃. Then this ring can only contain circles, and with these circles it forms a circular pattern C̃ = (t̃, P') ∈. Replacing the ring of type t̃ by a circle with same external radius
  gives the packable tuple (F̂, P̂) := (F̃ - e_t̃, P̃ + e_t̃).  Then
  define a new solution ẑ via
  
    ẑ_(F,P)   := 
        0     if  (F,P) = (F̃, P̃),
    
        z^*_(F̂,P̂) + z^*_(F̃,P̃)    if  (F,P) = (F̂, P̂),
    
        z^*_(F,P)    otherwise,
        for all (F,P) ∈, andẑ_C   := 
        z^*_C̃ + z^*_(F̃,P̃)    if  C = C̃,
    
        z^*_C    otherwise,

  for all C ∈.  By construction, ẑ is feasible for
  (<ref>) and has identical objective function value.  However,
  μ(ẑ) = μ(z^*) - z^*_(F̃,P̃) < μ(z^*), contradicting
  the minimality assumption.

  2. Suppose (DW) > Z^* and let z^* be an optimal solution to
  (<ref>) such that ν(z) = ∑_C ∈ z_C is minimal.  By
  assumption, ν(z^*) > 0; otherwise, z^* could be transformed into an
  optimal solution of (DW) by removing all circles from each
  rectangle. Hence, we can choose a circular pattern C̃ = (t̃, P')
  with z^*_C̃ > 0 and largest external radius _t̃.

  Now consider Constraint (<ref>) for t=t̃. Because ∑_C ∈ P_t̃· z_C must be zero, there
  exists an (F̃,P̃) such that z^*_(F̃,P̃) > 0 and
  P̃_t̃≥ 1.  Replacing one ring of type t̃ by the
  circular pattern C̃ = (t̃,P') gives the packable tuple (F̂,
  P̂) := (F̃ + e_t̃, P̃ - e_t̃ + P').  Finally,
  we define a new solution ẑ via
  
    ẑ_(F,P)   := 
        0     if  (F,P) = (F̃, P̃),
    
        z^*_(F̂,P̂) + z^*_(F̃,P̃)    if  (F,P) = (F̂, P̂),
    
        z^*_(F,P)    otherwise,
        for all (F,P) ∈, andẑ_C   := 
        0     if  C = C̃,
    
        z^*_C    otherwise,

  for all C ∈.  By construction, ẑ is feasible for
  (<ref>) and has identical objective function value.  However,
  ν(ẑ) = ν(z^*) - z^*_C̃ < ν(z^*), contradicting the
  minimality assumption.
  



While (<ref>) does not improve
the strength of the relaxation, compared to (<ref>), the
advantage of (<ref>) is that it breaks the symmetry of the
combinatorial part of the , i.e., packing rings into rings, on each
recursion level. Applying the pattern-based Dantzig-Wolfe reformulation makes
deciding how to pack rings a counting problem in the master problem.  Compared
to (<ref>), the resulting sub-problems do not contain the
recursive structure of any more.  This balances the complexity between the
master problem and sub-problems, which is crucial for the performance of a
column generation algorithm.



§ COLUMN GENERATION METHOD FOR SOLVING THE 



This section presents a column generation based method for solving
formulation (<ref>).  The key ingredients of our method are the
enumeration of valid circular patterns, the generation of rectangular patterns,
and a dynamic verification for circular pattern candidates during the column
generation algorithm.
Each of these fundamental components of the column generation based method are
necessary for addressing the complexity of solving the pricing
problem (<ref>) and the difficulty in verifying whether a
circular pattern candidate is packable. Since it may not be possible to compute
all possible circular and rectangular patterns, the dynamic verification
provides the capability to only check patterns that may be part of an optimal
solution.
Additionally, a key feature of our algorithm is that it is always capable of
computing valid primal and dual bounds even though not all rectangular and
circular patterns have been found.



 §.§ Enumeration of Circular Patterns



Formulation (<ref>) contains one variable for each circular pattern
in . This set is, in general, of exponential size. We present a column
enumeration algorithm to compute all relevant circular patterns
for (<ref>). The main step of the algorithm is to verify whether a
given tuple (t,P)∈×_+^ is in the set  or not. A
tuple can be checked by solving the following nonlinear nonconvex verification
problem:


    x_iy_i - x_jy_j_2 ≥_i + _j     i,j ∈ C: i < j 
    x_iy_i_2 ≤_t - _i     i ∈ C 
    
      x_i, y_i ∈    i ∈ C


Here C := {1, …, ∑_iP_i} is the index set of individual circles,
and _i the corresponding external radius of a circle i ∈
C. Model (<ref>) checks whether all circles can be placed in a
non-overlapping way into a ring of
type t∈. Constraint (<ref>) ensures that no two
circles overlap, and (<ref>) guarantees that all circles are
placed inside a ring of type t.

The non-overlapping conditions (<ref>) are nonconvex and
make (<ref>) computationally difficult to solve. Due to the
positioning of circles, (<ref>) contains a lot of symmetry. The
rotation of every solution by 180 leads to another equivalent solution.
Typically, this kind of symmetry is difficult to address within a global solver. Branching on some continuous variables is likely to have no impact on
the dual bound. One way to overcome this problem is to break some symmetry of
the problem by ordering circles of the same type in the x-coordinate
non-decreasingly. We achieve this by adding

    x_i ≤ x_j  i < j: _i = _j

to (<ref>). Additionally, we add an auxiliary objective function
min_i ∈ C x_i to (<ref>). From our computational experiments
we have seen that adding (<ref>) to (<ref>) makes it
easier for the solver to prove infeasibility.

As already seen in Section <ref>, there is a dominance
relation between circular patterns, meaning that in any optimal solution of
, dominated patterns can be replaced by non-dominated
ones. Definition <ref> formalizes this notion of a dominance
relation between circular patterns.

  A circular pattern (t,P)∈ dominates (t,P') ∈ if and
  only if P' <_lex P, where <_lex denotes the standard lexicographical
  order of vectors.

Let

    := { (t,P) ∈|∄ (t,P') ∈: (t,P')  dominates  (t,P) }

be the set of non-dominated circular patterns. The set  might be
much smaller than , but is, in general, still of exponential size. Using
 in (<ref>), instead of the larger set , results in
fewer variables.

Finally, we present the procedure EnumeratePatterns in order to compute
. Algorithm <ref> considers all possible
(t,P) ∈×_+^ and checks whether (t,P) is a
circular pattern by solving (<ref>). The algorithm exploits the
dominance relation between circular patterns to reduce the number of solves
and filter dominated patterns.
In the following, we discuss the different steps of Algorithm <ref> in
more detail. For simplicity, we define the set [x] := {0,…,x} for an
integer number x ∈_+, and call a candidate
pattern (t,P) ∈×_+^ infeasible if
(t,P) ∉ and feasible otherwise.


The algorithm maintains three sets , , ,
initialized to the empty set.
In Line <ref>, we iterate through all possible pattern
candidates (t,P) for a fixed t ∈.
In Line <ref>, we check whether P dominates a circular
pattern already verified as infeasible and whether P is
dominated by a circular pattern already verified as feasible. In both cases, P can be skipped.
Otherwise, in Line <ref>, we solve a nonconvex verification
 (<ref>), which is the bottleneck of Algorithm <ref>.
Roughly speaking, this is easy to solve for the case where P, selected in
Line <ref>, is component-wise too small or too large. In the
first case, finding a feasible solution is easy due to a small number of
circles. In the other case, we can conclude that the circles of the candidate
P cannot be packed due to limited volume of the surrounding ring. The
computationally expensive verification lie between these two extreme
cases.
Because of the two reversed dominance checks, it is in general unclear in which order the P in
Line <ref> should be enumerated. On the one hand, it can be beneficial to start with
candidates that contain many circles. In case of a feasible candidate, many
other candidates can be discarded because of the dominance relation between
circular patterns. On the other hand, an infeasible candidate that dominates
another infeasible candidate can incur a redundant, difficult
 (<ref>) solve.

Algorithm <ref> returns two sets of circular patterns. The first set
contains all feasible circular patterns that could be successfully verified and
is denoted by . The second set, , contains all candidates
that could not be verified because of working limits, e.g., a time or memory
limit on the solve of (<ref>). At the end, each non-dominated circular pattern
is either in the set  or , which means that

    ⊆∪

holds.

Ideally, we have verified all candidates, i.e., = ∅. However, since
there are exponentially many candidates to check and each candidate requires to
solve (<ref>), it might not be possible to compute 
in a reasonable amount of time.

Nevertheless, even if the set  is non-empty, we are able to compute valid
dual and primal bounds for .
A valid primal bound is given when solving (<ref>) after restricting
the set of circular patterns to . This is becasuse this restriction
ensures that we only use packable patterns.
Using ∪ in (<ref>) yields a valid relaxation
of because we use at least all patterns in  and maybe some
circular patterns that are not packable.



 §.§ Computation of Valid Dual Bounds



The Pricing Problem (<ref>) is a classical —an
𝒩𝒫-hard nonlinear optimization problem, which is in practice very
hard to solve. State-of-the-art solvers might fail to prove global
optimality for this type of problems. Nevertheless, the following theorem shows
how to use a dual bound for (<ref>) to compute a valid dual
bound for .

Let ν_RMP be the optimum of the restricted master problem of
  ('), ν_Pricing be the optimal value for the Pricing
  Problem (<ref>), and OPT be the optimal solution value
  of . Then the inequality
  
    ν_RMP/1 - z_Pricing≤ OPT

  holds for all valid dual bounds z_Pricing≤ν_Pricing.


In our computational experiments we have seen that this bound can
indeed be used to obtain good quality bounds in cases where the circle packing
pricing problem (<ref>) could not be solved to
optimality. Note that the dual bounds of Theorem <ref> depend on
the quality of the dual bounds of pricing problems. Any improvement on the dual
bound for the automatically translates to better dual bounds for the .




 §.§ Price-and-Verify Algorithm



The price-and-verify algorithm is a column generation based algorithm that
incorporates ideas from Sections <ref>, <ref>,
and <ref>. This is summarized in
Algorithm <ref> and consists of three main steps:

  
  * An initial enumeration of circular patterns.
  
  * Generation of rectangular patterns with negative reduced cost.
  
  * Verification of circular pattern candidates during the pricing loop.

First, in Line <ref>, we use
Algorithm <ref> to compute the set of non-dominated circular patterns
. Its computational cost depends on the number of different ring types
, the external radii , and the internal radii .
Algorithm <ref> returns two sets  and  with the
properties

    ⊆ and
       ⊆∪.


A feature of Algorithm <ref> is the ability to compute valid
dual and primal bounds simultaneously. This is achieved by computing the primal
and dual bounds while dynamically verifying circular pattern candidates in
 during the solving process. The simultaneous computation of bounds
is an improvement over the methods previously discussed. In the previous
section, the proposed methods separately compute valid primal and dual bound for
by using  and ∪ respectively.

Algorithm <ref> uses ∪ as the initial
set of circular patterns in Formulation (<ref>). This ensures
that at least all packable circular patterns are considered, which is necessary
for proving a valid dual bound for . In general, many pattern candidates in
 are not packable and need to be discarded to prove global
optimality.  Algorithm <ref> dynamically verifies C ∈ and fixes the corresponding variable z_C to zero if C is not
packable. By discarding non-packable pattern candidates, the verification step
does not only improve the quality of the dual bound but also ensures that any
integer feasible solution z̅ is feasible for the , i.e., z_C = 0
for all C ∈.

The key idea of the dynamic verification is to only consider candidate patterns
in  that have a nonzero solution value. To be more precise, let
z^* be the optimal solution of the restricted master problem after no more
rectangular patterns with negative reduced cost could be found in the pricing
loop, see
Line <ref>. Algorithm <ref>
solves the relaxation of the master problem (<ref>) to
optimality if z^*_C = 0 holds for all C ∈. Otherwise, there
exists at least one C ∈ with z_C^* > 0. In order to verify C,
we solve (<ref>) in Line <ref> with
larger working limits than we have used in the initial enumeration step. There
are three possible outcomes. The candidate pattern C


  * is packable: We remove C from , add it to
  , and continue with the next pattern candidate C ∈
    that has a nonzero solution value in z^*.


  * is not packable: We remove C from  and fix z_C to
  zero, which cuts off the solution z^*. Resolving the leads to a
  different dual solution that might allow us to find new rectangular patterns
    with negative reduced cost. In this case, Algorithm <ref>
    goes back to Line <ref> and continues with
    pricing.


  * could not be verified: Due to working limits, it may not be
  possible to verify C. In this case, we label that C has been tested, i.e.,
    Ψ(C)=1, and continue with the next candidate C' ∈ that
    has not been labeled yet, i.e., Ψ(C')= 0, and z_C'^* >0. If C'
    can be verified to be not packable, we might get a different solution
    with z_C^* = 0. This would allow us to solve the relaxation of the
    master problem to optimality even though we could not verify C.

  In Line <ref> we check whether there is still
    a candidate C' ∈ with z_C'^* > 0 left. The candidates
    where z_C'^* > 0 have already been tested, so Ψ(C') = 1, but were
    unable to be verified within the working limits.  We fix all variables
    z_C' to zero for all C' ∈.  Since unverified patterns
    have been fixed to zero, it is no longer possible to compute a valid dual
    bound for .
  The remaining solution process can be seen as solving a restricted version of
    whose solution z̅ is feasible for the original problem. However,
    it might be the case that z̅ is still optimal, even though
    unverified candidates from  are fixed to zero. It is possible to
    verify the circular patterns a posteriori to determine whether an optimal
    solution has been found.


The advantage of dynamically verifying circular pattern candidates during the
pricing loop is that small working limits can be used in
Algorithm <ref> in order to identify packable patterns quickly and then
focus, with larger working limits, on the patterns that are used in the solution of the restricted master problem.

After applying Algorithm <ref> we have solved the relaxation of (<ref>) in the root node of the branch-and-bound tree.
If there exist any integer variables with a fractional solution value, then
branching must be performed.  Due to the complexity of the pricing problems, we
observed in our experiments that solving (<ref>) to global
optimality is only possible for simple problems that can be solved in the root
node—without requiring branching. The proposed branching strategy does not
greatly reduce the complexity of the pricing problems at each node of the tree.
As a result, performing pricing in each node is very time consuming. Thus, to
improve the computational performance, pricing is only performed in the root
node. Afterwards the is solved for the set of rectangular patterns that
have been found so far. The optimal solution of this restricted problem is
feasible for the original .  Our results show that applying this strategy
allows us to find good quality solutions for difficult problems.


 


§ COMPUTATIONAL EXPERIMENTS


In this section, we investigate the performance and the quality of the dual and
primal bounds obtained by our method and analyze how they
relate to specific properties of an instance. The algorithm presented in
Section <ref> is implemented in the solver  <cit.>. We refer to <cit.> for an
overview of the general solving algorithm and features of .



 §.§ Implementation


We extended with the addition of two plug-ins: one pricing plug-in for
solving the LP relaxation of Formulation (<ref>) and one constraint
handler plug-in to apply the dynamic verification of circular patterns during
Algorithm <ref>.
Algorithm <ref> is executed immediately before the solving process for
the commences.
To accelerate the verification of circular pattern candidates, we use a
simple greedy heuristic to check whether a given candidate (t,P) is a circular
pattern, i.e., if (t,P) ∈. The heuristic iteratively packs circles to
the left-most, and then lowest possible position in a ring of type
t∈. If the heuristic fails to verify a candidate, we
solve (<ref>) until a feasible solution has been found, or it has
been proven to be infeasible.
The same heuristic is used for finding a rectangular pattern with negative
reduced cost during Algorithm <ref>. If the heuristic fails
to find such a pattern, we directly solve (<ref>) to global
optimality.
The implementation is publically available in source code as part of the SCIP
Optimization Suite and can be downloaded at <https://scip.zib.de/>.



 §.§ Experimental Setup





We conducted three main experiments. In the first experiment we characterize
instances for which Algorithm <ref> finds all elements of the set of
non-dominated circular patterns ⊆. The second
experiment answers the question whether our proposed method is able to solve
instances to global optimality and characterizes these instances by their
structural properties. Because our method can also be used as a primal
heuristic, in the last experiment we compare it with the heuristic of
Pedroso et al. <cit.>.

In the enumeration experiment we apply Algorithm <ref> on each instance
and check whether  could be computed in two hours. For very difficult
problems it might happen that we spend the whole time limit in solving a single
.

For our second experiment, we use our method to compute valid dual and primal
bounds for with a total time limit of two hours. In contrast to the first
experiment, we enforce a time limit of 10s for each  (<ref>)
in Algorithm <ref>. After a time budget of 1200s, we stop
solving (<ref>) and only use the greedy heuristic to verify
circular pattern candidates. A pattern is added to  if it can be
verified. Otherwise, we add a candidate to  and process with the
next candidate pattern. During the pricing loop we then use a larger time limit
of 120s to verify a pattern in  that has a nonzero value in the LP
relaxation solution.  Again, we stop solving after 2400s were spent on
verifying pattern candidates.

During Algorithm <ref>, we use a time limit of
300s to solve (<ref>). If we fail to solve a pricing
problem to optimality and no improving column could be found, we stop solving
any further pricing problems, obtain a valid dual bound by applying
Theorem <ref>, and continue to solve the restricted master
problem for the current set of rectangular patterns. In our experiments, this
only occurs at the root node.

Finally, in our third experiment we compare the obtained primal bounds of our
method with those obtained from the heuristic. Both algorithms run with a
time limit of three hours on each instance. For this experiment the
specifications from the second experiment are used for out method.
We use the Python implementation of from <cit.>. Note that
is written in the programming language C, in which an implementation of
would be much faster. However, in our primal bound experiment we only
compare the quality of obtained solutions and it can be observed that finds its best solutions in the first few minutes.




  
Test Sets.

We consider two different test sets for our experiments. The first one contains
 real-world instances from the tube industry, which were
used in <cit.>, and is in the following called test set.
Because this test set is too limited for a detailed computational study, we
created a second test set containing  instances, the
test set. The purpose of this set is to show how the number of
different ring types , the maximum ratio of external radii
max_t _t / min_t _t, and the ratio between rectangle size and
the maximum volume of a ring
max{,} / max_t π (_t)^2 influence the performance
of our method.

The name of each instance reads
 where


  * ∈{3,4,5,10} is the number of ring types,

  * max_t _t/min_t _t = :α∈{2.0,2.3,…,4.7}
  is the maximum external radii ratio,

  * max{,}/max_t _t =: β∈{2.0,2.3,…,4.7} is the rectangle size to external radius ratio, and

  * /max_t π (_t)^2[0.8 γ, 1.2 γ] for γ∈{5,10} is the demand interval for each type t.

The demand of a type t ∈ is randomly chosen from the corresponding
demand interval. The size of this interval is anti-proportional to the external
radius, i.e., types with large external radius appear less often. For all
instances in we fixed the width  and height  of the
rectangles to 10. We created one instance for each 4-tuple, giving 800 instances in total.
All instances of the and test set are publically available at
  <https://github.com/mueldgog/RecursiveCirclePacking>.



  
Hardware and Software.

The experiments were performed on a cluster of 64bit Intel(R) Xeon(R) CPU
E5-2660 v3 2.6 GHz with 12 MB cache and 48 GB main memory.
In order to safeguard against a potential mutual slowdown of parallel processes,
we ran only one job per node at a time.
We used version 5.0 with  12.7.1.0 as LP solver <cit.>,
 20140000.1 <cit.>, and  3.12.5 with
 4.10.0 <cit.> as solver <cit.>.



 §.§ Computational Results


In the following, we discuss the results for the three described experiments in
detail. Instance-wise results of all experiments can be found in
Table in the electronic supplement.



  
Enumeration Experiments.

Figure <ref> shows the computing time required to compute all
non-dominated circular patterns  for the instances of the test
set. Each line corresponds to the subset of instances with identical number of
ring types . Each point on a line is computed as the shifted
geometric mean (with a shift of 1.0) over all instances that have the same value
max_t _t/min_t _t. We expect that the number of circular
patterns increases when increasing the ratio between the ring with largest inner
and the ring with smallest outer radius.

The first observation is that the time to compute all circular patterns
increases when  increases. For example, for = 10 we need
about 4-10 times longer to enumerate all patterns than for = 5.
Also, all lines in Figure <ref> approximately increase
exponentially in max_t _t/min_t _t. A larger ratio
implies that each verification  (<ref>) has a larger number of
circles that fit into a ring of inner radius max_t _t. These difficult
and the larger number of possible circular patterns provide an
explanation for the exponential increase of each line in
Figure <ref>.



Table <ref> shows in more detail for how many instances we could
compute  successfully and how much time it took on average. The rows
partition the instances according to the number of ring types and the columns
group these instances by their max_t _t / min_t _t
values. First, we see that for 392 of the 800 instances of the test
set we could successfully enumerate all circular patterns, in 19.8 seconds on
average. We see that for less and less instances the enumeration step is
successful as max_t _t / min_t_t increases. For none of the
instances with max_t _t / min_t _t
strictly larger than 3.5 could  be successfully
enumerated. Many verification for these instances are too difficult to
solve and often consume the whole time limit of two hours, even for the case of
three different ring types.
However, for the 480 instances with max_t _t / min_t _t≤ 3.5
Algorithm <ref> managed to compute on 81.6% (392) of these instances all
non-dominated circular patterns.





  
Exact Price-and-Verify.

In our second experiment, we analyze the primal and dual bounds that have been
computed by our column generation method. Figure <ref> shows the
achieved optimality gaps, i.e., (primal - dual)/dual,
for all instances of the test set. We solve 35.9% of the instances
to global optimality and get gaps between 0-25% for 5.6% of the
instances. For about 46.3% of the instances we achieve gaps between
25-100%, and only for a single instance the gap is larger than 100%.



Table <ref> and Table <ref> contain
aggregated results for the optimality gaps for the test
set. Table <ref> shows that out of the 287 optimally solved
instances, 80 instances have three, 72 have four, 70 have five, and 65
have ten different ring types.
Most of the instances with a gap larger than 50% are from the subset of
instances with ten ring types. Only 33 of the 98 instances with a gap larger
than 50% have less than ten different ring types.
Figure <ref> visualizes the results of Table <ref>
in a bar diagram. As expected, for an increasing number of ring types worse
optimality gaps are obtained.





Each row in Table <ref> corresponds to the set of instances
that have at least a certain value for max_t _t/min_t _t. For
example, the bottom-left corner value signifies that 60 out of the
160 instances with max_t _t/min_t _t≥ 4.4 could be solved
to optimality. As for Table <ref>, we see that the gaps
increase with a larger max_t _t/min_t _t ratio. This can be
explained by our previous observation, namely, the
difficulty of enumerating all circular patterns for these instances.
When ≠∅, then it could contain packable and
unpackable patterns. A valid dual bound is given by the solution to the relaxation without any unverified patterns fixed to zero. If this solution
contains patterns from  that are unpackable, then the computed bound
will be lower than the optimal bound if all circular patterns were verified.
Alternatively, after the relaxation has been solved to optimality, all
unverified patterns are fixed to zero. If  contains packable
patterns that are necessary to express an optimal integer solution, then the best
primal bound will be greater than the optimal solution value to the .
To summarize, our results show that the number of ring types  and the
quotient max_t _t/min_t _t are in many cases reliable
indicators for both the quality of primal and dual bounds and the computational
cost of our method. Instances that require branching are often
too difficult to solve to global optimality.



Finally, we briefly report on the size of the branch-and-bound trees for the
primal and dual bound experiments. We consider a node to be explored once it has
been selected by 's node selection algorithm. Our method explored more than
one node for 367 of the 800 instances and only 15 of these
instances could be solved to global optimality. The maximum number of explored
nodes is 207.



  
Primal Bound Experiments.

In our final experiments, we consider our method as a pure
primal heuristic for and compare it to the heuristic by Pedroso et
al. <cit.>, which is specifically designed to find dense packings
quickly. Table <ref> contains detailed results for the
, and Table <ref> aggregated results for the test
set. For analytical purposes, Table <ref> also shows the
results for the dual bounds.



For the test set, we are able to solve the three
instances , that require only one rectangle in the optimal
solution. On all but two instances our method achieves the same primal
bound as . On  we need three more rectangles and
on  four rectangles less.
Due to the small value max_t _t/min_t _t = 2.2 of the
instances with three different ring types, the enumeration step takes only a
fraction of a second. The difficulty of these instances lies only in the
placement of rings into rectangles and not in the recursive structure of
. Hence, it is not surprising that our method computes a worse solution than
on  because we only use a simple left-most greedy heuristic
before solving (<ref>).

Proving optimality for the instances of the test set is difficult for
our method.  Only the three instances  with one rectangle in the
optimal packing, could be solved to gap zero.
Because the rectangles are very large relative to the radii of the rings, the
pricing problems contain many variables and constraints. As a result, the
pricing problems are too difficult to solve to optimality. As shown above, the
ratio max_t _t/min_t _t of the instances with > 3 is
too large to enumerate and verify all circular patterns in reasonable time.

It is worth to notice that the dual bounds that can be proved by our method are
much better than simple volume-based bounds. Except for the three instances that
require only one rectangle, our dual bounds are at least 1.6 times larger than
the volume-based bounds.

Even though our method is not particularly designed for the characteristics of
the instances in the test set, it still performs well as a primal
heuristic. On the instances with five ring types it could enumerate many
non-trivial circular patterns and uses them to find a better primal solution
than .

For the test set, Table <ref> shows the number of instances on which
our method performed better or worse than with respect to the achieved
primal bound. The second column reports the primal bound average relative to the
value of on all instances of . For this we compute the shifted
geometric mean of all ratios between the obtained primal bounds of our method
and . The third column shows the total number of instances on which our
method found a better primal solution. The fourth column shows the improvement
relative to . The remaining three columns show statistics for the instances on
which our method performed worse.

We observe that our method outperforms on many instances.  On average,
the solutions are 2.7% better than the ones from . In total, we find a
better primal bound on 356 of the instances, and a worse bound on only 33
instances. Our method could find for all instances a primal feasible solution
before hitting the time or memory limit. The average deterioration on the 33
instances is 5.1-7.2% and the average improvement on the 356 instances is
5.6-6.9%.
Our method finds more often a better solution than for instances that
have a larger number of ring types. For ten ring types we find 123 better
solutions, which is about twice as large as for three ring types.

There are two reasons why our method performs better than on many
instances.  The first is that considers and positions each ring
individually. A large demand vector  results in a large number of
rings, which makes it difficult for to find good primal solutions. In
contrast, the number of rings and circles that need to be considered in our
pricing problems and in the enumeration is typically bounded by a number derived
from some volume arguments instead of the entries of the demand vector
. Thus, scaling up  typically does not have a large impact
when applying our column generation algorithm as a primal heuristic. The second
reason for the better performance is that for a given set of circular and
rectangular patterns, the master problem takes the best decisions of how to pack
rings recursively into each other. For instances where this combinatorial part
of the problem is difficult, we expect that our method performs better than
. Indeed, on instances with a large number of ring types our method
frequently finds better solutions than .



In summary, the experiments on synthetic and real-world instances shows that our
method solves small and medium-sized instances to global optimality.  This was
the case on 287 of the randomly generated instances and for three of nine
real-world instances.  Due to the costly verification of circular patterns and
difficult sub-problems, our method is not able to solve larger instances to
global optimality, but still achieves good primal and dual bounds.  Compared to
the state-of-the-art heuristic for , our method finds on 356 of the
instances better, and only on 33% of the instances worse primal solutions.
 


§ CONCLUSION



In this article, we have presented the first exact algorithm for solving
practically relevant instances for the extremely challenging recursive circle packing problem. Our method is based
on a Dantzig-Wolfe decomposition of a nonconvex model. The key idea of
solving this decomposition via column generation is to break symmetry of the
problem by using circular and rectangular patterns. These patterns are used to
model all possible combinations of packing rings into other rings. As a result,
we were able to reduce the complexity of the sub-problems significantly and
shift the recursive part of to a linear master problem.

In some sense, this reformulation can be interpreted as a reduction technique from to . All
occurring sub-problems in the enumeration of circular patterns and the pricing
problems are classical and they constitute the major computational
bottleneck. Every primal or dual improvement for this problem class would
directly translate to better primal and dual bounds for . Still, in order
to prove optimality it is usually necessary to solve the 𝒩𝒫-hard
 to optimality, which can fail for harder instances. However,
even for this case, the application of Theorem <ref> and the
pessimistic and optimistic enumeration of circular patterns guarantees valid
primal and dual bounds for . The combination of column generation with
column enumeration could be of more general interest when using
decomposition techniques for that lead to hard nonconvex sub-problems.

An interesting extension of the presented method is its application
to problem with different container shapes and sizes. Since the master problem
of the decomposed model does not depend on the shape of the containers or packed
objects, it is possible to apply this model to any container shape. This would
only require a modification to the column generation subproblems to produce
packable patterns that can be added to the master problem. Thus, the presented
methods cover a wide range of packing problems.

Finally, our current proof-of-concept implementation could certainly be improved
further. To mention only one point, we currently use a rather simple greedy
heuristic in order to find quickly a feasible solution for the verification
 (<ref>) and the Pricing
Problem (<ref>). By using more sophisticated heuristics for
the well-studied , we might be able to compute better optimality gaps for
instances where the positioning of circles into rectangles or rings is
difficult.
Surprisingly, even with a simple greedy heuristic our method works well as a
primal heuristic and finds for many instances better solutions than
 <cit.>.

 


§ ACKNOWLEDGMENTS

This work has been supported by the Research Campus MODAL Mathematical
  Optimization and Data Analysis Laboratories funded by the Federal Ministry of
Education and Research (BMBF Grant 05M14ZAM).  All responsibility for the content
of this publication is assumed by the authors.
 
spmpsci      




§ APPENDIX



@lrrrrrrrrr
  Detailed results for randomly generated instances.
  

  volume-based dual bound
  proven primal bound
  proven dual bound
  proven primal bound by heuristic
  total number of circular patterns found
  total number of circular patterns candidates
  total number of generated rectangular patterns
  total number of branch-and-bound nodes
  time to compute all circular patterns in enumeration experiment [1.5ex] instance                                             

  instance                                             

  i03_2.0_2.0_05              8             17             17             17              4              0              6              1            0.4

i03_2.0_2.0_10             22             34             38             38              5              0              7              3            1.4

i03_2.0_2.3_05              7             16             16             16              4              0              6              1            0.5

i03_2.0_2.3_10             23             33             45             49              4              0              9              3            0.9

i03_2.0_2.6_05              8             23             23             23              3              0              7              1            0.6

i03_2.0_2.6_10             14             41             41             41              4              0              9              1            0.3

i03_2.0_2.9_05              8             16             16             16              4              0              9              1            0.4

i03_2.0_2.9_10             14             18             27             27              4              0              8              3            0.7

i03_2.0_3.2_05              9             23             23             23              4              0              7              1            0.6

i03_2.0_3.2_10             20             26             38             38              4              0             11              3            1.0

i03_2.0_3.5_05              8             21             21             21              3              0             10              1            0.7

i03_2.0_3.5_10             16             23             32             33              4              0             10              3            0.5

i03_2.0_3.8_05              6             10             14             15              4              0             15              3            0.4

i03_2.0_3.8_10             16             23             31             33              4              0             16              3            0.3

i03_2.0_4.1_05              9             13             18             18              4              0             21              3            0.3

i03_2.0_4.1_10             12             18             24             24              4              0             25              3            0.4

i03_2.0_4.4_05              8             10             14             15              4              0             18              3            0.3

i03_2.0_4.4_10             14             20             25             27              4              0             18              3            0.3

i03_2.0_4.7_05              7             13             19             19              3              0             16              3            0.6

i03_2.0_4.7_10             14             21             29             30              4              0             24              3            0.4

i03_2.3_2.0_05              7             15             15             15              3              0              5              1            2.2

i03_2.3_2.0_10             16             36             36             36              4              0              6              1            0.5

i03_2.3_2.3_05              8             12             18             18              4              0              7              3            0.9

i03_2.3_2.3_10             14             32             32             32              4              0              5              1            1.2

i03_2.3_2.6_05              9             11             17             18              4              0              7              3            0.8

i03_2.3_2.6_10             16             30             35             38              4              0             10              4            1.0

i03_2.3_2.9_05              7             17             17             17              4              0              7              1            0.6

i03_2.3_2.9_10             17             66             66             66              3              0              5              1            2.1

i03_2.3_3.2_05              7             11             16             16              4              0              7              3            0.7

i03_2.3_3.2_10             14             38             38             38              4              0              5              1            0.9

i03_2.3_3.5_05              8             23             23             23              3              0              6              1            0.9

i03_2.3_3.5_10             14             21             28             29              4              0             14              3            0.9

i03_2.3_3.8_05              7             11             15             15              4              0             16              3            0.7

i03_2.3_3.8_10             23             25             34             35              5              0             18             20            2.6

i03_2.3_4.1_05              7             10             13             13              4              0             12              3            1.1

i03_2.3_4.1_10             16             24             31             30              3              0             22              3            0.9

i03_2.3_4.4_05              8             11             15             15              4              0             21              3            0.5

i03_2.3_4.4_10             13             19             24             25              5              0              8              3            1.6

i03_2.3_4.7_05              9             13             19             20              3              0             10              3            0.8

i03_2.3_4.7_10             16             23             30             30              4              0             23              3            0.8

i03_2.6_2.0_05              9             14             20             19              4              0              5              3            1.5

i03_2.6_2.0_10             12             34             34             34              4              0              5              1            1.3

i03_2.6_2.3_05              7             11             16             14              4              0              5              3            1.6

i03_2.6_2.3_10             17             29             39             40              4              0              7              3            1.4

i03_2.6_2.6_05              8             25             25             25              3              0              3              1            2.2

i03_2.6_2.6_10             24             26             36             37              8              1             11              3           11.6

i03_2.6_2.9_05              8             30             30             30              3              0              3              1            3.2

i03_2.6_2.9_10             13             67             67             67              3              0              3              1            2.5

i03_2.6_3.2_05              6             19             19             19              4              0              5              1            1.6

i03_2.6_3.2_10             12             37             37             37              6              0              5              1         1599.4

i03_2.6_3.5_05              8             12             16             17              4              0             19              3            2.0

i03_2.6_3.5_10             24             26             34             35              8              1             15              3         5686.4

i03_2.6_3.8_05              6              8             11             11              4              0             11              3            1.7

i03_2.6_3.8_10             12             38             38             38              3              0              6              1            2.0

i03_2.6_4.1_05              7              9             13             12              5              0              8              3            4.6

i03_2.6_4.1_10             14             19             26             26              3              0             21              3            2.5

i03_2.6_4.4_05              7             12             15             15              3              0             17              3            1.9

i03_2.6_4.4_10             22             23             31             32              8              1             15              3         1499.0

i03_2.6_4.7_05              6             10             14             14              4              0             16              3            1.6

i03_2.6_4.7_10             13             18             24             24              5              0             18              3            4.7

i03_2.9_2.0_05              7             12             17             17              4              0              6              3           10.9

i03_2.9_2.0_10             13             29             29             29              3              0              3              1           18.2

i03_2.9_2.3_05              6             15             15             15              3              0              3              1           17.6

i03_2.9_2.3_10             14             40             40             40              3              0              3              1           15.1

i03_2.9_2.6_05              7             18             18             18              4              0              5              1           13.5

i03_2.9_2.6_10             13             41             41             41              3              0              3              1           21.5

i03_2.9_2.9_05              7             11             12             12              7              1             12              3          843.5

i03_2.9_2.9_10             13             66             66             66              3              0              3              1          811.0

i03_2.9_3.2_05              7             14             14             15              4              0             16              1           12.7

i03_2.9_3.2_10             14             38             38             38              5              1              5              1           15.3

i03_2.9_3.5_05              7             10             13             13              7              1              7              3           63.6

i03_2.9_3.5_10             20             20             29             30             10              3             17              1         3990.8

i03_2.9_3.8_05              7             10             13             13              4              0             22              3            9.7

i03_2.9_3.8_10             12             14             19             19              9              2              9              1          320.8

i03_2.9_4.1_05              7             10             13             13              4              0             17              3           10.1

i03_2.9_4.1_10             15             20             26             27              7              1             16              3           27.0

i03_2.9_4.4_05              8              9             12             12              4              0             17              3           12.3

i03_2.9_4.4_10             12             21             27             28              4              0             13              3           11.1

i03_2.9_4.7_05              7             11             14             15              4              0             21              3            8.9

i03_2.9_4.7_10             13             22             29             29              4              0             16              3            8.8

i03_3.2_2.0_05              7             14             14             14              4              0              5              1          160.3

i03_3.2_2.0_10             14             18             27             27              6              1             10              1          189.1

i03_3.2_2.3_05              7              9             12             13              4              0              7              3          181.9

i03_3.2_2.3_10             16             20             28             30              4              0              7              3          178.9

i03_3.2_2.6_05              6             15             15             15              4              0              5              1          320.7

i03_3.2_2.6_10             15             29             29             29              4              0              5              1          318.9

i03_3.2_2.9_05              7             10             14             14              5              1             12              1          265.2

i03_3.2_2.9_10             15             23             31             31              4              0             13              3          250.8

i03_3.2_3.2_05              7             16             16             16              5              1              8              1          197.8

i03_3.2_3.2_10             16             32             32             32              8              2              7              1          329.4

i03_3.2_3.5_05              8             13             13             13              4              0             12              1          309.0

i03_3.2_3.5_10             14             17             25             26              7              2             19              1     time limit

i03_3.2_3.8_05             11             11             16             15             15              5             10              1     time limit

i03_3.2_3.8_10             22             22             32             32             15              5             19              1     time limit

i03_3.2_4.1_05              7              9             12             12              4              0             20              3          228.2

i03_3.2_4.1_10             15             21             28             27              4              0             14              3          231.3

i03_3.2_4.4_05              8             12             15             16              4              0             17              3          276.5

i03_3.2_4.4_10             15             19             26             26              4              0             13              3          276.6

i03_3.2_4.7_05              7              9             12             12              4              0             10              3          141.1

i03_3.2_4.7_10             16             21             30             32              5              1             26              1          152.1

i03_3.5_2.0_05              7              9             13             14              9              3             11              1         6052.1

i03_3.5_2.0_10             16             16             23             24             15              5              8              1     time limit

i03_3.5_2.3_05              8             15             15             15              4              0              7              1         3728.3

i03_3.5_2.3_10             14             20             29             30              5              1             10              1         3756.9

i03_3.5_2.6_05              7             17             17             17              5              1              7              1         3745.3

i03_3.5_2.6_10             13             39             39             39              4              0              5              1         3736.8

i03_3.5_2.9_05              9             16             16             17              8              2             13              3     time limit

i03_3.5_2.9_10             12             31             31             31              4              0              6              1     time limit

i03_3.5_3.2_05              7             18             18             18              4              0              5              1     time limit

i03_3.5_3.2_10             15             30             30             30              7              2             14             10     time limit

i03_3.5_3.5_05              8              9             14             15              5              1             12              2         4886.7

i03_3.5_3.5_10             14             19             27             27              5              1             23              1         5042.7

i03_3.5_3.8_05              6             13             13             13              4              0              5              1     time limit

i03_3.5_3.8_10             15             21             27             29              4              0             18              3     time limit

i03_3.5_4.1_05              6              9             12             12              4              0             22              3         3553.2

i03_3.5_4.1_10             14             19             24             25              4              0             21              3         3582.9

i03_3.5_4.4_05              8              9             14             15             12              4             29              1     time limit

i03_3.5_4.4_10             13             18             22             23              4              0             26              3         5203.6

i03_3.5_4.7_05              6              9             12             13              5              1             23              1         3311.8

i03_3.5_4.7_10             14             19             24             24              4              0             10              3         3042.6

i03_3.8_2.0_05              9             10             15             16             12              5             11              1     time limit

i03_3.8_2.0_10             14             34             34             34              6              2              5              1     time limit

i03_3.8_2.3_05              7             20             20             20              4              1              3              1     time limit

i03_3.8_2.3_10             15             33             34             34              6              2             11              1     time limit

i03_3.8_2.6_05              6             15             15             15              5              1              6              1     time limit

i03_3.8_2.6_10             12             26             26             26              5              1              6              1     time limit

i03_3.8_2.9_05              9             29             29             29              4              1              6              1     time limit

i03_3.8_2.9_10             13             36             36             36              6              2              6              1     time limit

i03_3.8_3.2_05              8             19             19             19              5              1              8              1     time limit

i03_3.8_3.2_10             14             25             25             25             18              8              5              1     time limit

i03_3.8_3.5_05              8             11             16             16              6              2             15              1     time limit

i03_3.8_3.5_10             15             17             26             27              5              1             10              1     time limit

i03_3.8_3.8_05             11             11             14             14             26             14             17              9     time limit

i03_3.8_3.8_10             15             46             46             46              5              2              5              1     time limit

i03_3.8_4.1_05              8              9             13             14              5              1             21              1     time limit

i03_3.8_4.1_10             16             20             29             31              9              3             18             10     time limit

i03_3.8_4.4_05              6              9             13             13             12              5             14              1     time limit

i03_3.8_4.4_10             12             16             21             23              6              2             17              1     time limit

i03_3.8_4.7_05              7              9             11             11              5              1             23              1     time limit

i03_3.8_4.7_10             13             20             28             31              4              1              7              3     time limit

i03_4.1_2.0_05              7              8             11             11             20              9              9              1     time limit

i03_4.1_2.0_10             15             27             27             27              6              2              5              1     time limit

i03_4.1_2.3_05              6             14             14             14              6              2              7              1     time limit

i03_4.1_2.3_10             14             18             25             25              5              1              7              1     time limit

i03_4.1_2.6_05              6             24             24             24              5              2              3              1     time limit

i03_4.1_2.6_10             14             25             27             28             10              4              9              1     time limit

i03_4.1_2.9_05              9             16             17             16              6              2             13              1     time limit

i03_4.1_2.9_10             15             33             33             33             19              9             10              1     time limit

i03_4.1_3.2_05              7             18             18             18              6              2              8              1     time limit

i03_4.1_3.2_10             12             29             29             29             12              5              7              1     time limit

i03_4.1_3.5_05              9             10             14             15              5              1             12              1     time limit

i03_4.1_3.5_10             13             18             24             26              5              1             12              1     time limit

i03_4.1_3.8_05              8             15             15             15             20              9              7              1     time limit

i03_4.1_3.8_10             15             22             30             30              8              3             15              1     time limit

i03_4.1_4.1_05             10             10             14             14             29             17             19              1     time limit

i03_4.1_4.1_10             14             18             25             26              5              1             13              1     time limit

i03_4.1_4.4_05              7              9             12             13              6              2             19              1     time limit

i03_4.1_4.4_10             17             40             40             40              5              2             10              1     time limit

i03_4.1_4.7_05              8             11             15             15              6              2             22              1     time limit

i03_4.1_4.7_10             14             17             22             22              5              1             15             12     time limit

i03_4.4_2.0_05              8             13             14             15              6              2              6              1     time limit

i03_4.4_2.0_10             11             14             22             23             12              5             10              1     time limit

i03_4.4_2.3_05              8             18             18             18              5              1              7              1     time limit

i03_4.4_2.3_10             13             27             27             27              6              2              5              1     time limit

i03_4.4_2.6_05              8              9             13             13             18              8             10              1     time limit

i03_4.4_2.6_10             14             51             51             51              5              2              3              1     time limit

i03_4.4_2.9_05              6             25             25             25              5              2              3              1     time limit

i03_4.4_2.9_10             13             63             63             63              5              2              3              1     time limit

i03_4.4_3.2_05              7             14             14             14              6              2              8              1     time limit

i03_4.4_3.2_10             14             30             30             30              6              2              7              1     time limit

i03_4.4_3.5_05              8             17             17             17              5              2             15              2     time limit

i03_4.4_3.5_10             13             18             25             25             11              4             17              1     time limit

i03_4.4_3.8_05              8             16             16             16              5              2              6              1     time limit

i03_4.4_3.8_10             13             19             23             27              5              1              9              3     time limit

i03_4.4_4.1_05              7              9             13             13              6              2             14              1     time limit

i03_4.4_4.1_10             16             21             27             29             10              4             16              2     time limit

i03_4.4_4.4_05              7              8             11             11              5              1             16              3     time limit

i03_4.4_4.4_10             12             31             31             31              5              2             10              1     time limit

i03_4.4_4.7_05              9             12             17             18              5              2             15              1     time limit

i03_4.4_4.7_10             16             16             23             24             26             14             20              1     time limit

i03_4.7_2.0_05              6             11             14             15             10              4             11              1     time limit

i03_4.7_2.0_10             14             16             25             26             18              8              7              1     time limit

i03_4.7_2.3_05              8             17             17             17              6              2              7              1     time limit

i03_4.7_2.3_10             16             29             29             29              6              2             10              1     time limit

i03_4.7_2.6_05              6             11             11             11              6              2              7              1     time limit

i03_4.7_2.6_10             12             34             34             34              6              2              5              1     time limit

i03_4.7_2.9_05             11             11             15             15             37             20             18              1     time limit

i03_4.7_2.9_10             12             31             31             31             12              5              5              1     time limit

i03_4.7_3.2_05              6             15             15             15             14              6              7              1     time limit

i03_4.7_3.2_10             16             60             60             60              5              2              5              1     time limit

i03_4.7_3.5_05              8             24             24             24              5              2              6              1     time limit

i03_4.7_3.5_10             15             21             28             28              8              3             23              1     time limit

i03_4.7_3.8_05              8             12             12             13              6              2              9              1     time limit

i03_4.7_3.8_10             13             16             27             28              6              2             13              1     time limit

i03_4.7_4.1_05              8             16             16             16              5              2             10              1     time limit

i03_4.7_4.1_10             13             17             24             24             10              4             17              1     time limit

i03_4.7_4.4_05              8              8             11             11              6              2             14              1     time limit

i03_4.7_4.4_10             12             14             21             21              6              2             11              1     time limit

i03_4.7_4.7_05              8              9             13             14              6              2             22              1     time limit

i03_4.7_4.7_10             16             20             25             26              5              1             15              2     time limit

i04_2.0_2.0_05              9             24             24             24              6              0              7              1            0.5

i04_2.0_2.0_10             25             50             50             50              7              0              9              1            1.0

i04_2.0_2.3_05              8             24             24             24              6              0              7              1            0.8

i04_2.0_2.3_10             14             36             36             37              7              0              8              1            0.7

i04_2.0_2.6_05              9             25             25             27              6              0              8              1            0.7

i04_2.0_2.6_10             14             33             33             32              7              0             11              1            0.6

i04_2.0_2.9_05             10             33             33             33              6              0              7              1            0.7

i04_2.0_2.9_10             18             21             33             33              7              0             17              3            0.7

i04_2.0_3.2_05              8             39             39             39              6              0              9              1            0.8

i04_2.0_3.2_10             17             44             44             44              6              0             14              1            0.5

i04_2.0_3.5_05              9             17             17             17              7              0             16              1            0.6

i04_2.0_3.5_10             17             23             33             34              7              0             23              3            0.6

i04_2.0_3.8_05             12             17             23             24              6              0             20              3            1.7

i04_2.0_3.8_10             15             24             35             36              6              0             21              3            0.5

i04_2.0_4.1_05              8             11             15             16              7              0             21              3            0.6

i04_2.0_4.1_10             16             22             30             31              7              0             20              3            0.5

i04_2.0_4.4_05             13             15             20             21              7              0             29              3            1.0

i04_2.0_4.4_10             14             21             30             30              6              0             30              3            0.5

i04_2.0_4.7_05              9             12             16             17              7              0             50              3            0.8

i04_2.0_4.7_10             36             39             55             58              6              0             18              3            1.9

i04_2.3_2.0_05              9             19             19             19              6              0              6              1            0.9

i04_2.3_2.0_10             26             30             47             50              9              0              9              3            2.8

i04_2.3_2.3_05              8             12             18             18              7              0             10              4            1.0

i04_2.3_2.3_10             19             30             47             45              7              0              9              3            1.1

i04_2.3_2.6_05              9             12             20             20              7              0             12              3            0.8

i04_2.3_2.6_10             14             22             33             34              7              0             20              3            1.1

i04_2.3_2.9_05             10             36             36             36              6              0              6              1            1.0

i04_2.3_2.9_10             16             44             44             44              6              0            525              1            0.7

i04_2.3_3.2_05              8             38             38             32              5              0              6              1            1.3

i04_2.3_3.2_10             16             41             41             41              6              0              7              1            1.2

i04_2.3_3.5_05              9             24             24             24              6              0             14              1            1.1

i04_2.3_3.5_10             22             39             39             40              8              0             19              1            3.7

i04_2.3_3.8_05              8             15             20             23              6              0             22              6            0.8

i04_2.3_3.8_10             13             19             26             26              7              0             21              3            1.2

i04_2.3_4.1_05              8             11             15             15              7              0             28              3            2.0

i04_2.3_4.1_10             17             25             34             35              7              0             24              3            1.1

i04_2.3_4.4_05             12             14             19             19             10              0             14              3            3.8

i04_2.3_4.4_10             16             26             37             36              6              0             23              3            1.1

i04_2.3_4.7_05              8             14             19             19              6              0             29              3            0.9

i04_2.3_4.7_10             18             29             39             39              6              0             28              3            0.9

i04_2.6_2.0_05             11             23             23             23             11              1             11              1          814.8

i04_2.6_2.0_10             13             21             29             30              7              0              9              3            3.2

i04_2.6_2.3_05              8             18             18             18              8              0             11              1            5.1

i04_2.6_2.3_10             17             56             56             56              4              0              4              1            2.9

i04_2.6_2.6_05              8             11             16             16              9              0              8              3            5.7

i04_2.6_2.6_10             14             49             49             49              6              0              8              1            2.8

i04_2.6_2.9_05              8             13             17             17              9              0             11              3            5.4

i04_2.6_2.9_10             21             25             34             34             12              1             20              3           11.5

i04_2.6_3.2_05              8             30             30             30              6              0              6              1            2.7

i04_2.6_3.2_10             15             25             34             35              7              0             18              3            2.1

i04_2.6_3.5_05             10             10             15             23             11              1             20              3         2087.5

i04_2.6_3.5_10             14             35             35             35              6              0              8              1            3.2

i04_2.6_3.8_05              8             14             19             20              6              0             29              3            1.7

i04_2.6_3.8_10             27             46             46             46             12              2             19              2           15.2

i04_2.6_4.1_05              8             12             15             16              7              0             27              3            2.9

i04_2.6_4.1_10             14             21             29             32              9              0             15              3            7.8

i04_2.6_4.4_05             11             13             17             17             10              0             24              3            9.9

i04_2.6_4.4_10             14             21             29             29              7              0             21              3            2.0

i04_2.6_4.7_05             10             15             21             21              6              0             19              3            2.0

i04_2.6_4.7_10             16             21             32             31              8              0             25              3            6.9

i04_2.9_2.0_05              9             20             20             20              7              0              8              1           11.4

i04_2.9_2.0_10             16             30             30             31              9              1             11              1           28.6

i04_2.9_2.3_05              7             13             16             17              7              0             13              4           12.7

i04_2.9_2.3_10             16             26             37             38              8              1             26              3           14.3

i04_2.9_2.6_05              9             14             19             20              7              0             18              3           13.7

i04_2.9_2.6_10             15             30             36             36              7              0             11              3           20.8

i04_2.9_2.9_05              7             11             16             16              9              1             21              3          833.5

i04_2.9_2.9_10             18             28             38             39             10              1             13              8          828.9

i04_2.9_3.2_05              9             12             18             18              7              0             17              3           13.4

i04_2.9_3.2_10             17             26             36             37              7              0             23              3           13.2

i04_2.9_3.5_05             10             24             24             24              8              1             14              1           17.6

i04_2.9_3.5_10             18             25             33             35              7              0             21              3           14.5

i04_2.9_3.8_05              8             13             17             18              7              0             32              3           10.2

i04_2.9_3.8_10             16             25             33             34              9              1             17              3           22.3

i04_2.9_4.1_05              7             16             16             16              6              0             13              1           11.2

i04_2.9_4.1_10             14             28             28             29             12              2             21              1          132.0

i04_2.9_4.4_05              8             13             17             17              7              0             34              3           12.9

i04_2.9_4.4_10             18             24             31             31              7              0             36              3           12.4

i04_2.9_4.7_05              9             12             16             16              7              0             40              3           11.0

i04_2.9_4.7_10             17             26             34             35              7              0             29              9           10.6

i04_3.2_2.0_05             10             13             19             20             11              2             12              1          687.1

i04_3.2_2.0_10             19             30             36             38             14              4              8              1         3399.2

i04_3.2_2.3_05             11             14             19             20             21              6             11              1     time limit

i04_3.2_2.3_10             14             38             38             38              9              1             13              1          200.7

i04_3.2_2.6_05             10             24             24             24              6              0              6              1          356.4

i04_3.2_2.6_10             17             35             52             53              8              2              8              1          336.0

i04_3.2_2.9_05              9             32             32             32              6              0              9              1          280.8

i04_3.2_2.9_10             18             33             33             33             18              5             16              1         1902.6

i04_3.2_3.2_05             12             14             20             21             28             12             31              1     time limit

i04_3.2_3.2_10             19             37             38             41              8              1             13              3          202.2

i04_3.2_3.5_05              8             12             17             18             11              2             20              1          442.5

i04_3.2_3.5_10             17             24             35             36              8              1              7              3          316.4

i04_3.2_3.8_05              8             12             18             19              6              0             12              3     time limit

i04_3.2_3.8_10             13             18             23             24             16              4             13              3     time limit

i04_3.2_4.1_05              7             11             14             14              7              0             27              3          229.9

i04_3.2_4.1_10             15             25             34             37             15              4             13              3     time limit

i04_3.2_4.4_05              7             21             21             20              5              0             10              1          333.5

i04_3.2_4.4_10             16             26             39             39              8              2             46              1          285.0

i04_3.2_4.7_05              8             13             17             18              8              1             23              1          147.9

i04_3.2_4.7_10             16             24             31             32              7              0             23              3          144.2

i04_3.5_2.0_05             10             14             19             19              6              0              6              3         5189.0

i04_3.5_2.0_10             16             23             35             36             26             10             13              1     time limit

i04_3.5_2.3_05             11             11             17             17             26              8             17              1     time limit

i04_3.5_2.3_10             14             34             34             34              6              0              6              1         3724.2

i04_3.5_2.6_05              8             18             18             19              7              0              9              1         3596.2

i04_3.5_2.6_10             27             27             39             41             27             10             15              1     time limit

i04_3.5_2.9_05             10             13             19             19              9              2             23              1     time limit

i04_3.5_2.9_10             18             24             31             31             17              4             13              1     time limit

i04_3.5_3.2_05              9             14             18             18              8              1             24              3     time limit

i04_3.5_3.2_10             16             34             34             34              8              1              6              1     time limit

i04_3.5_3.5_05              7             17             17             17             13              4             14              1     time limit

i04_3.5_3.5_10             27             27             38             47             87             48             18              1     time limit

i04_3.5_3.8_05              8             11             15             16             14              4             21              1     time limit

i04_3.5_3.8_10             14             22             29             29             10              2             26              1     time limit

i04_3.5_4.1_05              8             13             18             19              7              1             30              1         3703.7

i04_3.5_4.1_10             16             24             33             33              7              1             33              1         3775.6

i04_3.5_4.4_05              8             11             14             15              7              0             40              3         5490.4

i04_3.5_4.4_10             17             24             30             31              7              0             32              3         5245.5

i04_3.5_4.7_05              8             13             22             21              7              1             13              1         3241.2

i04_3.5_4.7_10             15             21             26             26              7              0             10              3         3024.1

i04_3.8_2.0_05              7             17             17             17             12              4             13              1     time limit

i04_3.8_2.0_10             16             36             36             36              7              1              6              1     time limit

i04_3.8_2.3_05              9             10             14             18             29             12             19              1     time limit

i04_3.8_2.3_10             16             39             39             39             17              7             12              1     time limit

i04_3.8_2.6_05             12             14             20             21             37             18             27              1     time limit

i04_3.8_2.6_10             19             46             46             46              7              1              6              1     time limit

i04_3.8_2.9_05              9             42             42             42              6              2              4              1     time limit

i04_3.8_2.9_10             18             54             54             54              7              1              7              1     time limit

i04_3.8_3.2_05              9             36             36             36              8              2              8              1     time limit

i04_3.8_3.2_10             17             71             71             71              8              2             10              1     time limit

i04_3.8_3.5_05              8             11             14             14              8              1             24              3     time limit

i04_3.8_3.5_10             16             38             38             38             22             10              9              1     time limit

i04_3.8_3.8_05              8             11             15             17              8              1             24              3     time limit

i04_3.8_3.8_10             18             55             55             55              7              3              9              1     time limit

i04_3.8_4.1_05              7             11             14             15             22              9             17              1     time limit

i04_3.8_4.1_10             18             26             36             37             14              5             21             48     time limit

i04_3.8_4.4_05              8             13             17             17             30             14             32              1     time limit

i04_3.8_4.4_10             14             19             27             27             18              6             21              1     time limit

i04_3.8_4.7_05              7              8             10             14             31             13             38              3     time limit

i04_3.8_4.7_10             17             24             32             32              9              2             26              1     time limit

i04_4.1_2.0_05             10             13             20             19             17              6             11              1     time limit

i04_4.1_2.0_10             18             38             40             40              9              3              7              1     time limit

i04_4.1_2.3_05              8             15             15             16             10              3             14              1     time limit

i04_4.1_2.3_10             17             50             50             50              7              1              4              1     time limit

i04_4.1_2.6_05              8             19             19             19              8              2             10              1     time limit

i04_4.1_2.6_10             18             48             48             48              9              3              7              1     time limit

i04_4.1_2.9_05              9             18             18             18              9              2              8              1     time limit

i04_4.1_2.9_10             25             26             35             35             43             21             16              1     time limit

i04_4.1_3.2_05              8             18             18             19             19              7              8              1     time limit

i04_4.1_3.2_10             18             40             40             40              9              2             11              1     time limit

i04_4.1_3.5_05             10             19             19             23              8              2            233              1     time limit

i04_4.1_3.5_10             18             35             36             36             12              5             15              1     time limit

i04_4.1_3.8_05              8             11             16             19              7              1              8              3     time limit

i04_4.1_3.8_10             18             25             32             32              9              2             20              1     time limit

i04_4.1_4.1_05              8             10             13             13             30             13              8              1     time limit

i04_4.1_4.1_10             16             35             35             35              8              2             24              2     time limit

i04_4.1_4.4_05              9             14             17             17              9              3             22              2     time limit

i04_4.1_4.4_10             18             19             27             29             28             12             28              7     time limit

i04_4.1_4.7_05              9             11             16             17              8              2             29              1     time limit

i04_4.1_4.7_10             15             23             34             37              7              1             11              3     time limit

i04_4.4_2.0_05              8             19             19             19             10              4              5              1     time limit

i04_4.4_2.0_10             18             18             27             27             45             23             16              1     time limit

i04_4.4_2.3_05              8             14             14             14             43             21              7              2     time limit

i04_4.4_2.3_10             23             25             36             37             53             29             12              1     time limit

i04_4.4_2.6_05              7             28             28             28              8              2              4              1     time limit

i04_4.4_2.6_10             22             25             35             35            157             96             15              5     time limit

i04_4.4_2.9_05             13             13             18             21            239            156             31              2     time limit

i04_4.4_2.9_10             19             43             43             43             11              4             11              1     time limit

i04_4.4_3.2_05              7             28             28             28             20              9              7              1     time limit

i04_4.4_3.2_10             18             41             41             41             12              4             13              1     time limit

i04_4.4_3.5_05             11             11             16             21            256            166             19              1     time limit

i04_4.4_3.5_10             14             22             29             29             20              8             14              3     time limit

i04_4.4_3.8_05              7             24             24             24             30             14             10              1     time limit

i04_4.4_3.8_10             14             21             29             32             10              3             15              1     time limit

i04_4.4_4.1_05              8             13             18             18             10              4             14              2     time limit

i04_4.4_4.1_10             19             25             35             36             35             17             35              1     time limit

i04_4.4_4.4_05              7             15             15             15             10              4             22              1     time limit

i04_4.4_4.4_10             15             26             34             35             23             10             32              2     time limit

i04_4.4_4.7_05             10             13             18             18             15              6             25              1     time limit

i04_4.4_4.7_10             19             26             36             36             18              7             20              1     time limit

i04_4.7_2.0_05             11             11             16             16            254            163              8              1     time limit

i04_4.7_2.0_10             17             18             27             27             51             27             17              1     time limit

i04_4.7_2.3_05              8             13             17             18             19              8             23              1     time limit

i04_4.7_2.3_10             16             20             30             31             38             19             16              1     time limit

i04_4.7_2.6_05              7             23             23             23             10              4              7              1     time limit

i04_4.7_2.6_10             16             33             33             33             10              3             10              1     time limit

i04_4.7_2.9_05              8             17             17             17             17              7             17              1     time limit

i04_4.7_2.9_10             15             32             47             54              9              3             11              1     time limit

i04_4.7_3.2_05              9             16             16             17             10              3             11              1     time limit

i04_4.7_3.2_10             18             34             34             34             13              5             14              1     time limit

i04_4.7_3.5_05              8             15             22             22              9              3             16              1     time limit

i04_4.7_3.5_10             13             42             42             42             10              4              8              1     time limit

i04_4.7_3.8_05              9             12             17             17             20              8             18              1     time limit

i04_4.7_3.8_10             16             18             26             26             41             21             20              1     time limit

i04_4.7_4.1_05             11             11             16             15             54             27             22              1     time limit

i04_4.7_4.1_10             14             34             34             34             46             24             11              1     time limit

i04_4.7_4.4_05              9             11             14             15              9              2             18              1     time limit

i04_4.7_4.4_10             17             19             25             25             52             27             23              1     time limit

i04_4.7_4.7_05             10             16             21             21             21              9             45              2     time limit

i04_4.7_4.7_10             15             23             30             33              9              3             12              1     time limit

i05_2.0_2.0_05             10             24             24             24             10              0              8              1            0.6

i05_2.0_2.0_10             20             59             59             59             10              0             10              1            1.4

i05_2.0_2.3_05             10             15             26             26             10              0              8              3            0.8

i05_2.0_2.3_10             19             47             47             47             10              0             10              1            0.7

i05_2.0_2.6_05             11             31             31             32              9              0             12              1            0.8

i05_2.0_2.6_10             17             46             46             46             10              0             15              1            0.7

i05_2.0_2.9_05              9             33             33             33              9              0             10              1            0.7

i05_2.0_2.9_10             27             50             50             50             10              0             14              1            1.9

i05_2.0_3.2_05             10             26             26             26              9              0             15              1            0.6

i05_2.0_3.2_10             20             40             40             40             11              0             13              1            0.8

i05_2.0_3.5_05              9             13             19             19             10              0             31              3            0.9

i05_2.0_3.5_10             20             25             37             40             10              0             29              3            0.9

i05_2.0_3.8_05             14             15             22             23             11              0             18              3            1.1

i05_2.0_3.8_10             19             44             44             44             10              0             10              1            0.8

i05_2.0_4.1_05              9             15             20             21              8              0             30              5            0.9

i05_2.0_4.1_10             24             32             48             48             10              0             22              3            1.1

i05_2.0_4.4_05              9             12             18             19             10              0             27              3            0.7

i05_2.0_4.4_10             21             29             40             43             10              0             23              3            0.6

i05_2.0_4.7_05             10             15             23             22              9              0             25              3            0.9

i05_2.0_4.7_10             17             25             34             36             10              0             22              3            0.8

i05_2.3_2.0_05             11             24             24             26             10              0              7              1            1.1

i05_2.3_2.0_10             27             38             53             58             12              0             14              3            2.5

i05_2.3_2.3_05             10             24             33             33              8              0              7              3            1.4

i05_2.3_2.3_10             18             61             61             61             10              0             11              1            1.4

i05_2.3_2.6_05              9             40             40             40             10              0             11              1            1.1

i05_2.3_2.6_10             27             34             52             55             13              0             16              3            3.2

i05_2.3_2.9_05              8             30             30             30             10              0              7              1            2.2

i05_2.3_2.9_10             24             61             61             61             12              0             21              1            9.7

i05_2.3_3.2_05              9             32             32             32              9              0             15              1            1.3

i05_2.3_3.2_10             29             34             47             50             14              0             29              3            5.2

i05_2.3_3.5_05             12             17             24             25             13              0             23              4            6.0

i05_2.3_3.5_10             17             23             32             34             12              0             18              3            2.0

i05_2.3_3.8_05             12             14             20             21             15              1             38              3           10.9

i05_2.3_3.8_10             33             36             52             55             17              0             28              3           10.7

i05_2.3_4.1_05              9             12             16             16             12              0             39              3            2.1

i05_2.3_4.1_10             16             27             37             39             10              0             19              3            1.5

i05_2.3_4.4_05              9             15             23             24              9              0             33              3            1.5

i05_2.3_4.4_10             17             34             51             51              8              0             12              3            1.4

i05_2.3_4.7_05              9             14             18             19             10              0             41              3            1.4

i05_2.3_4.7_10             17             26             34             36             10              0             25              3            1.1

i05_2.6_2.0_05              9             12             19             20             11              0             11              3            2.5

i05_2.6_2.0_10             18             28             41             41             10              0              7              3            2.1

i05_2.6_2.3_05             12             24             24             24             15              1             13              1           10.5

i05_2.6_2.3_10             22             45             54             56             10              0             13              3            4.5

i05_2.6_2.6_05              9             36             36             26             10              0             10              1            3.1

i05_2.6_2.6_10             19             49             49             49             10              0             12              1            3.0

i05_2.6_2.9_05             13             17             23             23             17              3             28              3     time limit

i05_2.6_2.9_10             18             58             58             58             10              0              9              1            3.4

i05_2.6_3.2_05              9             22             22             22             10              0             15              1            2.6

i05_2.6_3.2_10             16             76             76             76             14              0             13              1           15.6

i05_2.6_3.5_05              9             12             17             18             12              0             25             13            4.4

i05_2.6_3.5_10             21             29             40             41             11              0             26              6            3.5

i05_2.6_3.8_05              9             16             21             22             10              0             31              3            3.7

i05_2.6_3.8_10             16             21             29             29             12              0             19              3            6.3

i05_2.6_4.1_05              9             15             20             21             10              0             43              3            2.6

i05_2.6_4.1_10             17             33             45             46              8              0             27              3            5.0

i05_2.6_4.4_05              8             11             15             16             13              0             26              3            7.1

i05_2.6_4.4_10             21             30             43             45             10              0             24              3            4.0

i05_2.6_4.7_05             10             13             17             18             13              0             48              3            5.7

i05_2.6_4.7_10             21             31             41             41             10              0             33              3            2.7

i05_2.9_2.0_05             10             15             22             23             15              2             14              1           74.2

i05_2.9_2.0_10             26             29             48             49             24              6             11              1         3994.6

i05_2.9_2.3_05              8             27             27             27              8              0              5              1           19.2

i05_2.9_2.3_10             20             45             67             67             10              1              7              3           20.6

i05_2.9_2.6_05             10             27             27             27             10              0             14              1           16.7

i05_2.9_2.6_10             19             44             44             44             10              0             12              1           19.5

i05_2.9_2.9_05             13             16             24             24             22              3             31              1         4983.5

i05_2.9_2.9_10             22             46             46             46             12              1             27              1          817.1

i05_2.9_3.2_05              8             18             18             19             13              1             18              1           23.5

i05_2.9_3.2_10             22             47             47             47             22              4             12              1          369.7

i05_2.9_3.5_05             12             14             20             19             17              3             36              1         3887.4

i05_2.9_3.5_10             27             31             43             45             19              3             28              1         2519.3

i05_2.9_3.8_05              8             15             20             21              9              0             26              3           14.5

i05_2.9_3.8_10             23             30             44             45             18              3             31              3          264.7

i05_2.9_4.1_05              9             15             21             22             10              0             26              3           15.4

i05_2.9_4.1_10             29             36             47             51             22              4             49              3         1080.0

i05_2.9_4.4_05             13             14             20             20             52             20             27              2     time limit

i05_2.9_4.4_10             20             32             44             44             10              0             28              3           15.2

i05_2.9_4.7_05              9             14             18             18             11              0             38              3           10.4

i05_2.9_4.7_10             15             25             32             32             10              0             29              3           10.6

i05_3.2_2.0_05             10             14             22             22             21              4             13              1         1379.4

i05_3.2_2.0_10             20             29             43             45             21              5             17              3         1102.0

i05_3.2_2.3_05              9             13             19             20             33             11             15              1         3045.5

i05_3.2_2.3_10             18             47             65             65             13              4             10              1          261.1

i05_3.2_2.6_05              9             19             24             26             18              4             12              4     time limit

i05_3.2_2.6_10             29             51             51             52             19              4             14              1         4556.8

i05_3.2_2.9_05             10             43             43             43              8              0             10              1          318.9

i05_3.2_2.9_10             16             39             39             39             19              4             10              1          378.9

i05_3.2_3.2_05              9             29             29             29             11              1              8              1          246.1

i05_3.2_3.2_10             18             38             38             38             10              0             10              1          211.9

i05_3.2_3.5_05              8             13             18             19             12              1             26              3          358.4

i05_3.2_3.5_10             18             30             44             51             10              0             19              3          325.0

i05_3.2_3.8_05             12             13             20             22             48             18             27              1     time limit

i05_3.2_3.8_10             14             23             31             34             10              0             32              3     time limit

i05_3.2_4.1_05              9             17             22             21             19              6             12             97         5083.6

i05_3.2_4.1_10             17             20             27             27             26              6             37              1     time limit

i05_3.2_4.4_05             10             17             25             25              7              0             14              3          540.1

i05_3.2_4.4_10             17             23             39             39              9              0             23              9          371.1

i05_3.2_4.7_05             10             11             17             19             10              0             32              3          158.5

i05_3.2_4.7_10             18             26             35             36             14              3             44              2          195.1

i05_3.5_2.0_05             13             14             22             24            117             67             12              1     time limit

i05_3.5_2.0_10             27             60             60             60             27              6             12              1     time limit

i05_3.5_2.3_05              9             17             19             20             55             26             13              2     time limit

i05_3.5_2.3_10             20             28             41             42             30             10             16              1     time limit

i05_3.5_2.6_05             13             17             22             22             27              7             27              1     time limit

i05_3.5_2.6_10             20             47             47             47             12              2             13              1         4237.1

i05_3.5_2.9_05             10             11             22             23             11              2             39              1     time limit

i05_3.5_2.9_10             16             30             40             41             15              3             22              1     time limit

i05_3.5_3.2_05              9             14             20             22             11              1             26              1     time limit

i05_3.5_3.2_10             19             96             96             96             35             13              6              1     time limit

i05_3.5_3.5_05             10             15             20             21             16              3             28             16     time limit

i05_3.5_3.5_10             15             60             60             60             13              4             11              3         5548.7

i05_3.5_3.8_05             11             18             20             21             22              6             28             11     time limit

i05_3.5_3.8_10             15             52             52             52             10              2             13              1     time limit

i05_3.5_4.1_05              9             27             27             24              8              0             11              1         3572.4

i05_3.5_4.1_10             19             23             31             35             77             37             24              2     time limit

i05_3.5_4.4_05              9             16             22             23             29              9             28              3     time limit

i05_3.5_4.4_10             16             23             31             32             22              6             23              1     time limit

i05_3.5_4.7_05              9             12             18             19             26              7             19             14     time limit

i05_3.5_4.7_10             16             46             46             50             12              3             26              1         4915.6

i05_3.8_2.0_05              8             27             27             27             14              5              8              1     time limit

i05_3.8_2.0_10             18             55             55             55             11              2              5              1     time limit

i05_3.8_2.3_05             14             22             24             25             43             17             19              1     time limit

i05_3.8_2.3_10             16             38             38             38             16              4             11              1     time limit

i05_3.8_2.6_05             17             17             24             24            521            353             22              7     time limit

i05_3.8_2.6_10             16             52             52             52             12              2             11              1     time limit

i05_3.8_2.9_05              8             42             42             42             21              8              5              1     time limit

i05_3.8_2.9_10             20             33             42             44             21              7             24              3     time limit

i05_3.8_3.2_05             13             14             18             19            135             76             42              9     time limit

i05_3.8_3.2_10             18             41             41             41             14              3             20              1     time limit

i05_3.8_3.5_05              9             36             36             36             12              4             10              1     time limit

i05_3.8_3.5_10             16             40             40             45             11              2             13              1     time limit

i05_3.8_3.8_05              8             25             25             31             10              2             12              1     time limit

i05_3.8_3.8_10             18             27             36             37             16              4             33              3     time limit

i05_3.8_4.1_05              9             14             19             19             79             46             37             10     time limit

i05_3.8_4.1_10             18             26             34             35             28              9             22              3     time limit

i05_3.8_4.4_05              8             11             16             16             63             33             26              1     time limit

i05_3.8_4.4_10             16             23             39             38             18              6             25              1     time limit

i05_3.8_4.7_05              8             16             22             23             15              6             26              3     time limit

i05_3.8_4.7_10             18             24             39             42             33             13             23              5     time limit

i05_4.1_2.0_05              9             23             23             23             21              7             13              1     time limit

i05_4.1_2.0_10             19             39             41             43             14              4             12              1     time limit

i05_4.1_2.3_05             10             24             24             24             14              4             14              1     time limit

i05_4.1_2.3_10             22             52             52             54             16              6             13              1     time limit

i05_4.1_2.6_05             10             15             19             20             42             19             14              1     time limit

i05_4.1_2.6_10             26             45             45             45             65             32             10              1     time limit

i05_4.1_2.9_05             13             15             21             21             64             32             31              4     time limit

i05_4.1_2.9_10             17             51             51             51             24              8             13              1     time limit

i05_4.1_3.2_05             10             18             25             27             23              8             27              1     time limit

i05_4.1_3.2_10             16             61             61             61             14              5             11              1     time limit

i05_4.1_3.5_05             10             12             16             17             47             21             29              1     time limit

i05_4.1_3.5_10             19             27             35             36             33             12             32              2     time limit

i05_4.1_3.8_05              9             13             19             21             11              1             10              3     time limit

i05_4.1_3.8_10             17             38             38             40             11              2             10              1     time limit

i05_4.1_4.1_05             10             14             20             20             41             17             36              1     time limit

i05_4.1_4.1_10             25             31             43             43             56             28             42              1     time limit

i05_4.1_4.4_05             10             12             15             15             13              2             37              1     time limit

i05_4.1_4.4_10             16             26             37             39             13              4             26              3     time limit

i05_4.1_4.7_05              9             11             17             17             10              1             24              3     time limit

i05_4.1_4.7_10             19             34             45             45             41             19             28              1     time limit

i05_4.4_2.0_05              9             23             23             23             14              4             13              1     time limit

i05_4.4_2.0_10             16             37             37             37             44             20             14              1     time limit

i05_4.4_2.3_05              9             19             19             19             13              2             10              1     time limit

i05_4.4_2.3_10             16             30             43             43             93             53             12              1     time limit

i05_4.4_2.6_05              9             23             23             23             38             15             11              1     time limit

i05_4.4_2.6_10             16             70             70             70             11              2              6              1     time limit

i05_4.4_2.9_05             10             27             27             27             23              9             14              1     time limit

i05_4.4_2.9_10             26             30             41             40            106             60             24              1     time limit

i05_4.4_3.2_05              8             25             25             25             28             12             10              1     time limit

i05_4.4_3.2_10             17             64             64             64             15              5              7              1     time limit

i05_4.4_3.5_05              9             21             21             21             14              4             13              1     time limit

i05_4.4_3.5_10             18             43             44             43             14              4             12              3     time limit

i05_4.4_3.8_05              9             21             21             23            129             75             14              1     time limit

i05_4.4_3.8_10             18             28             41             43             30             12             36              1     time limit

i05_4.4_4.1_05              8             13             18             18             20              7             23              1     time limit

i05_4.4_4.1_10             21             33             48             49             15              6             29              1     time limit

i05_4.4_4.4_05              9             14             19             20             16              4             33              1     time limit

i05_4.4_4.4_10             16             25             36             37             23              9             52              2     time limit

i05_4.4_4.7_05             11             16             20             21             13              3             32              6     time limit

i05_4.4_4.7_10             18             21             37             39             16              6             25              1     time limit

i05_4.7_2.0_05              8             10             15             15             29             11             12              1     time limit

i05_4.7_2.0_10             18             27             39             39             16              4             17              1     time limit

i05_4.7_2.3_05              9             33             33             33             14              6              5              1     time limit

i05_4.7_2.3_10             20             33             35             38            190            116             14              3     time limit

i05_4.7_2.6_05              9             12             16             17            152             94             30              1     time limit

i05_4.7_2.6_10             25             28             38             41            446            291             28              1     time limit

i05_4.7_2.9_05              9             18             18             18             25              9             15              1     time limit

i05_4.7_2.9_10             21             67             67             67             59             31             13              1     time limit

i05_4.7_3.2_05              8             33             33             33             87             50              7              1     time limit

i05_4.7_3.2_10             17             26             39             40             20              7             40              2     time limit

i05_4.7_3.5_05             10             15             23             23            139             87             22              2     time limit

i05_4.7_3.5_10             19             28             41             44             18              6             47             25     time limit

i05_4.7_3.8_05              8             13             17             18             31             13             45              3     time limit

i05_4.7_3.8_10             16             28             39             43             21              8             33              2     time limit

i05_4.7_4.1_05             10             13             19             20             20              8             36              2     time limit

i05_4.7_4.1_10             18             26             34             35             35             14             38              1     time limit

i05_4.7_4.4_05              8             12             16             16             19              6             57             32     time limit

i05_4.7_4.4_10             20             27             38             38             14              4             48              1     time limit

i05_4.7_4.7_05              9             15             20             20             17              6             40              4     time limit

i05_4.7_4.7_10             29             31             46             44            140             88             46             32     time limit

i10_2.0_2.0_05             15             38             38             38             37              0             10              1            1.3

i10_2.0_2.0_10             37             73             73             73             40              0             15              1            2.9

i10_2.0_2.3_05             16             65             65             65             36              0             10              1            1.5

i10_2.0_2.3_10             37             94             94             95             40              0             20              1            2.7

i10_2.0_2.6_05             22             28             48             50             39              0             28              3            5.8

i10_2.0_2.6_10             26             87             87             87             38              0             15              1            2.4

i10_2.0_2.9_05             15             57             57             57             36              0             20              1            2.3

i10_2.0_2.9_10             45            127            127            127             38              0             22              1            5.2

i10_2.0_3.2_05             15             82             82             82             30              0             12              1            1.7

i10_2.0_3.2_10             34            101            101            101             35              0             26              1            4.3

i10_2.0_3.5_05             15             20             29             29             43              0             28              3            2.7

i10_2.0_3.5_10             47             58             89             91             38              0             39              3            7.2

i10_2.0_3.8_05             20             23             35             36             41              0             39              3            4.5

i10_2.0_3.8_10             36             39             57             58             40              0             45              7            2.6

i10_2.0_4.1_05             17             22             31             31             40              0             58              3            4.7

i10_2.0_4.1_10             29             48             71             74             38              0             27             17            1.3

i10_2.0_4.4_05             18             21             30             31             40              0             39              3            2.5

i10_2.0_4.4_10             28             34             59             58             38              0             37              3            1.5

i10_2.0_4.7_05             18             21             32             34             39              0             50              3            2.2

i10_2.0_4.7_10             43             55             81             89             33              0             53              3            9.7

i10_2.3_2.0_05             18             48             48             48             42              0             13              1           15.4

i10_2.3_2.0_10             25             63             63             63             37              0             10              1            2.8

i10_2.3_2.3_05             14             57             57             57             37              0             14              1            3.8

i10_2.3_2.3_10             47             62            101            101             46              0             19              3           18.6

i10_2.3_2.6_05             14             53             53             53             40              0             18              1            5.2

i10_2.3_2.6_10             28            100            100            100             37              0             18              1            4.2

i10_2.3_2.9_05             18             44             44             44             45              0             24              1           12.2

i10_2.3_2.9_10             26            132            132            132             33              0             13              1            5.4

i10_2.3_3.2_05             19             54             54             54             45              0             26              1           12.3

i10_2.3_3.2_10             35             41             62             66             48              0             51              3           21.2

i10_2.3_3.5_05             17             19             28             30             41              0             39              3            4.3

i10_2.3_3.5_10             35             59             85             85             44              0             36              4           13.2

i10_2.3_3.8_05             13             28             41             42             33              0             41              3            3.9

i10_2.3_3.8_10             47             52             76             92             66              0             50              3           44.9

i10_2.3_4.1_05             17             21             29             31             43              0             35             11            6.6

i10_2.3_4.1_10             27             50             72             76             37              0             35              3            3.1

i10_2.3_4.4_05             15             23             34             35             39              0             56              3           10.3

i10_2.3_4.4_10             26             37             58             60             40              0             48              3            4.6

i10_2.3_4.7_05             14             23             38             37             36              0             39             17            3.0

i10_2.3_4.7_10             35             39             58             64             48              0             50              7           20.5

i10_2.6_2.0_05             18             36             36             38             69              3             27              1     time limit

i10_2.6_2.0_10             28             58             73             73             43              0             16              3           12.8

i10_2.6_2.3_05             15             45             45             45             29              0             14              1            7.1

i10_2.6_2.3_10             29             93             93            117             32              0             10              1           14.7

i10_2.6_2.6_05             18             25             38             40            102             11             26              3     time limit

i10_2.6_2.6_10             28            120            120            120             36              0             14              1            9.2

i10_2.6_2.9_05             17             24             34             36             49              1             38              3          703.8

i10_2.6_2.9_10             27             99             99             99             43              0             24              1           65.9

i10_2.6_3.2_05             14             26             39             42             36              0             36              3            8.3

i10_2.6_3.2_10             37             76             76             80             37              1             48              1           12.2

i10_2.6_3.5_05             20             37             55             57             35              1             27              7           23.1

i10_2.6_3.5_10             28             92             92             92             44              1             29              1         4337.2

i10_2.6_3.8_05             15             24             32             39             45              0             33              3           19.3

i10_2.6_3.8_10             29             43             58             59             40              0             46              7            9.7

i10_2.6_4.1_05             26             26             40             45            409            266             85             38     time limit

i10_2.6_4.1_10             30             57             82             84             35              0             43              3           13.8

i10_2.6_4.4_05             20             39             39             39            148             14             38              1     time limit

i10_2.6_4.4_10             26             45             62             64             42              0             47              3           18.1

i10_2.6_4.7_05             14             25             37             38             36              0             33              6            7.8

i10_2.6_4.7_10             33             39             57             61             55              1             61              3           68.5

i10_2.9_2.0_05             20             20             33             36            591            437             28              4     time limit

i10_2.9_2.0_10             27             71             71             71             41              1             16              1           34.6

i10_2.9_2.3_05             14             55             55             55             40              1             16              1           20.5

i10_2.9_2.3_10             26             68             68             83             43              1             26              1           34.0

i10_2.9_2.6_05             18             54             54             54             83             17             29              1     time limit

i10_2.9_2.6_10             27             48             73             79             99             15             26              3          435.3

i10_2.9_2.9_05             19             24             34             36             81             14             31             10         5081.9

i10_2.9_2.9_10             36             89             89             89             58              5             29              1         1103.7

i10_2.9_3.2_05             13             32             32             34             44              2             39              1           31.3

i10_2.9_3.2_10             25             41             64             71             49              3             33              3           88.7

i10_2.9_3.5_05             15             21             32             33             38              0             56              3           16.3

i10_2.9_3.5_10             30             37             54             61             48              2             63              3           50.3

i10_2.9_3.8_05             22             26             35             37            197             94             50            125     time limit

i10_2.9_3.8_10             35             49             68             72             90             16             48              3          526.4

i10_2.9_4.1_05             15             23             32             32             44              2             44              3           36.0

i10_2.9_4.1_10             29             39             58             71             59              5             49              3          229.0

i10_2.9_4.4_05             13             21             29             30             78             12             48              3         3472.1

i10_2.9_4.4_10             27             45             68             74             39              2             63              3           42.2

i10_2.9_4.7_05             15             24             34             36             38              0             55             25           24.8

i10_2.9_4.7_10             25             42             60             64             40              0             47             12           58.3

i10_3.2_2.0_05             13             36             36             36             54             10             13              1          667.3

i10_3.2_2.0_10             30             64             65             69             80             20             18              1     time limit

i10_3.2_2.3_05             12             24             35             37            250            157             34              3     time limit

i10_3.2_2.3_10             26            126            126            126             39              1             10              1          194.4

i10_3.2_2.6_05             15             26             41             41            530            400             19              3     time limit

i10_3.2_2.6_10             32             52             61             70             89             23             37              1     time limit

i10_3.2_2.9_05             14             20             29             32             79             19             45              4          708.9

i10_3.2_2.9_10             31             66             66             66             62             11             31              1         1282.6

i10_3.2_3.2_05             14             24             36             38             74             15             27              3         2195.9

i10_3.2_3.2_10             28             40             62             67             65             13             65              3     time limit

i10_3.2_3.5_05             14             23             33             34             80             20             63              2         2882.0

i10_3.2_3.5_10             28             42             58             64             99             26             28              3     time limit

i10_3.2_3.8_05             15             20             27             29             62              8             54             40     time limit

i10_3.2_3.8_10             33             39             59             61            232            152             39              4     time limit

i10_3.2_4.1_05             13             20             31             30             99             28             38              3         4442.3

i10_3.2_4.1_10             28             35             55             55             45              3             39              9          358.9

i10_3.2_4.4_05             15             19             28             29            107             35             56             45     time limit

i10_3.2_4.4_10             33             33             59             63            180             93             77             13     time limit

i10_3.2_4.7_05             13             19             28             30             72             14             45              3     time limit

i10_3.2_4.7_10             34             35             66             67            619            457             77             98     time limit

i10_3.5_2.0_05             22             23             38             41           1475           1075             36              5     time limit

i10_3.5_2.0_10             29             96             96             96             76             16             10              4     time limit

i10_3.5_2.3_05             23             46             46             46            727            502             28             15     time limit

i10_3.5_2.3_10             28            123            123            123             34              0             10              1     time limit

i10_3.5_2.6_05             13             36             36             39             55             11             23              1     time limit

i10_3.5_2.6_10             26             56             56             56            567            407             22              1     time limit

i10_3.5_2.9_05             13             55             55             55             45              4             17              1     time limit

i10_3.5_2.9_10             26             89             89             89            264            164             20              1     time limit

i10_3.5_3.2_05             15             51             51             51             39              5             16              1     time limit

i10_3.5_3.2_10             28             40             63             66             63             12             46             13     time limit

i10_3.5_3.5_05             15             42             42             42            386            253             26              8     time limit

i10_3.5_3.5_10             32             52             56             58            661            479             33              1     time limit

i10_3.5_3.8_05             13             32             32             32             81             21             31              2     time limit

i10_3.5_3.8_10             29             47             70             73             37              2             32              5     time limit

i10_3.5_4.1_05             19             25             32             33            106             31             51             12     time limit

i10_3.5_4.1_10             30             39             60             60             79             22             55             42     time limit

i10_3.5_4.4_05             15             25             36             36             48              7             72             92     time limit

i10_3.5_4.4_10             28             43             66             68            315            203             50            207     time limit

i10_3.5_4.7_05             17             19             31             32            452            284             73             50     time limit

i10_3.5_4.7_10             26             40             58             62            108             33             45              3     time limit

i10_3.8_2.0_05             22             22             34             36           3079           2293             33              2     time limit

i10_3.8_2.0_10             39             87             87             89            364            216             10              2     time limit

i10_3.8_2.3_05             15             20             43             41            181            113             17              1     time limit

i10_3.8_2.3_10             25             78             78             78             71             20             15              1     time limit

i10_3.8_2.6_05             13             31             32             33            251            166             34              3     time limit

i10_3.8_2.6_10             39             53             79             85            214            137             31              6     time limit

i10_3.8_2.9_05             16             19             29             31            601            436             35              2     time limit

i10_3.8_2.9_10             39             96             96             96           1216            900             26              1     time limit

i10_3.8_3.2_05             14             21             31             33             48              8             31              3     time limit

i10_3.8_3.2_10             39             46             78             82            811            630             66              3     time limit

i10_3.8_3.5_05             13             34             34             34            617            415             25              2     time limit

i10_3.8_3.5_10             34             53             79             98            176             94             20              3     time limit

i10_3.8_3.8_05             18             21             32             39            947            689             47             23     time limit

i10_3.8_3.8_10             34             38             59             65            879            646             54              6     time limit

i10_3.8_4.1_05             13             18             27             29            677            497             48             32     time limit

i10_3.8_4.1_10             29             44             68             67            100             46             41             25     time limit

i10_3.8_4.4_05             13             21             36             34            408            270             42              2     time limit

i10_3.8_4.4_10             29             34             51             53           1174            909             50              3     time limit

i10_3.8_4.7_05             13             21             36             36            193            110             52              2     time limit

i10_3.8_4.7_10             28             41             63             68            193            118             54              6     time limit

i10_4.1_2.0_05             14             41             41             41            160             97             26              2     time limit

i10_4.1_2.0_10             25             39             62             67           1333           1020             25             52     time limit

i10_4.1_2.3_05             14             56             56             45            146             88             12              1     time limit

i10_4.1_2.3_10             27             91             91             91             73             21             21              1     time limit

i10_4.1_2.6_05             13             31             54             54            121             64             18              1     time limit

i10_4.1_2.6_10             25             60             60             60            336            225             16              1     time limit

i10_4.1_2.9_05             15             33             33             33             57             12             30              1     time limit

i10_4.1_2.9_10             31             91             91             91            128             62             27              1     time limit

i10_4.1_3.2_05             13             15             24             26            382            270             67              2     time limit

i10_4.1_3.2_10             26             67             72             77           1350            992             56             11     time limit

i10_4.1_3.5_05             15             36             37             39            153             83             41              3     time limit

i10_4.1_3.5_10             28             45             61             62             76             22             58              1     time limit

i10_4.1_3.8_05             20             21             37             39            305            195             70              9     time limit

i10_4.1_3.8_10             36             44             69             71            255            160             67              4     time limit

i10_4.1_4.1_05             15             19             29             32            163             91             49             12     time limit

i10_4.1_4.1_10             27             54             90             92            322            212             23             52     time limit

i10_4.1_4.4_05             18             18             30             32            673            439             47             30     time limit

i10_4.1_4.4_10             27             34             55             57            205            112             61             10     time limit

i10_4.1_4.7_05             15             23             32             32            123             55             72              2     time limit

i10_4.1_4.7_10             28             55             80             85             64             19             41              8     time limit

i10_4.4_2.0_05             13             20             31             33           1128            856             23              3     time limit

i10_4.4_2.0_10             31             48             82             87           1222            958             32              2     time limit

i10_4.4_2.3_05             18             31             33             34            544            358             44              1     time limit

i10_4.4_2.3_10             27             68             68             68            247            158             26              1     time limit

i10_4.4_2.6_05             13             22             39             40            172            104             27              1     time limit

i10_4.4_2.6_10             29             66             70             70            459            321             17              1     time limit

i10_4.4_2.9_05             15             45             45             51            103             60             27              1     time limit

i10_4.4_2.9_10             26             77             77             77            433            295             16              1     time limit

i10_4.4_3.2_05             14             35             35             35             75             23             22              1     time limit

i10_4.4_3.2_10             39             69             69             69            322            188             27              1     time limit

i10_4.4_3.5_05             17             20             31             33          14181          11455             49              3     time limit

i10_4.4_3.5_10             28             76             76             76            602            404            107              2     time limit

i10_4.4_3.8_05             13             21             32             33            438            311             61              3     time limit

i10_4.4_3.8_10             26             41             72             77            420            287             62              2     time limit

i10_4.4_4.1_05             14             19             29             31            249            169             83            120     time limit

i10_4.4_4.1_10             28             41             62             61             56             17             27              1     time limit

i10_4.4_4.4_05             19             21             33             41           1879           1452             99             71     time limit

i10_4.4_4.4_10             28             51             73             75             75             32             45              9     time limit

i10_4.4_4.7_05             14             18             29             30            309            216             70              9     time limit

i10_4.4_4.7_10             30             44             60             63             70             23             58             16     time limit

i10_4.7_2.0_05             16             40             41             41            110             58             22              1     time limit

i10_4.7_2.0_10             27            103            103            103            334            222             10              1     time limit

i10_4.7_2.3_05             15             47             47             48            288            189             20              1     time limit

i10_4.7_2.3_10             36             76             76             76            428            282             18              1     time limit

i10_4.7_2.6_05             15             26             39             39            214            136             31              3     time limit

i10_4.7_2.6_10             27             63             63             64            676            476             18              1     time limit

i10_4.7_2.9_05             20             21             37             39            559            383             74              3     time limit

i10_4.7_2.9_10             26             65             65             72             66             18             34              1     time limit

i10_4.7_3.2_05             18             31             34             39           2181           1555             44              2     time limit

i10_4.7_3.2_10             29             65             75             78            192            128             57              2     time limit

i10_4.7_3.5_05             13             19             31             31           1734           1326             51             20     time limit

i10_4.7_3.5_10             27             28             50             54            603            412             52             10     time limit

i10_4.7_3.8_05             13             19             28             32             82             38             46              8     time limit

i10_4.7_3.8_10             29             37             56             62            224            135             36              3     time limit

i10_4.7_4.1_05             20             20             32             34           3538           2686             55              3     time limit

i10_4.7_4.1_10             27             42             64             68            807            617             48              3     time limit

i10_4.7_4.4_05             15             26             38             40             61             17             57              2     time limit

i10_4.7_4.4_10             24             37             57             59            267            186             83             77     time limit

i10_4.7_4.7_05             14             22             32             34            412            259             57            123     time limit

i10_4.7_4.7_10             28             42             69             78            782            578             87              3     time limit

 
 
