SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
|
xternal.c
Go to the documentation of this file.
22 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 28 * This example contains a branch-and-price approach for the binpacking problem which is realized with the framework 31 * - a problem reader which parses the problem out of file and creates the corresponding problem within \SCIP 33 * - a (global) problem data structure which contains all necessary information (probdata_binpacking.c) 36 * - a constraint handler which handles the branching decisions of the Ryan/Foster branching (cons_samediff.c) 37 * - a variable data structure which stores information for each variable and is needed to perform the Ryan/Foster 40 * In the following we introduce the problem, explain the use of the reader plugin and pricer plugin. Finally, we 41 * introduce the Ryan/Foster branching rule and briefly discuss how that specific branching rule can be realized within 55 * The binpacking problem consists of the task to distribute a given set of items \f$ [n] := \{1, \dots, n\}\f$ with 56 * nonnegative size \f$s_i\f$ to a minimal number of bins, all of the same capacity \f$\kappa\f$. As example consider 9 57 * items with sizes: 2, 1, 2, 1, 1, 2, 3, 2, and 1 and a bin capacity of \f$\kappa\f$ of 4. The following pictures show 58 * a feasible solution which needs 5 bins. The minimum number of bins needed for that example is 3. 64 * This problem can be formulated as a set covering problem as discussed by Gilmore and Gomory in the following two classical papers: 65 * - Gilmore P. C., R. E. Gomory: A linear programming approach to the cutting-stock problem. Operations Research 9 (1961): 849-859. 66 * - Gilmore P. C., R. E. Gomory: A linear programming approach to the cutting-stock problem - Part II. Operations Research 11 (1963): 863-888 68 * We introduce a binary variable \f$x_{S}\f$ for each feasible packing \f$S\f$. A <b>packing</b> \f$S\f$ is an 69 * assignment vector \f$ \lambda_{S}\in\{0,1\}^n \f$ which states the items belonging to that packing. It is 70 * <b>feasible</b>, if and only if the total size of the items contained in this assignment is not greater than the 71 * given capacity \f$\kappa\f$. Let \f$\mathcal{S}\f$ be the set of all feasible packing, this measns: 83 * subject \ to & \displaystyle \sum_{S \in \mathcal{S}} (\lambda_{S})_{i}x_{S} \ge 1 & \quad \forall i \in \{1,\dots,n\} \\ 89 * This means we are searching for a set of packings such that each item is contained in at least one of the selected 90 * packings. Since the objective is to minimize the number of used packings, each optimal solution to the above problem 94 * Since \f$\mathcal{S}\f$ can be of exponential size, we are using a column generation approach to solve this 95 * problem. We initialize the (master) problem with a set of \f$ n \f$ variables representing packings of a single item 96 * per bin. Now, we have to iteratively search for variables representing "better" packings, i.e., a packing pattern 97 * which reduces the overall cost. For a given solution \f$y^\star\f$ of the (restricted) dual linear program, we have 98 * to find a variable/packing \f$ \lambda_{S} \f$ for which the reduced costs is negative. This means: 104 * Since all variables \f$ \lambda_{S} \f$ have an objective coefficient \f$ c_{S} = 1 \f$ the above condition is 124 * where \f$ (\lambda_S)_i \f$ for \f$i\in\{1,\dots,n\}\f$ are binary variables and \f$y^\star_i\f$ given by the dual 127 * The above problem is a knapsack problem which can be solved via dynamic programming or by solving the above integer 136 * The Makefile is based on the main \SCIP Makefile. This means that all compiling options which are |