Scippy

    SCIP

    Solving Constraint Integer Programs

    xternal_ringpacking.c
    Go to the documentation of this file.
    1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    2/* */
    3/* This file is part of the program and library */
    4/* SCIP --- Solving Constraint Integer Programs */
    5/* */
    6/* Copyright (c) 2002-2026 Zuse Institute Berlin (ZIB) */
    7/* */
    8/* Licensed under the Apache License, Version 2.0 (the "License"); */
    9/* you may not use this file except in compliance with the License. */
    10/* You may obtain a copy of the License at */
    11/* */
    12/* http://www.apache.org/licenses/LICENSE-2.0 */
    13/* */
    14/* Unless required by applicable law or agreed to in writing, software */
    15/* distributed under the License is distributed on an "AS IS" BASIS, */
    16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
    17/* See the License for the specific language governing permissions and */
    18/* limitations under the License. */
    19/* */
    20/* You should have received a copy of the Apache-2.0 license */
    21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
    22/* */
    23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    24
    25/**@file xternal_ringpacking.c
    26 * @brief The ringpacking application of SCIP
    27 * @author Benjamin Mueller
    28 */
    29
    30/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    31
    32/**@page RINGPACKING_MAIN Ringpacking
    33 * @author Benjamin Mueller
    34 *
    35 * This application contains a branch-and-price approach for the Ringpacking problem, also known as recursive circle
    36 * packing problem, which is realized with the framework \SCIP. Therefore, the following plugins are implemented:
    37 *
    38 * - a \ref reader_rpa.c "problem reader" which parses the problem out of a file and creates the corresponding problem within \SCIP
    39 * - a \ref probdata_rpa.c "(global) problem data structure" which contains all necessary information
    40 * - a \ref pricer_rpa.c "pricer" which generates new variables/columns during the search
    41 * - a \ref cons_rpa.c "constraint handler" which stores information about which patterns have been verified
    42 * - a \ref pattern.c "variable data structure" which provides fundamental functions for handling patterns
    43 *
    44 * In the following we introduce the problem, explain the use of the reader plugin and pricer plugin.
    45 *
    46 * -# \subpage RINGPACKING_PROBLEM "Problem description"
    47 * -# \subpage RINGPACKING_READER "Parsing the input format and creating the problem"
    48 * -# \subpage RINGPACKING_PROBLEMDATA "Main problem data"
    49 * -# \subpage RINGPACKING_PRICER "Pricing new variables"
    50 * -# \subpage RINGPACKING_ENUMERATION "Enumerating circular patterns"
    51 *
    52 * Installation
    53 * ------------
    54 *
    55 * See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
    56 */
    57
    58/**@page RINGPACKING_PROBLEM Problem description
    59 *
    60 * The objective of the Ringpacking Problem is to select a minimum number of rectangles of the same size such that a
    61 * given set of rings can be packed into these rectangles in a non-overlapping way. A ring is characterized by an
    62 * internal and an external radius. Rings can be put recursively into larger ones or directly into a rectangle. The
    63 * following picture gives two examples of such packings:
    64 *
    65 *
    66 * <CENTER>
    67 * \image html ringpacking.png
    68 * </CENTER>
    69 *
    70 *
    71 * Instead of using a compact noncovex MINLP formulation, we utilize the results from A. Gleixner, S. Maher, B. Mueller,
    72 * and J. Pedroso that have been presented in <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6449">ZIB-Report 17-07</a>.
    73 * Their approach is based on a Dantzig-Wolfe decomposition that can be solved via column generation. The first step
    74 * is a reformulation which is similar to the classical reformulation for the Cutting Stock Problem, however, featuring
    75 * nonlinear and nonconvex sub-problems. The purpose of this formulation is to break the symmetry between equivalent rectangles.
    76 * As a second step, we combine this reformulation with an enumeration scheme for patterns that are characterized by rings
    77 * packed inside other rings. Such patterns only allow for a one-level recursion and break the symmetry between rings with the
    78 * same internal and external radius in each rectangle.
    79 *
    80 * More precisely, we introduce an integral variable \f$z_{P}\f$ for each rectangular pattern \f$P\f$ and an integral
    81 * variable \f$z_{C}\f$ for each circular pattern \f$C\f$. A vector \f$P \in \mathbb{Z}_{+}^T\f$, where \f$T\f$ is
    82 * the total number of ringtypes, is a <b>rectangular pattern</b> if and only if \f$P_t\f$ many circles with external radius
    83 * \f$R_t\f$ for each \f$t \in \mathcal{T}\f$ (the set of types) can be packed together into a rectangle. Similarly, a tuple
    84 * \f$(t,P)\in \mathcal{T} \times \mathbb{Z}_{+}^T\f$ is a <b>circular pattern</b> if it is possible to pack \f$P_1\f$ many
    85 * circles of type \f$1\f$, \f$P_2\f$ many circles of type \f$2\f$, \f$\ldots\f$, \f$P_T\f$ many circles of type \f$T\f$
    86 * into a larger ring of type \f$t\f$. Let \f$\mathcal{RP}\f$ and \f$\mathcal{CP}\f$ be the set of all rectangular or
    87 * circular patterns, respectively, and let \f$D_t\f$ denote the demand of ringtype \f$t\f$.
    88 *
    89 * Then the problem can be formulated as follows:
    90 *
    91 * \f[
    92 * \begin{align}
    93 * && \min \sum_{P \in \mathcal{RP}} z_P \quad\,\\
    94 * && \text{s.t.} \sum_{C = (t,P) \in \mathcal{CP}} z_C &\ge D_t && \text{ for all } t \in \mathcal{T} \\
    95 * && \sum_{C = (t,P) \in \mathcal{CP}} z_C &\le \sum_{P \in \mathcal{RP}} P_t \cdot z_P + \sum_{C = (t',P) \in \mathcal{CP}} P_t \cdot z_C && \text{ for all } t \in \mathcal{T} \\
    96 * && z_C & \in \mathbb{Z}_{+} && \text{ for all } C \in \mathcal{CP} \\
    97 * && z_P & \in \mathbb{Z}_{+} && \text{ for all } P \in \mathcal{RP}
    98 * \end{align}
    99 * \f]
    100 *
    101 * The objective minimizes the total number of used rectangles. The first constraint ensures that the demand for each
    102 * ring type is satisfied. The recursive decisions how to place rings into each other are implicitly modeled by the
    103 * second type of constraints. Each selection of a pattern allows us to choose \f$P_t\f$ circular patterns of the type
    104 * \f$(t,P)\f$. Note that at least one rectangular pattern needs to be selected before circular patterns can be packed.
    105 * This is true because the largest ring only fits into a rectangular pattern.
    106 *
    107 * Since \f$\mathcal{RP}\f$ can be of exponential size, we are using a column generation approach to solve this
    108 * problem. We initialize the (master) problem with a set of variables representing a selection of rectangular patterns
    109 * that are easy to verify. Now, we have to iteratively search for variables representing "better" patterns, i.e.,
    110 * a pattern which reduces the overall cost. Let \f$\lambda\f$ be the non-negative vector of dual multipliers for
    111 * the recursive constraints after solving the LP relaxation of the restricted master problem for the
    112 * current set of rectangular patterns. To compute a rectangular pattern with negative reduced cost we solve
    113 *
    114 * \f[
    115 * \begin{equation}
    116 * \min_{P \in \mathcal{RP}} \left\{1 - \sum_{t \in \mathcal{T}} \lambda_t P_t\right\}.
    117 * \end{equation}
    118 * \f]
    119 *
    120 * This problem is NP-hard and can be very difficult to solve. However, even if it cannot be solved to optimality within the
    121 * given time limit, any solution with negative reduced cost can be used to continue the solving process. In that case, a
    122 * dual bound of the LP relaxation can also be turned into a valid dual bound of the complete master problem. See
    123 * @ref RINGPACKING_PRICER for more details. Also note that the dual bound is invalidated after the first branching step.
    124 * This means that it is not a typical branch-and-price, but rather a <b>price-and-branch</b> framework.
    125 *
    126 * Another issue with the above formulation is the fact that \f$\mathcal{CP}\f$ can be of exponential size, as well. We try
    127 * to overcome this by using a column enumeration algorithm to compute all relevant circular patterns.
    128 * See @ref RINGPACKING_ENUMERATION for details.
    129 */
    130
    131
    132/**@page RINGPACKING_ENUMERATION Enumeration of circular patterns
    133 *
    134 * Here we describe a column enumeration algorithm that is used to deal with the exponential number of circular patterns.
    135 *
    136 * The main step of the algorithm is to verify whether a given tuple \f$(t,P)\in \mathcal{T} \times\mathbb{Z}_{+}^T\f$
    137 * is in the set \f$\mathcal{CP}\f$ or not. A tuple can be checked by solving the following nonlinear nonconvex
    138 * verification problem:
    139 *
    140 * \f[
    141 * \begin{align}
    142 * {\left\|{{\begin{pmatrix}x_i\\y_i\end{pmatrix}} - {\begin{pmatrix}x_j\\y_j\end{pmatrix}}}\right\|}_2 \ge R_i + Rj && \text{ for all } i,j \in C: i < j \\
    143 * {\left\|{{\begin{pmatrix}x_i\\y_i\end{pmatrix}}}\right\|}_2 \le r_t - R_i && \text{ for all } i \in C \\
    144 * x_i, y_i \in \mathbb{R} && \text{ for all } i \in C
    145 * \end{align}
    146 * \f]
    147 *
    148 * Here \f$C\f$ is the index set of individual circles, and \f$R_i\f$ the corresponding external radius of a circle \f$i \in
    149 * C\f$. The model checks whether all circles can be placed in a non-overlapping way into a ring of type \f$t\in\mathcal{T}\f$.
    150 * The first constraints ensure that no two circles overlap, and the second constraints guarantee that all circles are placed
    151 * inside a ring of type \f$t\f$.
    152 *
    153 * Two more steps are taken in order to solve this problem more efficiently. Firstly, symmetry handling constraints are added
    154 * to break the large amount of symmetry the formulation contains. Secondly, a dominance relation betwen circular patterns is
    155 * introduced. In fact, it is easy to see that some patterns are never needed in an optimal solution, e.g. when at least one
    156 * more circle fits. Therefore, some patterns don't have to be verified if certain others have already been (dis)proved to be
    157 * feasible. The algorithm enumerates the circular patterns in a way that minimizes the number of verifications that have to
    158 * be performed. See <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6449">ZIB-Report 17-07</a>
    159 * for more details.
    160 *
    161 * In addition to all this, a simple greedy heuristic is used to verify simple patterns before actually solving the NLP.
    162 */
    163