SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
xternal_queens.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-2025 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_queens.c
26 * @brief using SCIP's callable library for solving the n-queens problem.
27 * @author Cornelius Schwarz
28 */
29
30/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32/**@page QUEENS_MAIN The n-Queens Problem
33 * @author Cornelius Schwarz
34 *
35 * We show how to use SCIP as a backend for solving mixed
36 * integer programs by developing a solver for the \f$n\f$-queens problem. We
37 * first give a brief introduction into the problem and then describe a C++
38 * program for solving it. The model is based on the one described in the
39 * Zimpl documentation.
40 *
41 * The n-queens problem
42 * ====================
43 *
44 * The \f$n\f$-queens problem asks how to place \f$n\f$ queens on an \f$n \times n\f$
45 * chess board in a way that no two queens interfere. In detail this means:
46 *
47 * - In each vertical line of the board only one queen is allowed, we
48 * will refer to these lines as columns.
49 *
50 * - In each horizontal line of the board only one queen is allowed,
51 * these lines will be called rows later on.
52 *
53 * - In each diagonal line only one queen is allowed.
54 *
55 * This can be modeled as a binary program in the following way: Let
56 * \f$x_{i,j} \in \{0,1\}\f$ denote whether a queen is placed on the \f$i\f$th row
57 * and the \f$j\f$th column of the chess board. Since the problem is to find a
58 * placement, the objective function is irrelevant. We add, however, the
59 * redundant objective to maximize the number of placed queens:
60 * \f[
61 * \max \sum_{i=1}^n \sum_{j=1}^n x_{i,j}
62 * \f]
63 * Now we force exactly one
64 * queen to be placed in every column and every row:
65 * \f[
66 * \begin{aligned}
67 * \sum_{i=1}^n x_{i,j} & = & 1, \ j=1,\ldots,n \\
68 * \sum_{j=1}^n x_{i,j} & = & 1, \ i=1,\ldots,n\end{aligned}
69 * \f]
70 * The
71 * diagonal rows are a little bit more complicated to write up:
72 * \f[
73 * \begin{aligned}
74 * \sum_{i=1}^{n-j+1} x_{i,j+i-1} & \leq & 1, \ j = 1, \ldots, n \\
75 * \sum_{j=1}^{n-i+1} x_{i+j-1,j} & \leq & 1, \ i = 1, \ldots, n \\
76 * \sum_{i=1}^{n-j+1} x_{i,n-j-i+2} & \leq & 1, \ j = 1, \ldots, n\\
77 * \sum_{j=1}^{n-i+1} x_{i+j-1,n-j+1} & \leq & 1, \ i = 1, \ldots, n\\\end{aligned}
78 * \f]
79 *
80 * Error handling in SCIP
81 * ======================
82 *
83 * Before we transform the \f$n\f$-queens IP program into a SCIP program, we
84 * first consider a general point when working with SCIP functions: Most
85 * SCIP functions return a value of the type `SCIP_RETCODE`. If this is
86 * equal to `SCIP_OKAY`, then everything went well, otherwise it indicates
87 * an error code. Therefore the normal call of a SCIP function returning a
88 * `SCIP_RETCODE` (we use `SCIPfunction` as a generic name – replace it
89 * with whatever function you are calling) is
90 *
91 * SCIP_RETCODE retcode;
92 * retcode = SCIPfunction();
93 * if (retcode != SCIP_OKAY)
94 * {
95 * // do your error handling here
96 * }
97 *
98 * Since this is a lot of code for every function call, SCIP provides two
99 * macros namely `SCIP_CALL` and `SCIP_CALL_ABORT`. The second one just
100 * aborts the execution by calling `abort()` if an error occured. The first
101 * one calls the SCIP function and, in the error case, returns the retcode.
102 * This results in the following code:
103 *
104 * SCIP_RETCODE myfunction(void)
105 * {
106 * SCIP_CALL(SCIPfunction());
107 * SCIP_CALL(SCIPotherfunction());
108 *
109 * return SCIP_OKAY;
110 * }
111 * int main(int args, char * argv)
112 * {
113 * SCIP_RETCODE retcode = myfunction();
114 * if (retcode != SCIP_OKAY)
115 * {
116 * // do your error handling here
117 * }
118 * }
119 *
120 * While this is nice for C programs, there is a problem when using
121 * `SCIP_CALL` from C++: A C++ constructor is not allowed to return a
122 * value. The same is true for destructors. Therefore we supply a third
123 * method, the `SCIP_CALL_EXC` macro. This behaves just like `SCIP_CALL`,
124 * but instead of returning the error code it throws an exception of a new
125 * type `SCIPException`. So the example above would now be written as:
126 *
127 * int main(int args, char * argv)
128 * {
129 * try
130 * {
131 * SCIP_CALL_EXC(SCIPfunction());
132 * SCIP_CALL_EXC(SCIPotherfunction());
133 * } catch(SCIPException & exec)
134 * {
135 * cerr<<exec.what()<<endl;
136 * exit(exec.getRetcode());
137 * }
138 * }
139 *
140 * Include files
141 * =============
142 *
143 * For a SCIP based project there are three main header files to consider.
144 * The first and most important one is of course scip/scip.h. It declares
145 * the `SCIP` pointer and \ref PUBLICCOREAPI "all public functions".
146 * You may have noticed that
147 * SCIP can be extended by plugins. In fact most parts of the MIP solver
148 * like heuristics, separators, etc. are implemented as plugins. To use
149 * them, include scip/scipdefplugins.h.
150 *
151 * These two header files are C type. In early versions of SCIP it was
152 * necessary to wrap them in an `extern "C"` statement. As of version 1.1
153 * SCIP now detects a C++ compiler and adds `extern "C"` own its own.
154 *
155 * The last header file to consider is objscip/objscip.h if you want to
156 * use the C++ wrapper classes distributed with SCIP. For the queens
157 * example we do not develop own plugins, so we just use
158 *
159 * #include <scip/scip.h>
160 * #include <scip/scipdefplugins.h>
161 *
162 * Developing a queens solver
163 * ==========================
164 *
165 * When you use SCIP you have to do the following steps:
166 *
167 * - initialize the SCIP environment
168 *
169 * - load all desired plugins (including your own, if you like)
170 *
171 * - create a problem
172 *
173 * - add variables and constraints to the problem
174 *
175 * - solve the problem
176 *
177 * - access results
178 *
179 * - free the SCIP environment
180 *
181 * You can, of course, cycle through some of these steps like accessing the
182 * results, modifying the problem and solving again. We will now describe
183 * these steps in more detail for the queens solver.
184 *
185 * ### Initializing the SCIP environment
186 *
187 * In this section, we start developing our queens solver. Before you can
188 * do anything with SCIP, you have to create a valid `SCIP` pointer. For
189 * this purpose use the SCIPcreate() function:
190 *
191 * SCIP* scip;
192 * SCIP_CALL_EXC(SCIPcreate(& scip));
193 *
194 * ### Loading all desired plugins
195 *
196 * After we created our `SCIP` pointer we load the plugins. In SCIP nearly
197 * everything is a plugin: heuristics, separators, constraint handlers,
198 * etc. Whenever you want to use one you first have to include it. This is
199 * done by various `SCIPinclude` functions like SCIPincludeHeur() for
200 * heuristics or SCIPincludeConshdlr() for constraint handlers. This also
201 * activates the default display plugins which writes various messages to
202 * standard output. (If you do not like this you can disable it by a call
203 * of `SCIPmessagehdlrSetQuiet(SCIPgetMessagehdlr(scip), TRUE)`.) All together we get:
204 *
205 * SCIP_CALL_EXC(SCIPincludeDefaultPlugins(scip));
206 * // SCIPmessagehdlrSetQuiet(SCIPgetMessagehdlr(scip), TRUE);
207 * // uncomment the above line to disable output
208 *
209 * ### Creating a problem
210 *
211 * Now we can create the IP model for the queens solver in SCIP. First we
212 * create an empty problem with SCIPcreateProb(). The first argument is our
213 * `SCIP` pointer and the second is the name of the problem. You can also
214 * supply user specific problem data and call back functions to handle
215 * them, but normally you will not need them and can safely set them to
216 * `NULL`:
217 *
218 * SCIP_CALL_EXC(SCIPcreateProb(scip, "queens", NULL, NULL,
219 * NULL, NULL, NULL, NULL, NULL));
220 *
221 * The default objective sense for SCIP problems is minimizing. Since we
222 * have a maximization problem we have to change this:
223 *
224 * SCIP_CALL_EXC(SCIPsetObjsense(scip, SCIP_OBJSENSE_MAXIMIZE));
225 *
226 * ### Creating variables
227 *
228 * Now it is time to fill the empty problem with information. We start by
229 * creating variables, one binary variable for every field on the chess
230 * board. Variables are accessed through the type `SCIP_VAR*`. Associated
231 * with each variable is a type (continuous, integer, or binary), lower and
232 * upper bound and an objective coefficient. In our case, the type is binary for all
233 * variables, the lower bound is naturally 0, the upper bound 1, and the
234 * objective is 1 for all variables:
235 *
236 * SCIP_VAR* var;
237 * SCIP_CALL_EXC(SCIPcreateVar(scip, & var, "x#i#j", 0.0, 1.0, 1.0,
238 * SCIP_VARTYPE_BINARY, TRUE, FALSE,
239 * NULL, NULL, NULL, NULL, NULL));
240 *
241 * Here, you should replace \f$i\f$ and \f$j\f$ by the actual row and column
242 * number of the variable. The fourth argument is the lower bound, the
243 * fifth the upper bound, the sixth the objective, and the seventh the
244 * type. After that you specify two boolean parameters indicating whether
245 * this variable is in the initial (root) LP and whether it is allowed to
246 * be removed during aging. Like in SCIPcreateProb() you can use the last
247 * five parameters to specify user data. We set these parameters to `NULL`.
248 * After creating the `SCIP_VAR` pointer it is time to add it to the SCIP
249 * problem:
250 *
251 * SCIP_CALL_EXC(SCIPaddVar(scip, var));
252 *
253 * You should store the `SCIP_VAR` pointers somewhere, since you will need
254 * them to add the variables to constraints and to access their values in
255 * the final solution and so on. In our example, you can use a two
256 * dimensional STL vector for that purpose.
257 *
258 * ### Creating constraints
259 *
260 * Creating and adding variables is just half of the battle. To ensure
261 * feasibility, we have to add the constraints we described above. To
262 * create a constraint in SCIP you first need to specify a constraint
263 * handler. The constraint handler is responsible for checking feasibility,
264 * tighten variable bounds, adding new rows to the underlying LP problem
265 * and so on. The creating method depends on the actual constraint you want
266 * to use and is usually called `SCIPcreateConsName` – for instance
267 * SCIPcreateConsLinear(). Although there are many different default
268 * constraints like knapsack, logic-OR, etc. (for a complete list, see
269 * \ref CONSHDLRS), it is a safe way to create
270 * them as linear constraints. The presolver will automatically transform
271 * them to the right constraint type. We will therefore add all our
272 * constraints as type linear and describe the handler here.
273 *
274 * The linear constraint handler handles constraint of the following type:
275 * \f[
276 * lhs \leq a^T x \leq rhs
277 * \f]
278 * There are three special cases of these: For
279 * equality constraints set \f$lhs = rhs\f$, for lesser equal constraints, set
280 * \f$lhs = -\f$`SCIPinfinity(scip)` and for greater equal constraints
281 * \f$rhs = \f$ `SCIPinfinity(scip)`. So the creating of the diagonal
282 * constraints looks as follows:
283 *
284 * SCIP_CONS* cons;
285 * SCIP_CALL_EXC(SCIPcreateConsLinear(scip, & cons, "diag",
286 * 0, NULL, NULL, 0, 1.0, TRUE,
287 * TRUE, TRUE, TRUE, TRUE, FALSE,
288 * FALSE, FALSE, FALSE, FALSE));
289 *
290 * The first is, as usual, the `SCIP` pointer and the second the
291 * `SCIP_CONS` pointer, which allows to access the constraint later. After
292 * that you can specify variables to be added to the constraint. This could
293 * be done by specifying the number, an array of `SCIP_VAR` pointers to
294 * variables, and an array of values of the coefficients, stored as
295 * doubles. We skip the adding at this point and use the function
296 * SCIPaddCoefLinear() described later on. The next two entries are \f$lhs\f$
297 * and \f$rhs\f$. In our cases 0 and 1. Then you specify the following
298 * parameters:
299 *
300 * | parameter | description |
301 * |----------------|---------------------------------------------------------------------|
302 * | initial | set this to `TRUE` if you want the constraint to occur in the root problem |
303 * | separate | set this to `TRUE` if you would like the handler to separate, e.g. generate cuts |
304 * | enforce | set this to `TRUE` if you would like the handler to enforce solutions. This means that when the handler declares an LP or pseudo solution as infeasible, it can resolve infeasibility by adding cuts, reducing the domain of a variable, performing a branching, etc. |
305 * | check | set this to `TRUE` if the constraint handler should check solutions |
306 * | propagate | set this to `TRUE` if you want to propagate solutions, this means tighten variables domains based on constraint information |
307 * | local | set this to `TRUE` if the constraint is only locally valid, e.g., generated in a branch and bound node |
308 * | modifiable | set this to `TRUE` if the constraint may be modified during solution process, e.g. new variables may be added (colum generation) |
309 * | dynamic | set this to `TRUE` if this constraint is subject to aging, this means it will be removed after being inactive for a while (you should also say `TRUE` to removable in that case) removable set this to `TRUE` to allow the deletion of the relaxation of the constraint from the LP |
310 * | stickingatnode | set this to `TRUE` if you want the constraint to be kept at the node it was added |
311 *
312 * Variables which are not added at the creation time of the constraint can
313 * be added by calling:
314 *
315 * SCIP_CALL_EXC(SCIPaddCoefLinear(scip, cons, var, 1.0));
316 *
317 * Here “1.0” is the matrix coefficient.
318 *
319 * ### Solving the problem
320 *
321 * When the problem is setup completely we can solve it. This is done by
322 *
323 * SCIP_CALL_EXC(SCIPsolve(scip));
324 *
325 * SCIP then starts transforming and preprocessing the problem. After that
326 * it enters the solving stage where the root LP is solved, heuristics are
327 * run, cuts are generated, and the branching process starts. All plugins
328 * you wrote (heuristics, separators, etc.) will be called by SCIP through
329 * callback functions at this stage.
330 *
331 * ### Accessing results
332 *
333 * Now that the problem is solved, we want to know the solution data.
334 * Whether the problem has been solved to optimality, only feasible
335 * solutions were found, and so on, can be queried by SCIPgetStatus(). We
336 * ignore this in our queens solver and start with the best solution found
337 * so far. This can be accessed by
338 *
339 * SCIP_SOL* sol = SCIPgetBestSol(scip);
340 *
341 * If SCIP did not find a solution `sol` is equal to `0`. Otherwise, you
342 * can get the objective value by SCIPgetSolOrigObj(). In the queens
343 * example we want to know whether a queen is placed on a field or not.
344 * Therefore we need the value of the variable \f$x_{i,j}\f$ which can be
345 * accessed by SCIPgetSolVal(). In the case of an integer or binary
346 * variable, care must be taken, because this functions returns double
347 * values. So if we want to query a binary variable we use the following:
348 *
349 * if (sol == NULL)
350 * {
351 * // output error message here and abort
352 * }
353 * if ( SCIPgetSolVal(scip, sol, var) > 0.5 )
354 * {
355 * // value is one
356 * }
357 * else
358 * {
359 * // value is zero
360 * }
361 *
362 * In this example, we of course use the knowledge that variables have 0/1
363 * values only. There are special SCIP functions for performing numerical
364 * comparisons between values that are not known to be integer. For
365 * instance, you can use `SCIPisFeasEQ(scip, x, y)` for comparing whether
366 * \f$x\f$ is equal to \f$y\f$ within the feasibility tolerance of SCIP. This macro
367 * return `TRUE` if \f$|x - y| < \epsilon\f$, where \f$\epsilon\f$ is the feasibility
368 * tolerance of SCIP (by default \f$\epsilon = 10^{-6}\f$).
369 *
370 * ### Freeing the SCIP environment
371 *
372 * Finally, we must free all the memory SCIP used. When we created the
373 * variables and constraints, the SCIPcreateVar() and SCIPcreateCons()
374 * captured the corresponding variables and constraints. This means that
375 * SCIP knows that we have a pointer to these and will only free the memory
376 * if we tell it that we do not need these pointers anymore. This is done
377 * by the `SCIPrelease` functions. So before we can free the `SCIP`
378 * pointer, we have to call:
379 *
380 * SCIP_CALL_EXC(SCIPreleaseVar(scip, & var));
381 * SCIP_CALL_EXC(SCIPreleaseCons(scip, & cons));
382 *
383 * Then we close the SCIP environment:
384 *
385 * SCIP_CALL_EXC(SCIPfree(& scip));
386 *
387 * Installation
388 * ============
389 *
390 * See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
391 */