xternal.c
Go to the documentation of this file.
41/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
47 * \SCIP is a framework to solve constraint integer programs (CIPs) and mixed-integer nonlinear programs. In particular,
53 * Since version 10, \SCIP can optionally be configured to solve mixed-integer linear programs in a numerically exact
54 * solving mode and produce certificates that can be independently verified, see \ref EXACT "How to use the numerically exact solving mode" for details.
56 * See the web site of <a href="http://scipopt.org">\SCIP</a> for more information about licensing and how to download \SCIP.
58 * <b style="color: blue">If you are new to SCIP and don't know where to start you should have a look at the
64 * This manual gives an accessible introduction to the functionality of the SCIP code in the following chapters
96 * Let's consider the following minimal example in LP format. A 4-variable problem with a single, general integer
101 * Saving this file as "simple.lp" allows to read it into SCIP and solve it by calling the scip binary with the `-f` flag to solve the problem from the provided file and exit.
115/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
135/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
148/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
152 * SCIP implements the NLP solver interface for the solvers <a href="https://conopt.com">CONOPT</a>, <a href="https://github.com/coin-or/Ipopt">IPOPT</a>, <a
153 * href="https://worhp.de/">WORHP</a>, and <a href="http://www.mcs.anl.gov/~leyffer/solvers.html">FilterSQP</a>. In
154 * contrast to the implementations of the LP solver interface, SCIP can be compiled with multiple NLP solvers and selects
156 * Currently, the priorities are, in descending order: CONOPT, Ipopt, WORHP/IP, FilterSQP, WORHP/SQP.
158 * If more than one solver is available, then it is possible to solve all NLPs during the solving process with all
160 * In this case, SCIP uses the solution from a solver that provides the best objective value. Other possible use
163 * In the @ref MAKE "GNU make" based build system, building the implementations of the interface for CONOPT, FilterSQP, IPOPT, and
164 * WORHP can be enabled by specifying `CONOPT=true`, `FILTERSQP=true`, `IPOPT=true`, and `WORHP=true`, respectively, as argument to the
166 * In the @ref CMAKE "CMAKE" based build system, building the implementation of the interface for CONOPT, IPOPT and WORHP can be
167 * enabled by specifying `CONOPT=on`, `IPOPT=on` and `WORHP=on`, respectively, as argument to the `cmake` call.
171 * <b>CONOPT</b> is a feasible path solver based on advanced active set methods. Originally developed by ARKI Consulting
172 * & Development A/S in Denmark, CONOPT was acquired by GAMS in 2024. It is free for academic uses and is available at
177 * <b>IPOPT</b> implements a primal-dual interior point method and uses line searches based on filter methods. It has
178 * been developed by Andreas Wächter and Carl Laird and is available under the Eclipse Public License on <a
183 * <b>WORHP</b> implements a sequential quadratic programming method and a penalty-interior point algorithm. It is
184 * developed at the <a href="https://www.uni-bremen.de/en/">University of Bremen</a> and is free for academic
189 * <b>FilterSQP</b> implements a sequential quadratic programming method. It has been developed by Roger Fletcher
190 * and Sven Leyffer. It is not publicly available, but may be obtained from Sven Leyffer on request.
193/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
201 * Charlotte lectures at a university and she wants her students to get in touch with solving constraint integer programs (CIPs).
202 * She would like to use SCIP for this purpose because it allows the students to look at the full source code
214 * She works on a recent computer with a windows system and already has the <a href="https://support.microsoft.com/en-us/help/2977003/the-latest-supported-visual-c-downloads">Visual C++ Redistributable Packages</a> and <a href="https://github.com/oneapi-src/oneTBB">TBB</a> installed.
216 * Having these prerequisites in place, Charlotte downloads the 64-bit windows exectuable from the <a href="https://scipopt.org/index.php#download">download page</a> and installs it without a problem.
217 * They also read about the <a href="http://www.pokutta.com/blog/pages/scip/scip-teaching.html"> dockerized SCIP container</a> which she wants
222 * To test her installation and get a first feeling for SCIP, Charlotte follows the steps described in the \ref QUICKSTART "quickstart" section to solve a first simple lp problem.
224 * She has just solved a problem, using SCIP in the command-based mode, by passing a command to the scip call via the `-c` flag.
225 * These commands can also be typed into the interactive shell, that one uses by just calling the binary `scip`.
227 * After the first solution process worked like a charm, Charlotte downloads a more complicated problem file from the <a href="https://miplib.zib.de/instance_details_enlight_hard.html">MIPLIB 2017</a> page
229 * There, she already learns quite a lot about the solving process and how to work with the interactive shell.
233 * Feeling happy about having already solved some instances and having worked in interactive mode, Charlotte is curious on what more options SCIP has.
236 * She feels confident to being able to understand and use some of the other options, like `-l` to write the output to a logfile, or `-b` to pass a file containing the commands to be executed by scip.
237 * There are some commands that do not yet make a lot of sense to her, but she doesn't worry about it for now.
242 * Alex is a researcher in Charlotte's group and is working on problems that have a very special structure that he hopes to be able to exploit in the solving process.
245 * She explained that SCIP is plugin-based, that is, different components (plugins) are implemented using a generic interface and that it is very easy to write your own plugins, like constraint handlers, heuristics etc.
250 * After some time of using SCIP, he feels confident enough to dig into the source code and decides to write his own plugin.
251 * Alex likes to use his linux machine for developing code, because in his experience compilation is easiest there.
253 * He starts by downloading the latest <a href="http://scipopt.org/#download">source code tarball</a>,
254 * unpacking it and compiling via \ref CMAKE "cmake", typing `mkdir build; cd build; cmake ..; make`.
258 * Before writing any code, he quickly scans over the contents of the \ref PROGRAMMING "Programming with SCIP" page,
260 * If a problem comes up later or he gets stuck, he knows what to look out for and where to find help.
262 * Whenever Alex gets stuck inside the code, he makes use of the extensive documentation to \ref DOC "search for interface functions".
266 * Alex is now ready to write his very first example, he creates a new folder `MinEx` under `examples` and puts two files in there:
307 * After having successfully written this minimal example, Alex follows the instructions to \ref START "start a new project" to start his actual project and extend this most basic code.
311 * Alex now needs a custom constraint handler in his project, for that he will write a custom plugin.
323 * After implementing his own constraint handler Alex realizes that he needs to use repotimization in his project.
324 * He looks up the \ref HOWTOUSESECTION "How to use..." section and finds some more information about \ref REOPT "how to use reoptimization".
334 * If you just want to use SCIP as a black box solver you should use an installer with a precompiled binary from the <a href="http://scipopt.org/#download">download section</a>.
336 * If you are just curious and want to try it out you can use the <a href="http://www.pokutta.com/blog/pages/scip/scip-teaching.html"> dockerized SCIP container</a>.
338 * However, if you want to develop your own plugin for SCIP, you have to compile SCIP or the SCIPOptSuite from source code, which are available as a tarball from the <a href="http://scipopt.org/#download">download page</a>.
339 * Note that you might need some level of experience to be able to do this, this is described in the following.
345 * Be aware that generated libraries and binaries of both systems might be different and incompatible.
366 * Below you find for most plugin types a detailed description of how to implement and add them to \SCIP.
420 * <a class="el" href="https://www.cgudapati.com/integer-programming/2019/12/15/Getting-Started-With-SCIP-Optimization-Suite.html">Getting Started with SCIP optimization in C++: A toy example</a> by Chaitanya Gudapati.
426 * New features, peformance improvements, and interface changes between different versions of SCIP are documented in the
452 * As a stand-alone solver, \SCIP can solve mixed-integer nonlinear programs \b (MINLPs), to which it applies
453 * an LP based spatial branch-and-cut algorithm. This method is guaranteed to solve bounded MINLPs
454 * within a given numerical tolerance in a finite amount of time. In particular, \SCIP is a stand-alone
457 * As a framework, \SCIP also provides the tools to solve constraint optimization problems defined over
460 * More precisely, \SCIP can handle the class of constraint integer programs \b (CIPs), which are constraint optimization problems
465 * The following table gives a non-exhaustive list of common types of mathematical optimization problems that can be solved
466 * through \SCIP itself or one of its extensions. Some recommendations are given on how to compile \SCIP for a
467 * certain problem class and how make best use of \SCIP. The file format column gives some common file
468 * formats for every class. Note that since some of the mentioned problem classes are more general than others (like
469 * every LP is a MIP is an MINLP), the formats for the superclass should always work just as fine, although they
472 * Please see also the pages on \ref EXAMPLES "SCIP Examples" and \ref APPLICATIONS "SCIP Applications" to learn more on how
474 * All examples and applications use the C or C++ APIs of \SCIP. Please have a look at \ref INTERFACES "SCIP interfaces"
507 * <li>Compile with Zimpl support (<code>ZIMPL=true</code>) to read in Zimpl models directly.</li>
508 * <li>\SCIP comes with many different parameters. Use the provided emphasis settings (see \ref SHELL "this tutorial")
544 * <li>See <a href="FAQ\FILEEXT#minlptypes"> Which kind of MINLPs are supported by \SCIP? </a> in the FAQ.</li>
546 * <li>Mixed-integer quadratically constrained programs (MIQCP) can also be formulated in the file formats
563 * where \f$\forall i \in\mathcal{M}, \forall x^* \in \mathbb{Z}^{p},\f$ \f$ \{ y : C_i(x^*, y) = \text{true} \} \f$ is a polyhedron.
573 * <li>\SCIP supports a limited number of general constraints; see \ref CONS "How to add constraint handlers"
575 * <li>Use the emphasis setting <code>set emphasis cpsolver</code> to completely disable LP solves and
577 * <a href="FAQ\FILEEXT#scipascpsolver"> Can I use \SCIP as a pure CP solver? </a> in the FAQ.</li>
588 * <li>In addition, use <code>constraints/nonlinear/assumeconvex = TRUE</code> to inform \SCIP about a convex
603 * <td>See <a href="FAQ\FILEEXT#scipaslpsolver">Can I use \SCIP as a pure LP solver</a> in the FAQ.</td>
609 * \text{s.t.} \quad& \sum_{k=0}^p a_{ik} \cdot \prod_{j \in \mathcal{N}_{ik}} x_j \leq b_i && \forall i \in \mathcal{M} \\
629 * \text{s.t.} \quad&\bigvee\limits_{j \in B_i} x_j \vee \bigvee\limits_{j \in \bar{B}_i} \neg x_j = \text{true} && \forall i \in \mathcal{M}\\
640 * <li>Use the emphasis setting <code>set emphasis cpsolver</code> to completely disable LP solves and
642 * <a href="FAQ\FILEEXT#scipascpsolver"> Can I use \SCIP as a pure CP/SAT solver? </a> in the FAQ.</li>
666 * <td colspan="3"> see the <a href="http://www.opt.tu-darmstadt.de/scipsdp/">SCIP-SDP web page</a></td>
673/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
687 * - Spaces around the arguments inside an if/for/while-statement, as well as inside macros (e.g., SCIP_CALL).
688 * - No spaces between control structure keywords like "if", "for", "while", "switch" and the corresponding brackets.
689 * - No spaces between a function name and the parenthesis in both the definition and function calls.
695 * - In function declarations, every parameter is on a new line. The name of the parameter starts at column 26,
699 * - Joint declaration and initialization is possible at the top-level of a function and in the header of loops.
708 * - Multiple blank lines are used to structure the code where single blank lines are insufficient,
721 * - All global functions start with "SCIP". In the usual naming scheme this is followed by the object and a function name
737 * - When documenting functions, the first brief description starts with lower case and is separated by semi-colons, if necessary
746 * If you are using (x)emacs, you can use the following customization for the c++-mode. These settings satisfy the
754 * Eclipse user can use the profile below. This profile does not match the \SCIP coding guideline completely.
759/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
767 * Instructions on how to write a new plugin and include it in \SCIP can be found in the corresponding
770 * \SCIP can also be used for writing your own branch-and-cut or branch-and-cut-and-price code. \SCIP already
771 * provides a number of existing code examples which we suggest as both reference and starting point
777 * The example should be chosen depending on the programming language (<b>C</b> or <b>C++</b>) and the purpose
781 * - The \ref VRP_MAIN "Vehicle Routing Problem Example" is a <b>branch-and-cut-and-price</b> (column generation)-code
798 * from the \SCIP root directory for copying the content of the <code>Binpacking</code>-example into a fresh
799 * directory named SCIPProject in the parent directory of the \SCIP root directory and jumping to
804 * It is recommended for all new users to use the CMake build system configuration, if available on their platform.
806 * - Open the <code>CMakeLists</code> (some examples projects have a subdirectory "check" for testing) via
810 * and replace all instances of the copied project's name (e.g. <code>binpacking</code>) with your project name.
811 * - Create a new subdirectory, jump to the new directory and use cmake specifying your \SCIP directory. For instance, type
815 * and compile using the <code>make</code> command. For the CMake equivalents of all the flags that can be used in \SCIP, see \ref CMAKE.
820 * If CMake should be unavailable on your targeted platform, try the classic Makefile system of SCIP.
839 * \SCIP contains several examples that demonstrate its usage. They are contained in the "examples" directory
855 * An example showing how to setup constraints (esp. nonlinear ones) when using \SCIP as callable library.
933 * A short implementations of a constraint handler, two easy combinatorial heuristics, a file reader, etc. which
934 * demonstrate the usage of \SCIP as a branch-and-cut-framework for solving traveling salesman problem instances.
949 * An implementation of the column generation approach for the binpacking problem. It includes a customized reader,
958 * A solver for a simple capacity-constrained vehicle routing problem, which is based on pricing tours via a dynamic
974 * A stochastic programming problem that demonstrates the use of the Benders' decomposition framework within SCIP.
982 * There are several extensions of \SCIP for particular applications included in the release. They are contained in the "applications" directory
1015 * A solver for pseudoboolean problems in OPB or WBO format. It complies by default with the technical regulations of
1016 * PB competition. Therefore, it includes a message handler to produce a valid general log and for optimization
1025 * An implementation of the column generation approach for the Ringpacking Problem. It includes a customized reader,
1044 * If you are using \SCIP as a black box solver, here you will find some tips and tricks what you can do.
1053 * Therefore, you can either download the \SCIP standard distribution (which includes problem files) and compile it on your own or you can download a
1054 * precompiled binary and an example problem separately. \SCIP can read files in LP, MPS, ZPL, WBO, FZN, PIP, OSiL, and
1057 * If you want to download the source code of the \SCIP standard distribution, we recommend to go to the <a
1059 * inflate the tarball (e.g., with "tar xzf scipoptsuite-[version].tgz"), and follow the instructions
1060 * in the INSTALL file. The instance stein27, which will serve as an example in this tutorial, can be found under
1062 * Alternatively you can download an instance file from the <a href="https://miplib.zib.de/tag_benchmark.html">MIPLIB 2017 page</a>.
1064 * If you want to download a precompiled binary, go to the <a href="http://scipopt.org/#download">SCIP download
1065 * section</a> and download an appropriate binary for your operating system. The \SCIP source code distribution already comes with
1066 * the example instance used throughout this tutorial. To follow this tutorial with a precompiled binary, we recommend downloading the instance
1072 * Now start your binary, without any arguments. This opens the interactive shell, which should look somehow like this:
1076 * First of all "help" shows you a list of all available shell commands. Brackets indicate a submenu with further options.
1080 * Okay, let's solve the example instance... use "read check/instances/MIP/stein27.fzn" (or the problem file of your choice) to parse the instance file, "optimize" to solve it and "display
1085 * What do we see here? After "optimize", SCIP first goes into presolving. Not much is happening for this instance, just
1086 * the linear constraints get upgraded to more specific types. Each round of presolving will be displayed in a single
1087 * line, with a short summary at the end. Then, we see the actual solving process. The table output of the branch-and-cut
1088 * solving process is very detailed during the root node. Afterwards, a new line is displayed every 100th node.
1089 * Furthermore, every new incumbent solution triggers a new table row, starting with a character to indicate the
1090 * heuristic that found the solution. Which letter represents which heuristic can be seen with the
1093 * After some lines the root node processing is finished. From now on, we will see an output line every hundredth node or
1095 * moving, too. At one point, both will be the same, and the solving process terminates, showing us some wrap-up
1098 * The exact performance may of course vary among different architectures and operating systems. Do not be worried if
1099 * your installation needs more or less time or nodes to solve. Also, this instance has more than 2000 different optimal
1100 * solutions. The optimal objective value always has to be 18, but the solution vector may differ. If you are interested
1101 * in this behavior, which is called "performance variability", you may have a look at the MIPLIB2010 paper.
1105 * \SCIP can also write information to files. E.g., we could store the incumbent solution to a file, or output the
1106 * problem instance in another file format (the LP format is much more human readable than the MPS format, for example).
1107 * Since stein27.fzn has many constraints with the same name, which would result in an unusable LP file, we write out
1108 * the problem with generic variable and constraint names (x1, x2, x3, ...; c1, c2, c3, ...) here.
1112 * Passing starting solutions can increase the solving performance so that \SCIP does not need to construct an initial feasible solution
1113 * by itself. After reading the problem instance, use the "read" command again, this time with a file containing solution information.
1114 * Solutions can be specified in a raw or xml-format and must have the file extension ".sol", see the documentation of the
1117 * Customized settings are not written or read with the "write" and "read" commands, but with the three commands
1125 * We might want to have some more information now. Which of the heuristics found solutions? Which plugins
1127 * Information on certain plugin types (e.g., heuristics, branching rules, separators) is displayed via
1128 * "display <plugin-type>", information on the solution process via "display statistics", and "display problem"
1134 * thus, we just explain a few lines here. Information is grouped by the plugin type. For the primal heuristics,
1135 * the execution time in seconds is shown as well as the number of calls to the heuristic, and its success regarding
1136 * the number of (best) solutions found by that heuristic. Appropriate statistics are also shown for presolvers, constraint handlers,
1137 * separators, propagators, the search tree, etc. User-written plugins will appear automatically in these statistics,
1142 * Now, we can start playing around with parameters. The primal heuristics Rounding and shifting seem to be quite successful on this instance,
1143 * wondering what happens if we disable them? Or what happens, if we are even more rigorous and disable all heuristics?
1148 * We can navigate through the menus step-by-step and get a list of available options and submenus. Therefore, we select
1149 * "set" to change settings, "heuristics" to change settings of primal heuristics, and "shifting" for that particular
1150 * heuristic. Then we see a list of parameters (and yet another submenu for advanced parameters), and disable this
1151 * heuristic by setting its calling frequency to -1. If we already know the path to a certain setting, we can directly
1152 * type it (as for the rounding heuristic in the above example). Note that we do not have to use the full names, but we
1155 * To solve a problem a second time, we have to read it in again before starting the optimization process.
1159 * Okay, what happened here? First, we reset all parameters to their default values, using "set default". Next, we
1160 * loaded some meta-parameter settings (also see <a href="FAQ.php#howtochangebehaviour">the FAQ</a>), to apply primal heuristics
1161 * more aggressively. \SCIP shows us, which single parameters it changed therefore. Additionally, for pedagogical purposes,
1162 * we set the node limit to 200. Now, the optimal solution is already found at the root node, by a heuristic which is
1163 * deactivated by default. Then, after node 200, the user defined node limit is reached which interrupts the solving
1164 * process, We see that now in the short status report, primal and dual bound are different, thus, the problem is not solved
1165 * yet. Nevertheless, we could access statistics, see the current incumbent solution, change parameters and so on.
1166 * Entering "optimize" we continue the solving process from the point on at which it has been interrupted.
1168 * Once you found a non-default parameter setting that you wish to save and use in the future, use either the command
1176 * in order to save only the nondefault parameters. The latter has several advantages, you can, e.g., combine parameter
1177 * settings from multiple settings files stored by the latter command, as long as they only affect mutually exclusive
1184 * Special attention should be drawn to the reserved settings file name "scip.set"; whenever the \SCIP interactive shell
1185 * is started from a working directory that contains a settings file with the name "scip.set", it will be automatically
1188 * For using special settings for automated tests as described in \ref TEST, save your custom settings in a subdirectory
1192 * We hope this tutorial gave you an overview of what is possible using the \SCIP interactive shell. Please also read our
1197/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
1199/**@page DOC How to search the documentation and source files structure for public interface functions
1201 * If you are looking for a function in order to perform a specific task, the public \ref PUBLICAPI "SCIP C-API" is the place to look.
1202 * - It contains interface functions for all SCIP structs, both in the solver core or in one of the plugins.
1203 * - Plugins are mostly independent from each other, so to use them it is usually enough to browse the \ref PUBLICCOREAPI "Core API".
1204 * - If you want to add your own plugins, see the \ref HOWTOADD pages for exhaustive information for each plugin type.
1205 * - If you are learning SCIP with a concrete project in mind, looking at the available \ref EXAMPLES page may help you
1209 * Header file names of SCIP obey a consistent naming scheme: Type definitions and related objects such as enums are found in headers starting with "type_",
1210 * such as \ref type_var.h , which contains enums and type definitions related to \ref PublicVariableMethods "SCIP problem variables".
1211 * Definitions of the actual structs can be found in separate header files starting with "struct_".
1212 * All function definitions of the public SCIP API are split across header files starting with "pub_" such as \ref pub_cons.h
1214 * The latter headers starting with "scip_" contain more complex functions, which always receive a scip pointer as first argument.
1215 * Those functions may affect several individual components controlled by SCIP. Such a function is SCIPbranchVar(), which
1216 * affects the search tree, which is controlled by SCIP itself and not meant to be accessed by user plugins.
1221 * If, for example, you are looking for information on how to create a problem instance, here are some steps you can take:
1223 * 1. Browse the SCIP Core API and follow the path \ref PUBLICAPI > \ref PUBLICCOREAPI > \ref PublicProblemMethods > \ref GlobalProblemMethods > SCIPcreateProb()
1224 * 2. Here you can find information on the function's return value, preconditions, postconditions, parameters, as well as related functions.
1225 * 3. If you are unsure of how to use some of the parameters, it is worth looking for a basic version of the function.
1226 * This and other related functions may be found by either browsing neighboring functions and groups in the navigation tree to the left, or in the
1227 * 'References' and 'Referenced by' section of the function documentation. In this case, you can find `SCIPcreateProbBasic()`.
1232 * 2. In addition, you can find related functions by browsing the neighboring functions of the same group.
1234 * variables with fractional LP solution value, which are good candidates for classical branching on variables.
1236 * Note that the \ref INTERNALAPI "private SCIP API" contains more complex functions and data structures that fill specialized roles and
1238 * Those functions are **not** exported to the library and are therefore **not available in user projects** using the \ref PUBLICAPI "public SCIP API".
1241/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
1245 * A constraint handler defines the semantics and the algorithms to process constraints of a certain class. A single
1246 * constraint handler is responsible for all constraints belonging to its constraint class. For example, there is
1247 * one \ref cons_knapsack.h "knapsack constraint handler" that ensures solutions are only accepted if they satisfy all
1248 * knapsack constraints in the model. \n A complete list of all constraint handlers contained in this release can be
1252 * For an example, look into the subtour constraint handler (examples/TSP/src/ConshdlrSubtour.cpp) of the
1256 * It is very easy to transfer the C explanation to C++; whenever a function should be implemented using the
1257 * SCIP_DECL_CONS... notion, reimplement the corresponding virtual member method of the abstract scip::ObjConshdlr
1264 * -# Copy the template files src/scip/cons_xyz.c and src/scip/cons_xyz.h into files "cons_subtour.c"
1267 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
1268 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
1269 * -# Use `SCIPincludeConshdlrSubtour()` in order to include the constraint handler into your SCIP instance,
1271 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
1274 * -# Define the \ref CONS_DATA "constraint data and the constraint handler data". This is optional.
1283 * These are given as compiler defines. Some of them are optional, as, e.g., separation-related properties,
1285 * In the C++ wrapper class, you have to provide the constraint handler properties by calling the constructor
1286 * of the abstract base class scip::ObjConshdlr from within your constructor (see the TSP example).
1293 * Additionally, if you are searching for a constraint handler with SCIPfindConshdlr(), this name is looked up.
1297 * This string is printed as a description of the constraint handler in the interactive shell of SCIP.
1300 * Like the separation priority, the enforcement priorities define the order in which the different constraint handlers
1302 * The constraint enforcement is called after the price-and-cut loop is executed (in the case that the LP is solved
1306 * That means, if a constraint handler has negative enforcement priority, it only has to deal with integral solutions
1307 * in its enforcement functions, because for fractional solutions, the integrality constraint handler would have
1309 * If you want to implement a constraint-depending branching rule (for example, SOS branching on special ordered
1310 * set constraints), you have to assign a positive enforcement priority to your constraint handler.
1315 * \par CONSHDLR_CHECKPRIORITY: the priority of the constraint handler for checking feasibility.
1316 * Like the separation priority, the checking priorities define the order in which the different constraint handlers
1319 * That means, constraint handlers with negative checking priorities only have to deal with integral solutions.
1321 * \par CONSHDLR_EAGERFREQ: the default frequency for using all instead of only the useful constraints in separation, propagation and enforcement.
1322 * If \em constraint \em aging is activated, some constraints that were not useful in the past for propagation or
1324 * Usually, the obsolete constraints are not presented to the separation and propagation functions of the constraint
1326 * However, every n'th call, with n being the EAGERFREQ of the constraint handler, all constraints are presented to the
1330 * If the eager evaluation frequency is set to -1, obsolete constraints are never presented to the separation and
1332 * A frequency of 0 means, that obsolete constraints are only used in the first call of each function.
1334 * \par CONSHDLR_NEEDSCONS: indicates whether the constraint handler should be skipped, if no constraints are available.
1335 * Usually, a constraint handler is only executed if there are constraints of its corresponding class in the model.
1337 * However, some constraint handlers must be called without having a constraint of the class in the model, because
1339 * For example, the integrality constraint handler has the NEEDSCONS flag set to FALSE, because there is no explicit
1341 * The integrality conditions are attached to the variables, and the integrality constraint handler has to check
1346 * The following properties are optional and only need to be defined if the constraint handlers support
1349 * \par LINCONSUPGD_PRIORITY: priority of the constraint handler for upgrading of linear constraints
1350 * This property is only needed if a certain linear constraint can be upgraded to a more specific one. In one of
1351 * the first presolving rounds SCIP tries to upgrade linear constraints to more specialized constraints, such as
1354 * \par NONLINCONSUPGD_PRIORITY: priority of the constraint handler for upgrading of nonlinear constraints
1355 * This property has the same effect as the LINCONSUPGD_PRIORITY parameter, see above, and should be set whenever
1356 * an upgrade functionality from a general nonlinear constraint to the more specific one is defined.
1359 * The separation frequency defines the depth levels at which the constraint handler's separation functions \ref CONSSEPALP
1361 * For example, a separation frequency of 7 means, that the separation callback is executed for subproblems that are
1363 * A separation frequency of 0 means, that the separation function is only called at the root node.
1368 * If you want to have a more flexible control of when to execute the separation algorithm, you have to assign
1369 * a separation frequency of 1 and implement a check at the beginning of your separation algorithm whether you really
1373 * \par CONSHDLR_SEPAPRIORITY: the priority of the constraint handler for separation. (optional: to be set only if the constraint handler supports separation)
1374 * In each separation round during the price-and-cut loop of the subproblem processing or during the separation loop
1375 * of the primal solution separation, the separators and separation functions of the constraint handlers are called in
1376 * a predefined order, which is given by the priorities of the separators and the separation priorities of the
1378 * First, the separators with non-negative priority are called in the order of decreasing priority.
1379 * Next, the separation functions of the different constraint handlers are called in the order of decreasing separation
1381 * Finally, the separators with negative priority are called in the order of decreasing priority.
1383 * The separation priority of the constraint handler should be set according to the complexity of the cut separation
1385 * Constraint handlers that provide fast algorithms that usually have a high impact (i.e., cut off a large portion of
1389 * \par CONSHDLR_DELAYSEPA: the default for whether the separation function should be delayed, if other separators found cuts.
1390 * If the constraint handler's separation function is marked to be delayed, it is only executed after no other separator
1392 * If the separation function of the constraint handler is very expensive, you may want to mark it to be delayed until all
1396 * This default frequency has the same meaning as the CONSHDLR_SEPAFREQ with respect to the domain propagation
1398 * A propagation frequency of 0 means that propagation is only applied in preprocessing and at the root node.
1401 * \par CONSHDLR_DELAYPROP: the default for whether the propagation function should be delayed, if other propagators found reductions.
1402 * This property is analogous to the DELAYSEPA flag, but deals with the propagation function of the constraint handler.
1406 * This property indicates at which places the propagation routine of the constraint handler is called.
1407 * Possible values are defined in type_timing.h and can be concatenated, e.g., as in SCIP_PROPTIMING_ALWAYS.
1409 * \par CONSHDLR_PRESOLTIMING: the timing of the constraint handler's presolving function (FAST, MEDIUM, or EXHAUSTIVE).
1410 * Every presolving round starts with the FAST presolving timing. MEDIUM presolving functions are only called, if FAST presolvers did not find
1411 * enough reductions in this round so far, and EXHAUSTIVE presolving steps are only performed if all presolvers called before
1413 * Presolving functions should be assigned a timing based on how expensive they are, e.g., presolvers that provide fast algorithms that
1414 * usually have a high impact (i.e., remove lots of variables or tighten bounds of many variables) should have a timing FAST.
1415 * If a presolving function implements different algorithms of different complexity, it may also get multiple timings and check the timing
1418 * \par CONSHDLR_MAXPREROUNDS: the default maximal number of presolving rounds the constraint handler participates in.
1420 * If enough changes have been applied to the model, an additional preprocessing round is performed.
1421 * The MAXPREROUNDS parameter of a constraint handler denotes the maximal number of preprocessing rounds the constraint
1430 * Below the header "Data structures" you can find two structs called "struct SCIP_ConsData" and
1433 * The constraint handler data must be implemented as member variables of your constraint handler class.
1435 * The constraint data are the information that is needed to define a single constraint of the constraint handler's
1437 * For example, the data of a knapsack constraint would consist of a list of variables, a list of weights, and
1442 * The constraint handler data are additional variables, that belong to the constraint handler itself and which are
1444 * For example, you can use these data to store parameters of the constraint handler or statistical information.
1451 * At the bottom of "cons_subtour.c" you can find three interface functions, that also appear in "cons_subtour.h".
1452 * These are SCIPincludeConshdlrSubtour(), SCIPcreateConsSubtour(), and SCIPcreateConsSubtourBasic().
1455 * It is responsible for notifying SCIP of the presence of the constraint handler by calling the function
1457 * It is called by the user, if (s)he wants to include the constraint handler, i.e., if (s)he wants to make
1460 * -# If you are using constraint handler data, you have to <b>allocate the memory for the data</b> at this point.
1466 * -# Now, <b>SCIP gets notified</b> of the presence of the constraint handler together with its \ref CONS_FUNDAMENTALCALLBACKS "basic callbacks".
1471 * -# All \ref CONS_ADDITIONALCALLBACKS "additional callbacks" are added via their setter functions.
1476 * -# If the constraint handler is a specialization of a general linear or nonlinear constraint, we want to include an
1483 * SCIP_CALL( SCIPincludeNonlinconsUpgrade(scip, nonlinconsUpgdSubtour, NULL, NONLINCONSUPGD_PRIORITY, TRUE, CONSHDLR_NAME) );
1486 * in the nonlinear case. See also cons_nonlinear.h for further information about the general upgrade procedure in the nonlinear case.
1488 * Some parameters which are important to play with are added to every constraint automatically, as, e.g.,
1496 * The functions SCIPcreateConsSubtour() and SCIPcreateConsSubtourBasic() are called to create a single constraint of the constraint
1499 * Take a look at the following example from the \ref cons_knapsack.h "knapsack constraint handler":
1503 * In this example, consdataCreate() is a local function that allocates memory for the given consdata
1504 * and fills the data with the given <code>vars</code> array. For allocating memory for the constraint data, you
1513 * Besides the various functions which you will implement inside your constraint handler there exists a number
1515 * tasks which your constraint handler is able to provide to the solver. They are grouped into two
1525 * \ref CONS_ADDITIONALCALLBACKS "additional callbacks". Such callbacks can be used to allocate and free memory
1526 * at different stages of the solving process. Although not mandatory, it might be useful to implement
1530 * All callbacks should be passed to SCIP during the SCIPinclude<PLUGINTYPE><PLUGINNAME> function
1531 * (e.g., SCIPincludeConshdlrKnapsack() for the \ref cons_knapsack.h "knapsack constraint handler").
1532 * Since SCIP version 3.0, two ways of setting callbacks can be used, either via SCIPincludeConshdlr()
1533 * (all at once, as it always was), or via SCIPincludeConshdlrBasic() and setter functions for additional callbacks.
1540 * By implementing the fundamental callbacks, you define the semantics of the constraint class the constraint handler
1542 * If these functions are implemented, the resulting code is already correct and finds the optimal solution to the
1544 * However, it might be very slow because the additional features, like cut separation and domain propagation, are
1546 * In the C++ wrapper class scip::ObjConshdlr, the fundamental callbacks are virtual abstract member functions.
1547 * You have to implement them in order to be able to construct an object of your constraint handler class.
1549 * There are three fundamental callbacks that are all dealing with the feasibility of a given solution.
1551 * However, it is usually reasonable to implement a single local function that is called by all of the three callback
1561 * It has to return a result SCIP_FEASIBLE, if the solution satisfies all the constraints of the constraint handler,
1564 * If the solution is not NULL, SCIP should also be informed about the constraint violation with a call to
1565 * SCIPupdateSolConsViolation() and additionally SCIPupdateSolLPRowViolation() for every row of the constraint's current
1568 * is represented completely by a set of LP rows, meaning that the current constraint violation is equal to the maximum
1572 * That means, the constraint handler has to deal with arbitrary solutions that do not necessarily satisfy the bounds
1580 * For example, the \ref cons_knapsack.h "knapsack constraint handler" loops over its constraints and
1581 * calculates the scalar product \f$w^T x\f$ of weights \f$w\f$ with the solution vector \f$x\f$.
1583 * If it exceeds the capacity, the CONSCHECK function is immediately aborted with the result SCIP_INFEASIBLE.
1588 * The CONSENFOLP function is called after the price-and-cut loop was finished and an LP solution is available.
1589 * Like the CHECK call, the ENFOLP function should return a result SCIP_FEASIBLE, if the solution satisfies all the
1591 * However, the behavior should be different, if the solution violates some of the associated constraints.
1592 * The constraint handler may return a result SCIP_INFEASIBLE in this situation, but this is not the best what
1599 * - tightening the LP primal feasibility tolerance and requesting to solve the LP again (result SCIP_SOLVELP),
1602 * Note that in case SCIP_CONSADDED, the added constraints must be created with flag initial=TRUE.
1614 * By using the latter function, you can have a single local function to check a solution for feasibility by passing
1615 * the given <code>sol</code> to the CONSCHECK call and by passing a NULL pointer as <code>sol</code> to
1621 * The CONSENFOPS callback is similar to the CONSENFOLP callback, but deals with \em pseudo \em solutions instead
1624 * If the LP was not solved at the current subproblem (either because the user did not want to solve it, or because
1627 * In this solution, the variables are set to the local bound which is best with respect to the objective function.
1628 * You can think of the pseudo solution as solution to the LP relaxation with all constraints except the bounds
1631 * Like the ENFOLP callback, the ENFOPS callback has to check whether the pseudo solution satisfies all the constraints
1633 * The pseudo solution can be accessed by the same functions as the LP solution (SCIP knows, if the LP was solved at the
1636 * Unlike the ENFOLP callback, the ENFOPS callback must not add cuts and cannot return the result SCIP_SEPARATED.
1637 * It is, however, possible to force the solving of the LP by returning the result SCIP_SOLVELP.
1638 * For example, the infeasibility of a linear constraint that contains continuous variables cannot be resolved,
1640 * In this case, the LP has to be solved in order to get a solution that satisfies the linear constraint.
1644 * The CONSENFORELAX callback is similar to the CONSENFOLP and CONSENFOPS callbacks, but deals with relaxation solutions.
1646 * If the best bound computed by a relaxator that includes the whole LP is strictly better than the bound of the LP itself,
1647 * the corresponding relaxation solution will get enforced. Therefore the CONSENFORELAX callback will only be called for
1650 * Like the ENFOLP and ENFOPS callbacks, the ENFORELAX callback has to check whether the solution given in sol satisfies
1651 * all the constraints of the constraint handler. Since the callback is only called for relaxators including the whole LP,
1652 * cuts may be added with a result of SCIP_SEPARATED, like in the ENFOLP callback. It is also possible to return
1653 * SCIP_SOLVELP if the relaxation solution is invalid for some reason and the LP should be solved instead.
1655 * Note that the CONSENFORELAX callback is only relevant if relaxators are used. Since the basic distribution of the
1656 * SCIP Optimization Suite does not contain any relaxators, this callback can be ignored unless any relaxators are added
1662 * It has to tell SCIP, which variables are existing in the given constraint, and in which way modifications of these
1665 * For each variable that is affected by the constraint, the callback should call SCIPaddVarLocks():
1666 * - If the constraint may become violated by decreasing the value of a variable, it should call
1667 * SCIPaddVarLocks(scip, var, nlockspos, nlocksneg), saying that rounding down is potentially rendering the
1668 * (positive) constraint infeasible and rounding up is potentially rendering the negation of the constraint
1670 * - If the constraint may become violated by increasing the value of a variable, it should call
1671 * SCIPaddVarLocks(scip, var, nlocksneg, nlockspos), saying that rounding up is potentially rendering the
1672 * constraint's negation infeasible and rounding down is potentially rendering the constraint itself
1674 * - If the constraint may become violated by changing the variable in any direction, it should call
1677 * <b>Note:</b> You do not have to worry about nlockspos and nlocksneg. These integer values are given as
1678 * parameter of the CONSLOCK callback (see type_cons.h). Just use these variables in the above described
1679 * fashion <b>without</b> adding or subtracting anything to them. In case of the knapsack constraints this
1684 * To give same more intuition, consider the linear constraint \f$3x -5y +2z \leq 7\f$ as an example.
1686 * SCIPaddVarLocks(scip, x, nlocksneg, nlockspos), SCIPaddVarLocks(scip, y, nlockspos, nlocksneg),
1688 * and \f$z\f$ and rounding down of \f$y\f$ can destroy the feasibility of the constraint, while rounding
1700 * The additional callbacks do not need to be implemented in every case, but provide useful functionality
1701 * for many applications. They can be added to your constraint handler via setter functions, see
1706 * If you are using constraint handler data, you have to implement this function in order to free the
1707 * constraint handler data. This can be done by the following procedure (which is taken from the
1712 * If you have allocated memory for fields in your constraint handler data, remember to free this memory
1719 * The CONSHDLRCOPY callback is executed when the SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
1720 * callback as <code>NULL</code> the user disables the inclusion of the specified constraint handler into all copied SCIP
1721 * instances. This may deteriorate the performance of primal heuristics solving sub-SCIPs, since these constitute only
1725 * calls the interface function which includes the constraint handler to the model. For example, this callback is
1732 * A problem copy is called valid if it is valid in both the primal and the dual sense, i.e., if
1737 * A constraint handler may choose to not copy a constraint and still declare the resulting copy as valid. It must ensure
1740 * <b>Note:</b> If you implement this callback and the constraint handler needs constraints (see CONSHDLR_NEEDSCONS),
1746 * The constraint handler may, e.g., use this call to replace the original variables in its constraints by transformed
1752 * In this function, the constraint handler should free all resources that were allocated for the solving process.
1756 * The CONSINITPRE callback is executed before the preprocessing is started, even if presolving is turned off.
1757 * The constraint handler may use this call to initialize its presolving data, or to modify its constraints
1759 * Necessary constraint modifications that have to be performed even if presolving is turned off should be done here
1764 * The CONSEXITPRE callback is executed after the preprocessing has been finished, even if presolving is turned off.
1765 * The constraint handler may use this call e.g. to clean up its presolving data, or to finally modify its constraints
1767 * Necessary constraint modifications that have to be performed even if presolving is turned off should be done here
1773 * The CONSINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
1780 * The constraint handler should use this call to clean up its branch-and-bound data, in particular to release
1788 * The CONSDELETE callback is therefore the counterpart of the SCIPcreateCons...() interface function and the CONSTRANS
1793 * The CONSTRANS function is called for each constraint of the constraint handler, when the user starts the solving
1795 * It has to copy the original constraint data of the constraint to the memory for the transformed problem.
1798 * The original model is copied in order to protect it from transformations that are applied during the solving process,
1801 * If the solving process data are freed, the original data still exist and the user can, e.g., modify the problem and
1804 * If you do not implement the CONSTRANS function, a transformed constraint is created with the same flags and the
1808 * If you want to implement preprocessing functions or other functions that modify the constraint data, you have to
1811 * Here is an example, which is taken from the \ref cons_knapsack.h "knapsack constraint handler":
1818 * It should add the LP relaxations of all "initial" constraints to the LP. The function should scan the constraints
1819 * array for constraints that are marked initial via calls to SCIPconsIsInitial() and put the LP relaxation
1824 * The CONSSEPALP callback is executed during the price-and-cut loop of the subproblem processing.
1825 * It should try to generate cutting planes for the constraints of the constraint handler in order to separate
1829 * Usually, a separation callback searches and produces cuts, that are added with a call to SCIPaddRow().
1831 * If the cut is constructed via multiple calls to SCIPaddVarToRow(), then performance can be improved by calling
1836 * - detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
1840 * - stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints
1844 * - stating that a new separation round should be started without calling the remaining separator functions (result SCIP_NEWROUND)
1847 * CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, and CONSHDLR_DELAYSEPA, which influence the behaviour of SCIP
1853 * It should try to generate cutting planes for the constraints of the constraint handler in order to separate
1855 * The function is not called in the LP solution loop, which means that there is no valid LP solution.
1857 * Usually, a separation callback searches and produces cuts, that are added with a call to SCIPaddRow().
1859 * If the cut is constructed via multiple calls to SCIPaddVarToRow(), then performance can be improved by calling
1864 * - detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
1868 * - stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints
1872 * - stating that a new separation round should be started without calling the remaining separator functions (result SCIP_NEWROUND)
1875 * CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, and CONSHDLR_DELAYSEPA, which influence the behaviour of SCIP
1881 * It should propagate the constraints, which means that it should infer reductions in the variables' local bounds
1883 * This technique, which is the main workhorse of constraint programming, is called "node preprocessing" in the
1887 * - detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
1889 * - stating that the propagator searched, but did not find domain reductions, cutting planes, or cut constraints
1895 * CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, and CONSHDLR_PROP_TIMING, which influence the behaviour of SCIP
1900 * If the constraint handler should support \ref CONF "conflict analysis", it has to supply a CONSRESPROP function.
1901 * It also should call SCIPinferVarLbCons() or SCIPinferVarUbCons() in domain propagation instead of SCIPchgVarLb() or
1903 * In the SCIPinferVarLbCons() and SCIPinferVarUbCons() calls, the handler provides the constraint that deduced the
1904 * variable's bound change, and an integer value <code>inferinfo</code> that can be arbitrarily chosen.
1906 * The propagation conflict resolving function CONSRESPROP must then be implemented to provide the "reasons" for the bound
1907 * changes, i.e., the bounds of variables at the time of the propagation, which forced the constraint to set the
1908 * conflict variable's bound to its current value. It can use the <code>inferinfo</code> tag to identify its own propagation rule
1909 * and thus identify the "reason" bounds. The bounds that form the reason of the assignment must then be provided by
1910 * calls to SCIPaddConflictLb() and SCIPaddConflictUb() in the propagation conflict resolving function.
1912 * <b>Note:</b> The fact that <code>inferinfo</code> is an integer, as opposed to an arbitrary data object, is a compromise between space and speed. Sometimes a propagator would
1913 * need more information to efficiently infer the original propagation steps that lead to the conflict. This would,
1914 * however, require too much space. In the extreme, the original propagation steps have to be repeated.
1916 * For example, the \ref cons_logicor.h "logicor constraint" \f$c = x \vee y \vee z\f$ fixes variable \f$z\f$ to TRUE (i.e., changes the lower
1917 * bound of \f$z\f$ to 1.0), if both, \f$x\f$ and \f$y\f$, are assigned to FALSE (i.e., if the upper bounds of these
1918 * variables are 0.0). It uses <code>SCIPinferVarLbCons(scip, z, 1.0, c, 0)</code> to apply this assignment (an
1919 * inference information tag is not needed by the constraint handler and is set to 0). In the conflict analysis, the
1920 * constraint handler may be asked to resolve the lower bound change on \f$z\f$ with constraint \f$c\f$, that was
1921 * applied at a time given by a bound change index "bdchgidx". With a call to <code>SCIPgetVarLbAtIndex(z,
1922 * bdchgidx)</code>, the handler can find out, that the lower bound of variable \f$z\f$ was set to 1.0 at the given
1923 * point of time, and should call <code>SCIPaddConflictUb(scip, x, bdchgidx)</code> and <code>SCIPaddConflictUb(scip, y,
1924 * bdchgidx)</code> to tell SCIP, that the upper bounds of \f$x\f$ and \f$y\f$ at this point of time were the reason for
1927 * If conflict analysis should not be supported, the function has to set the result code to SCIP_DIDNOTFIND. Although
1928 * this is a viable approach to circumvent the implementation of the usually rather complex conflict resolving function, it
1929 * will make the conflict analysis less effective. We suggest to first omit the conflict resolving function and check how
1930 * effective the \ref CONSPROP "propagation function" is. If it produces a lot of propagations for your application, you definitely should
1936 * It should try to tighten the domains of the variables, tighten the coefficients of the constraints of the constraint
1937 * handler, delete redundant constraints, aggregate and fix variables if possible, and upgrade constraints to more
1940 * If the CONSPRESOL callback applies changes to the constraint data, you also have to implement the \ref CONSTRANS callback
1941 * in order to copy the constraint data to the transformed problem space and protect the original problem from the
1944 * To inform SCIP that the presolving function found a reduction the result pointer has to be set in a proper way.
1947 * - SCIP_UNBOUNDED : at least one variable is not bounded by any constraint in objective direction
1960 * The CONSACTIVE callback is called each time a constraint of the constraint handler is activated.
1961 * For example, if a constraint is added locally to a subproblem, the CONSACTIVE callback is called whenever the
1966 * The CONSDEACTIVE callback is called each time a constraint of the constraint handler is deactivated.
1967 * For example, if a constraint is added locally to a subproblem, the CONSDEACTIVE callback is called whenever the
1972 * The CONSENABLE callback is called each time a constraint of the constraint handler is enabled.
1973 * Constraints might be active without being enabled. In this case, only the feasibility checks are executed,
1978 * The CONSDISABLE callback is called each time a constraint of the constraint handler is disabled.
1982 * The CONSPRINT callback is called, when the user asks SCIP to display the problem to the screen
1983 * or save the problem into a file. This is, however, only the case if the user requested the CIP format.
1984 * For more details about reading and writing with SCIP we refer to the \ref READER "file readers". In this
1985 * callback the constraint handler should display the data of the constraint in an appropriate form.
1987 * In later versions of SCIP, the constraint handlers should also be able to parse (i.e., read) constraints
1992 * The CONSCOPY callback is used whenever constraints should be copied from one SCIP instance into another SCIP
1993 * instance. This function comes with the necessary parameters to do so, most importantly with a mapping of the variables of the
1994 * source SCIP instance to the corresponding variables of the target SCIP instance, and a mapping for the constraints
1997 * To get the corresponding target variable of a given source variable, you can use the variable map directly:
2003 * We recommend, however, to use the function SCIPgetVarCopy() which gets besides others the variable map and the constraint map as input
2004 * and returns the requested target variable. The advantage of using SCIPgetVarCopy() is that in the case
2008 * SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevar, &targetvar, varmap, consmap, global) );
2011 * Finally, the result pointer <code>valid</code> has to be set to TRUE if (and only if!) the copy process was successful.
2014 * A problem copy is called valid if it is valid in both the primal and the dual sense, i.e., if
2019 * A constraint handler may choose to not copy a constraint and still declare the resulting copy as valid. Therefore, it must ensure
2022 * For an example implementation we refer to cons_linear.h. Additional documentation and the complete list of all
2027 * This function is the counterpart to CONSPRINT. The ideal idea is that a constraint handler is able to parse the output
2028 * which it generated via the CONSPRINT function and creates the corresponding constraint. If the parsing was successfully
2029 * the result pointer success should be set to TRUE. An example implementation can be found in the \ref cons_linear.h
2034 * This function should iterate over the given constraints and delete all variables that were marked for deletion by SCIPdelVar().
2035 * Variable deletion is especially interesting for branch-cut-and-price applications. If your constraint handler allows
2036 * the addition of variables during the solving process (see "modifiable" attribute of constraints), then you might also want to
2037 * implement this callback. This would allow you to not only create variables during solving, but also remove them dynamically
2039 * During presolving, SCIP may also find that some variables are not needed anymore and then try
2040 * to delete them. Thus, if you do not implement this callback, the constraint handler should capture its variables via
2043 * Additional documentation and the complete list of all parameters can be found in the file type_cons.h.
2047 * The CONSGETVARS callback of a constraint handler can be implemented to give access to the constraint variables
2049 * is already passed, together with its length. Consider implementing @ref CONSGETNVARS, too, to have
2054 * This callback can be implemented to return the number of variables involved into a particular constraint.
2061 * This callback is used inside the various diving heuristics of SCIP and does not affect the normal branching
2063 * The constraint handler can provide this callback to render a current working solution (even more) infeasible by
2068 * Further documentation can be found in @ref type_cons.h for callback descriptions and a complete
2073/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
2079 * The \ref PRICERREDCOST and \ref PRICERFARKAS functions are called after each LP solve to generate additional
2080 * variables which may improve the objective value or decrease the LP infeasibility, respectively.
2084 * If the pricer finds one or more variables with negative reduced costs or negative Farkas value, it should
2085 * call SCIPcreateVar() and SCIPaddPricedVar() to create and add the variable to the problem. Additionally,
2086 * the pricer has to add the variable to all constraints in which it appears. Therefore, a pricer needs to
2087 * know the constraints of the model and their meaning. Note that all constraints for which additional variables
2091 * For example, look into the variable pricer for the binpacking problem (examples/Binpacking/src/pricer_binpacking.c) of the
2093 * The example is written in C. C++ users can easily adapt the code by using the scip::scip::ObjPricer wrapper base class and
2099 * Notice that if your pricer cannot cope with variable bounds other than 0 and infinity, you have to mark
2100 * all constraints containing priced variables as modifiable, and you may have to disable reduced cost
2104 * -# Copy the template files src/scip/pricer_xyz.c and src/scip/pricer_xyz.h into files "pricer_mypricer.c"
2107 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
2108 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
2110 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
2111 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
2117 * -# Implement the additional callbacks (see \ref PRICER_ADDITIONALCALLBACKS). This is optional.
2124 * In the C++ wrapper class, you have to provide the pricer properties by calling the constructor
2130 * Additionally, if you are searching for a pricer with SCIPfindPricer(), this name is looked up.
2137 * In each pricing round during the price-and-cut loop of the subproblem processing, the included pricers are
2140 * Usually, you will have only one pricer in your application and the priority is therefore irrelevant.
2142 * \par PRICER_DELAY: the default for whether the pricer should be delayed, if other variables with negative reduced
2144 * Variables may be declared to be "removable" in the SCIPcreateVar() call. This means that SCIP may remove the variable
2145 * from the LP if it was inactive (i.e., sitting at zero) for a number of LP solves. Nevertheless, after the removal of the
2146 * column from the LP, the variable still exists, and SCIP can calculate reduced costs and add it to the LP again if
2149 * If the PRICER_DELAY flag is set to TRUE (which is the common setting), all those existing variables with negative reduced costs
2150 * are added to the LP, and the LP is resolved before the pricer is called. Thus, the pricer can assume that all existing variables
2151 * have non-negative reduced costs if the \ref PRICERREDCOST function is called or non-positive Farkas value if the \ref PRICERFARKAS
2154 * In some applications, this inner pricing loop on the already existing variables can significantly slow down the solving process,
2155 * since it may lead to the addition of only very few variables in each pricing round. If this is an issue in your application,
2156 * you should consider setting the PRICER_DELAY flag to FALSE. You must, however, be aware of the fact that there may be already
2157 * existing variables with negative reduced costs. For example, this may lead to the issue that your pricer generates the same
2158 * variable twice. In some models, this is not critical because an optimal solution would choose only one of the two identical
2159 * variables anyway, but for other models this can lead to wrong results because the duplication of a variable essentially doubles
2165 * Below the header "Data structures" you can find a struct which is called "struct SCIP_PricerData".
2166 * In this data structure, you can store the data of your pricer. For example, it may be convenient to store pointers to the
2167 * constraints of the problem instance here, because the pricer has to add variables to those constraints.
2175 * At the bottom of "pricer_mypricer.c" you can find the interface function SCIPincludePricerMypricer(), which also appears in "pricer_mypricer.h".
2176 * It is called by the user, if (s)he wants to include the pricer, i.e., if (s)he wants to solve a model for which variables should
2180 * It is responsible for notifying SCIP of the presence of the pricer. For this, you can either call SCIPincludePricer(),
2181 * or SCIPincludePricerBasic() since SCIP version 3.0. In the latter variant, \ref PRICER_ADDITIONALCALLBACKS "additional callbacks"
2182 * must be added via setter functions as, e.g., SCIPsetPricerCopy(). We recommend this latter variant because
2183 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
2184 * variant must be manually adjusted with every SCIP release containing new callbacks for pricers in order to compile.
2187 * In addition, the pricer has to be activated before the solution process starts, like it is done
2188 * in the pricer of the Coloring application (applications/Coloring/src/reader_col.c) by calling
2200 * You may also add user parameters for your pricer, see the function SCIPincludePricerColoring() in the pricer of the Coloring application
2206 * The fundamental callbacks have to be implemented in order to obtain an operational algorithm.
2207 * They are passed together with the pricer itself to SCIP using SCIPincludePricer() or SCIPincludePricerBasic(),
2210 * In the case of a pricer, there are two fundamental callbacks, namely the @ref PRICERREDCOST and the
2211 * @ref PRICERFARKAS callbacks, which both search for new variables and add them to the problem.
2213 * In the C++ wrapper class scip::ObjPricer, the scip_redcost() method (which corresponds to the PRICERREDCOST callback)
2214 * is a virtual abstract member function. You have to implement it in order to be able to construct an object of your
2221 * The PRICERREDCOST callback is called inside the price-and-cut loop of the subproblem solving process if the current LP relaxation
2223 * It should search for additional variables that can contribute to improve the current LP's solution value.
2224 * In standard branch-and-price, these are variables with negative dual feasibility, that is negative
2228 * Whenever the pricer finds a variable with negative dual feasibility, it should call SCIPcreateVar()
2229 * and SCIPaddPricedVar() to add the variable to the problem. Furthermore, it should call the appropriate
2230 * functions of the constraint handlers to add the necessary variable entries to the constraints, see pub_cons.h.
2232 * In the usual case that the pricer either adds a new variable or ensures that there are no further variables with negative dual feasibility,
2233 * the result pointer should be set to SCIP_SUCCESS. Only if the pricer aborts pricing without creating a new variable, but
2234 * there might exist additional variables with negative dual feasibility, the result pointer should be set to SCIP_DIDNOTRUN.
2235 * In this case, which sometimes is referred to as "early branching", the LP solution will not be used as a lower bound.
2239 * Since SCIP does not know the semantics of the individual constraints in the problem, the dual solution
2241 * For example, the \ref cons_setppc.h "setppc constraint handler", which deals with set partitioning, packing, and covering constraints, provides
2242 * the function SCIPgetDualsolSetppc() to access the dual solution value for a single constraint.
2243 * Similarly, the dual solution of a linear constraint can be queried with the function SCIPgetDualsolLinear() of cons_linear.h.
2244 * The reduced costs of the existing variables can be accessed with the function SCIPgetVarRedcost().
2248 * If the current LP relaxation is infeasible, it is the task of the pricer to generate additional variables that can
2249 * potentially render the LP feasible again. In standard branch-and-price, these are variables with positive Farkas values,
2252 * If the LP was proven to be infeasible, we have an infeasibility proof by the dual Farkas multipliers \f$y\f$.
2253 * With the values of \f$y\f$, an implicit inequality \f$y^T A x \ge y^T b\f$ is associated, with \f$b\f$ given
2258 * \f$y\f$ is chosen in a way, such that the valid inequality \f$y^T A x \ge y^T b\f$ is violated by all \f$x\f$,
2262 * Pricing in this case means to add variables \f$i\f$ with positive Farkas value, i.e., \f$y^T A_i x'_i > 0\f$.
2264 * To apply Farkas pricing, the pricer needs to know the Farkas values of the constraints. Like the dual solution values for
2265 * feasible LP solutions, the dual Farkas values for infeasible solutions can be obtained by constraint handler interface
2267 * The Farkas values for the bounds of the variables can be accessed with SCIPgetVarFarkasCoef().
2269 * It is useful to note that Farkas pricing is the same as the regular pricing with a zero objective function.
2270 * Therefore, a typical implementation of a pricer would consist of a generic pricing algorithm that gets a dual solution and an
2271 * objective function vector as input and generates variables by calling SCIPcreateVar() and SCIPaddPricedVar().
2272 * The PRICERREDCOST callback would call this function with the regular objective function and the regular dual solution vector,
2273 * while the PRICERFARKAS callback would call this function with a zero objective function and the Farkas vector.
2274 * From a practical point of view, it is usually the simplest approach to provide just one Boolean flag to the generic pricing
2275 * algorithm in order to identify whether it is reduced cost or Farkas pricing. Then, the algorithm would just call the appropriate
2281 * However, some of them have to be implemented for most applications. They can either be passed directly with
2282 * SCIPincludePricer() to SCIP or via specific <b>setter functions</b> after a call of SCIPincludePricerBasic(),
2287 * If you are using pricer data, you have to implement this function in order to free the pricer data.
2298 * The PRICERCOPY callback is executed when the SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
2299 * callback as <code>NULL</code> the user disables the inclusion of the pricer into all copied SCIP
2300 * instances. This means that primal heuristics will work on a sub-SCIP that contains only a part of the variables
2301 * and no variables are priced in during the solving process of the sub-SCIP. Therefore, primal solutions found in the
2302 * copied problem are typically still valid for the original problem and used for its solving process,
2305 * <b>Note:</b> If you implement this callback, be careful when setting the valid pointer. The valid pointer should be
2306 * set to TRUE if (and only if!) you can make sure that all necessary data of the pricer are copied
2307 * correctly. If the complete problem is validly copied, i.e. if the copy functions of all problem defining plugins
2308 * (constraint handlers and pricers) return <code>*valid = TRUE</code>, then dual reductions found for the copied problem can be
2309 * transferred to the original SCIP instance. Thus, if the valid pointer is wrongly set to TRUE, it might happen that
2315 * The pricer may, e.g., use this call to replace the original constraints stored in its pricer data by transformed
2321 * In this function, the pricer should free all resources that have been allocated for the solving process in PRICERINIT.
2325 * The PRICERINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to begin.
2331 * The pricer should use this call to clean up its branch-and-bound data, which was allocated in PRICERINITSOL.
2335 * If you use your own branching rule (e.g., to branch on constraints), make sure that it is able to branch on \a "pseudo solutions".
2336 * Otherwise, SCIP will use its default branching rules, if necessary (which all branch on variables). This
2337 * could disturb the pricing problem or branching might not even be possible, e.g., if all variables created thus far have already been fixed.
2339 * Note that if the original problem is a maximization problem, SCIP will transform the problem into a minimization
2340 * problem by multiplying the objective function by -1. The pricer has to take care of this by multiplying
2341 * the original objective function value of all variables created during the solving process by -1.
2343 * In some cases, bounds on variables are implicitly enforced by constraints of the problem and the objective function.
2344 * Therefore, these bounds do not need to be added to the LP explicitly, which has the advantage that the pricing routine does not need to
2346 * We call these bounds lazy bounds, they may be set by SCIPchgVarLbLazy() and SCIPchgVarUbLazy() for upper or lower bounds, respectively.
2348 * In diving mode, lazy bounds are explicitly put into the LP, because changing the objective (which is only possible in diving)
2349 * might reverse the implicitly given bounds. When diving is finished, the bounds are again removed from the LP.
2352/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
2356 * Presolvers are used to reduce the size of the model by removing irrelevant information like redundant constraints,
2357 * to strengthen the LP relaxation by exploiting integrality information, and to extract useful information in the
2359 * Constraint based presolving is done in the CONSPRESOL callbacks of the constraint handlers, see \ref CONSPRESOL.
2360 * Some propagation steps can already be applied in presolving via the PROPRESOL callbacks of propagators, see \ref PROPPRESOL.
2361 * The presolver plugins complement these by additional, usually optimality based, presolving reductions.
2363 * A complete list of all presolvers contained in this release can be found \ref PRESOLVERS "here".
2367 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjPresol wrapper
2368 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_PRESOL... callbacks.
2370 * Additional documentation for the callbacks of a presolver, in particular for their input parameters,
2374 * -# Copy the template files src/scip/presol_xyz.c and src/scip/presol_xyz.h into files named "presol_mypresolver.c"
2377 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
2378 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
2379 * -# Use `SCIPincludePresolMypresolver()` in order to include the presolver into your SCIP instance,
2380 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
2381 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
2382 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mypresolver".
2387 * -# Implement the additional callbacks (see \ref PRESOL_ADDITIONALCALLBACKS). This is optional.
2394 * In the C++ wrapper class, you have to provide the presolver properties by calling the constructor
2400 * Additionally, if you are searching for a presolver with SCIPfindPresol(), this name is looked up.
2408 * Every presolving round starts with the FAST presolvers. MEDIUM presolvers are only called, if FAST presolvers did not find
2409 * enough reductions in this round so far, and EXHAUSTIVE presolving steps are only performed if all presolvers called before
2411 * Presolvers should be assigned a timing based on how expensive they are, e.g., presolvers that provide fast algorithms that
2412 * usually have a high impact (i.e., remove lots of variables or tighten bounds of many variables) should have a timing FAST.
2413 * If a presolver implements different algorithms of different complexity, it may also get multiple timings and check the timing
2417 * Within a presolving round, when calling all presolvers and presolving functions of propagators and constraint handlers
2419 * a predefined order, which is given by the priorities of the presolvers and the check priorities of the
2421 * First, the presolvers with non-negative priority are called in the order of decreasing priority.
2422 * Next, the presolving functions of the different constraint handlers are called in the order of decreasing check
2424 * Finally, the presolvers with negative priority are called in the order of decreasing priority.
2426 * Again, presolvers that provide fast algorithms that usually have a high impact (i.e., remove lots of variables or tighten
2429 * priorities of all presolvers, propagators, and constraint handlers is to type "display presolvers", "display propagators",
2433 * The presolving is conducted in rounds: the presolvers and presolving functions of the constraint handlers
2434 * are called iteratively until no more reductions have been found or some other abort criterion applies.
2435 * The "maxrounds" parameter of a presolver imposes a limit on the number of presolving rounds in which the
2436 * presolver is called. The PRESOL_MAXROUNDS property specifies the default value for this parameter.
2442 * Below the header "Data structures" you can find a struct which is called "struct SCIP_PresolData".
2443 * In this data structure, you can store the data of your presolver. For example, you should store the adjustable parameters
2452 * At the bottom of "presol_mypresolver.c", you can find the interface function SCIPincludePresolMypresolver(),
2454 * SCIPincludePresolMypresolver() is called by the user, if (s)he wants to include the presolver,
2458 * It is responsible for notifying SCIP of the presence of the presolver. For this, you can either call SCIPincludePresol(),
2459 * or SCIPincludePresolBasic() since SCIP version 3.0. In the latter variant, \ref PRESOL_ADDITIONALCALLBACKS "additional callbacks"
2460 * must be added via setter functions as, e.g., SCIPsetPresolCopy(). We recommend this latter variant because
2461 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
2462 * variant must be manually adjusted with every SCIP release containing new callbacks for presolvers in order to compile.
2472 * You may also add user parameters for your presolver, see \ref PARAM for how to add user parameters and
2478 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
2480 * They are passed together with the presolver itself to SCIP using SCIPincludePresol() or SCIPincludePresolBasic(),
2485 * In the C++ wrapper class scip::ObjPresol, the scip_exec() method (which corresponds to the PRESOLEXEC callback) is a virtual
2494 * The PRESOLEXEC callback is called inside the presolving loop and should perform the actual presolving reductions.
2495 * It should inspect the problem instance at hand and simplify it by tightening bounds of variables, aggregating or fixing
2496 * variables, changing the type of variables, modifying the graph that represents the instance of your application, and
2499 * Typical functions called by a presolver are, for example, SCIPchgVarType(), SCIPfixVar(), SCIPaggregateVars(), SCIPtightenVarLb(),
2505 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
2506 * implemented for most applications, they can be used, for example, to initialize and free private data.
2507 * Additional callbacks can either be passed directly with SCIPincludePresol() to SCIP or via specific
2508 * <b>setter functions</b> after a call of SCIPincludePresolBasic(), see also @ref PRESOL_INTERFACE.
2512 * If you are using presolver data (see \ref PRESOL_DATA and \ref PRESOL_INTERFACE), you have to implement this function in order to free the presolver data.
2541 * In this function, the presolver should free all resources that have been allocated for the solving process in PRESOLINIT.
2546 * The presolver may use this call to initialize its presolving data which only need to exist during the presolving stage.
2550 * The PRESOLEXITPRE callback is executed after presolving finishes and before the branch-and-bound process begins.
2551 * The presolver should use this call to clean up its presolving data, which was allocated in PRESOLINITPRE.
2554/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
2558 * Separators are used to generate cutting planes that strengthen the LP relaxation of the problem formulation, but are
2560 * In contrast, constraint-based cutting planes, the second type of cutting planes in SCIP, are separated in the CONSSEPALP and
2561 * CONSSEPASOL callbacks of the constraint handlers, see \ref CONSSEPALP and \ref CONSSEPASOL. These cuts are
2562 * valid inequalities or even facets of the polyhedron described by a single constraint or a subset of the constraints of
2564 * "When should I implement a constraint handler, when should I implement a separator?" on \ref FAQ.
2566 * A complete list of all separators contained in this release can be found \ref SEPARATORS "here".
2569 * Take the separator for the class of Gomory mixed integer inequalities (src/scip/sepa_gomory.c) as an example.
2570 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjSepa wrapper
2571 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_SEPA... callbacks.
2573 * Additional documentation for the callbacks of a separator, in particular for the input parameters,
2577 * -# Copy the template files src/scip/sepa_xyz.c and src/scip/sepa_xyz.h into files "sepa_myseparator.c"
2580 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
2581 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
2582 * -# Use `SCIPincludeSepaMyseparator()` in order to include the separator into your SCIP instance,
2583 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
2584 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
2585 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "myseparator".
2597 * In the C++ wrapper class, you have to provide the separator properties by calling the constructor
2603 * Additionally, if you are searching for a separator with SCIPfindSepa(), this name is looked up.
2610 * In each separation round during the price-and-cut loop of the subproblem processing or the separation loop
2611 * of the primal solution separation, the separators and separation functions of the constraint handlers are called in
2612 * a predefined order, which is given by the priorities of the separators and the separation priorities
2614 * First, the separators with non-negative priority are called in the order of decreasing priority.
2615 * Next, the separation functions of the constraint handlers are called in the order of decreasing separation
2617 * Finally, the separators with negative priority are called in the order of decreasing priority. An easy way to list the
2618 * priorities of all separators and constraint handlers is to type "display separators" and "display conshdlrs" in
2621 * The priority of the separator should be set according to the complexity of the cut separation algorithm and the
2622 * impact of the resulting cuts: separators that provide fast algorithms that usually have a high impact (i.e., cut off
2627 * The frequency defines the depth levels at which the separation functions \ref SEPAEXECLP and \ref SEPAEXECSOL are called.
2628 * For example, a frequency of 7 means, that the separation callback is executed for subproblems that are in depth
2629 * 0, 7, 14, ... of the branching tree. A frequency of 0 means, that the separation function is only called at the root node.
2632 * The frequency can be adjusted by the user. This property of the separator only defines the default value of the frequency.
2633 * If you want to have a more flexible control of when to execute the separation algorithm, you have to assign
2634 * a frequency of 1 and implement a check at the beginning of your separation functions whether you really want to execute
2638 * \par SEPA_MAXBOUNDDIST: the default maximal relative distance from the current node's dual bound to primal bound compared to best node's dual bound for applying separation.
2639 * At the current branch-and-bound node, the relative distance from its dual bound (local dual bound)
2640 * to the primal bound compared to the best node's dual bound (global dual bound) is considered. The separation function
2641 * of the separator will only be applied at the current node if this relative distance does not exceed SEPA_MAXBOUNDDIST.
2643 * For example, if the global dual bound is 50 and the primal bound is 60, SEPA_MAXBOUNDDIST = 0.25 means that separation
2644 * is only applied if the current node's dual bound is in the first quarter of the interval [50,60], i.e., if it is less
2647 * In particular, the values 0.0 and 1.0 mean that separation is applied at the current best node only or at all
2648 * nodes, respectively. Since separation seems to be most important to apply at nodes that define to the global
2651 * Obviously, at the root node the local dual bound is equal to the global dual bound and thus, the separator is called
2655 * Some heuristics and separators solve MIPs or SAT problems and use a secondary SCIP instance. Examples are
2656 * Large Neighborhood Search heuristics such as RINS and Local Branching or the CGMIP separator. To avoid recursion,
2657 * these plugins usually deactivate all other plugins that solve MIPs. If a separator uses a secondary SCIP instance,
2658 * this parameter has to be TRUE and it is recommended to call SCIPsetSubscipsOff() for the secondary SCIP instance.
2660 * \par SEPA_DELAY: the default for whether the separation function should be delayed, if other separators or constraint handlers found cuts.
2661 * If the separator's separation function is marked to be delayed, it is only executed after no other separator
2662 * or constraint handler found a cut during the price-and-cut loop, and in the last separation or stalling round,
2663 * either in the end, or in an additional round if only the maximal subsequent round is exceeded.
2664 * If the separation function of the separator is very expensive, you may want to mark it to be delayed until all cheap
2669 * Below the header "Data structures" you can find a struct which is called "struct SCIP_SepaData".
2670 * In this data structure, you can store the data of your separator. For example, you should store the adjustable
2671 * parameters of the separator in this data structure. In a separator, user parameters for the maximal number of
2672 * separation rounds per node and for the maximal number of cuts separated per separation round might be useful.
2679 * At the bottom of "sepa_myseparator.c", you can find the interface function SCIPincludeSepaMyseparator(),
2685 * It is responsible for notifying SCIP of the presence of the separator. For this, you can either call SCIPincludeSepa(),
2686 * or SCIPincludeSepaBasic() since SCIP version 3.0. In the latter variant, \ref SEPA_ADDITIONALCALLBACKS "additional callbacks"
2687 * must be added via setter functions as, e.g., SCIPsetSepaCopy(). We recommend this latter variant because
2688 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
2689 * variant must be manually adjusted with every SCIP release containing new callbacks for separators in order to compile.
2699 * You may also add user parameters for your separator, see \ref PARAM for how to add user parameters and
2705 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
2707 * They are passed together with the separator itself to SCIP using SCIPincludeSepa() or SCIPincludeSepaBasic(),
2710 * Separator plugins have two callbacks, @ref SEPAEXECLP and @ref SEPAEXECSOL, of which at least one must be implemented.
2717 * The SEPAEXECLP callback is executed during the price-and-cut loop of the subproblem processing.
2718 * It should try to generate general purpose cutting planes in order to separate the current LP solution.
2721 * Usually, the callback searches and produces cuts, that are added with a call to SCIPaddRow().
2723 * If the cut is constructed via multiple calls to SCIPaddVarToRow(), then performance can be improved by calling
2725 * In addition to LP rows, the callback may also produce domain reductions or add additional constraints.
2727 * Overall, the SEPAEXECLP callback has the following options, which is indicated by the possible return values of
2729 * - detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
2733 * - stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints
2737 * - stating that a new separation round should be started without calling the remaining separator functions (result SCIP_NEWROUND)
2741 * The SEPAEXECSOL callback is executed during the separation loop on arbitrary primal solutions.
2742 * It should try to generate general purpose cutting planes in order to separate the given primal solution.
2743 * The function is not called in the LP solution loop, which means that there is no valid LP solution.
2745 * In the standard SCIP environment, the SEPAEXECSOL callback is not used because only LP solutions are
2746 * separated. The SEPAEXECSOL callback provides means to support external relaxation handlers like semidefinite
2747 * relaxations that want to separate an intermediate primal solution vector. Thus, if you do not want to support
2750 * Usually, the callback searches and produces cuts, that are added with a call to SCIPaddRow().
2752 * If the cut is constructed via multiple calls to SCIPaddVarToRow(), then performance can be improved by calling
2754 * In addition to LP rows, the callback may also produce domain reductions or add other constraints.
2756 * Overall, the SEPAEXECSOL callback has the following options, which is indicated by the possible return values of
2758 * - detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
2762 * - stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints
2766 * - stating that a new separation round should be started without calling the remaining separator functions (result SCIP_NEWROUND)
2771 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
2772 * implemented for most applications, they can be used, for example, to initialize and free private data.
2773 * Additional callbacks can either be passed directly with SCIPincludeSepa() to SCIP or via specific
2774 * <b>setter functions</b> after a call of SCIPincludeSepaBasic(), see also @ref SEPA_INTERFACE.
2778 * If you are using separator data (see \ref SEPA_DATA and \ref SEPA_INTERFACE), you have to implement this function
2807 * In this function, the separator should free all resources that have been allocated for the solving process in SEPAINIT.
2811 * The SEPAINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
2816 * The SEPAEXITSOL callback is executed before the branch-and-bound process is freed. The separator should use this call
2817 * to clean up its branch-and-bound data, in particular to release all LP rows that it has created or captured.
2820/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
2824 * Propagators are used to tighten the domains of the variables. Like for cutting planes, there are two different types
2825 * of domain propagations. Constraint based (primal) domain propagation algorithms are part of the corresponding
2826 * constraint handlers, see \ref CONSPROP. In contrast, domain propagators usually provide dual propagations, i.e.,
2827 * propagations that can be applied using the objective function and the current best known primal solution. This
2830 * A complete list of all propagators contained in this release can be found \ref PROPAGATORS "here".
2832 * We now explain how users can add their own propagators. Take the pseudo objective function propagator
2833 * (src/scip/prop_pseudoobj.c) as an example. As all other default plugins, it is written in C. C++ users can easily
2834 * adapt the code by using the scip::ObjProp wrapper base class and implement the @c scip_...() virtual methods instead
2837 * Additional documentation for the callbacks of a propagator can be found in the file type_prop.h.
2840 * -# Copy the template files src/scip/prop_xyz.c and src/scip/prop_xyz.h into files named "prop_mypropagator.c"
2843 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
2844 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
2845 * -# Use `SCIPincludePropMypropagator()` in order to include the propagator into your SCIP instance,
2846 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
2847 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
2848 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mypropagator".
2857 * At the top of the new file "prop_mypropagator.c" you can find the propagator properties. These are given as compiler
2860 * In the C++ wrapper class, you have to provide the propagator properties by calling the constructor of the
2861 * abstract base class scip::ObjProp from within your constructor. The properties you have the following meaning:
2866 * This name is used in the interactive shell to address the propagator. Additionally, if you are searching for a
2867 * propagator with SCIPfindProp(), this name is searched for. Names have to be unique: no two propagators may have the
2874 * In each propagation round, the propagators and propagation functions of the constraint handlers are called in a
2875 * predefined order, which is given by the priorities of the propagators and the check priorities of the constraint
2876 * handlers. First, the propagators with non-negative priority are called in order of decreasing priority. Next, the
2877 * propagation functions of the different constraint handlers are called in order of decreasing check priority. Finally,
2878 * the propagators with negative priority are called in order of decreasing priority. \n The priority of the
2879 * propagators should be set according to the complexity of the propagation algorithm and the impact of the domain
2880 * propagations: propagators providing fast algorithms that usually have a high impact (i.e., tighten many bounds)
2884 * The frequency defines the depth levels at which the propagation function \ref PROPEXEC is called. For example, a
2885 * frequency of 7 means, that the propagation callback is executed for subproblems that are in depth 0, 7, 14, ... of
2886 * the branching tree. A frequency of 0 means that propagation is only applied in preprocessing and at the root node. A
2889 * The frequency can be adjusted by the user. This property of the propagator only defines the default value of the
2891 * <b>Note:</b> If you want to have a more flexible control of when to execute the propagation algorithm, you have to
2892 * assign a frequency of 1 and implement a check at the beginning of your propagation algorithm whether you really want
2893 * to execute the domain propagation or not. If you do not want to execute it, set the result code to SCIP_DIDNOTRUN.
2895 * \par PROP_DELAY: the default for whether the propagation function should be delayed, if other propagators or constraint handlers found domain reductions.
2896 * If the propagator's propagation function is marked to be delayed, it is only executed after no other propagator or
2897 * constraint handler found a domain reduction in the current iteration of the domain propagation loop. If the
2898 * propagation function of the propagator is very expensive, you may want to mark it to be delayed until all cheap
2904 * Possible values are defined in type_timing.h and can be concatenated, e.g., as in SCIP_PROPTIMING_ALWAYS.
2912 * Every presolving round starts with the FAST presolvers. MEDIUM presolvers are only called, if FAST presolvers did not find
2913 * enough reductions in this round so far, and EXHAUSTIVE presolving steps are only performed if all presolvers called before
2915 * Presolving functions should be assigned a timing based on how expensive they are, e.g., presolvers that provide fast algorithms that
2916 * usually have a high impact (i.e., remove lots of variables or tighten bounds of many variables) should have a timing FAST.
2917 * If a presolving function implements different algorithms of different complexity, it may also get multiple timings and check the timing
2921 * This attribute is analogous to the PROP_PRIORITY flag, but deals with the preprocessing function of the presolver.
2923 * \par PROP_PRESOL_MAXROUNDS: the default maximal number of presolving rounds the propagator participates in.
2925 * If enough changes have been applied to the model, an additional preprocessing round is performed.
2926 * The MAXROUNDS parameter of a propagator denotes the maximal number of preprocessing rounds, the propagator
2933 * Below the title "Data structures" you can find a struct called <code>struct SCIP_PropData</code>. In this data
2934 * structure, you can store the data of your propagator. For example, you should store the adjustable parameters of the
2935 * propagator in this data structure. If you are using C++, you can add propagator data as object variables to your
2943 * At the bottom of "prop_mypropagator.c", you can find the interface function SCIPincludeSepaMypropagator(),
2945 * SCIPincludePropMypropagator() is called by the user, if (s)he wants to include the propagator,
2949 * It is responsible for notifying SCIP of the presence of the propagator. For this, you can either call SCIPincludeProp(),
2950 * or SCIPincludePropBasic() since SCIP version 3.0. In the latter variant, \ref PROP_ADDITIONALCALLBACKS "additional callbacks"
2951 * must be added via setter functions as, e.g., SCIPsetPropCopy(). We recommend this latter variant because
2952 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
2953 * variant must be manually adjusted with every SCIP release containing new callbacks for separators in order to compile.
2956 * If you are using propagator data, you have to allocate the memory for the data at this point. You can do this by
2963 * You may also add user parameters for your propagator, see the function SCIPincludePropPseudoobj() in
2969 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
2971 * They are passed together with the propagator itself to SCIP using SCIPincludeProp() or SCIPincludePropBasic(),
2975 * This function has to be implemented for every propagator; the other callbacks are optional. In the
2976 * C++ wrapper class scip::ObjProp, the scip_exec() method (which corresponds to the \ref PROPEXEC
2984 * The PROPEXEC callback is called during presolving and during the subproblem processing. It should perform the actual
2985 * domain propagation, which means that it should tighten the variables' bounds. The technique of domain propagation,
2986 * which is the main workhorse of constraint programming, is called "node preprocessing" in the Integer Programming
2990 * - detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
2992 * - stating that the propagator searched, but did not find domain reductions, cutting planes, or cut constraints
3001 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
3002 * implemented for most applications, they can be used, for example, to initialize and free private data.
3003 * Additional callbacks can either be passed directly with SCIPincludeProp() to SCIP or via specific
3004 * <b>setter functions</b> after a call of SCIPincludePropBasic(), see also @ref PROP_INTERFACE.
3008 * If the propagator wants to support \ref CONF "conflict analysis", it has to supply the PROPRESPROP function. It also should call
3009 * SCIPinferVarLbProp() or SCIPinferVarUbProp() in the domain propagation instead of SCIPchgVarLb() or SCIPchgVarUb() in
3010 * order to deduce bound changes on variables. In the SCIPinferVarLbProp() and SCIPinferVarUbProp() calls, the
3011 * propagator provides a pointer to itself and an integer value "inferinfo" that can be arbitrarily chosen.
3013 * The propagation conflict resolving function PROPRESPROP must then be implemented to provide the "reasons" for the bound
3014 * changes, i.e., the bounds of variables at the time of the propagation, which forced the propagator to set the
3015 * conflict variable's bound to its current value. It can use the "inferinfo" tag to identify its own propagation rule
3016 * and thus identify the "reason" bounds. The bounds that form the reason of the assignment must then be provided by
3017 * calls to SCIPaddConflictLb() and SCIPaddConflictUb() in the propagation conflict resolving function.
3019 * See the description of the propagation conflict resolving function \ref CONSRESPROP of constraint handlers for
3022 * Omitting the PROPRESPROP callback circumvents the implementation of the usually rather complex conflict resolving function.
3024 * will make the conflict analysis less effective. We suggest to first omit the conflict resolving function and check how
3025 * effective the propagation function is. If it produces a lot of propagations for your application, you definitely should
3031 * If you are using propagator data, you have to implement this function in order to free the propagator data.
3036 * If you have allocated memory for fields in your propagator data, remember to free this memory
3043 * The PROPINIT callback is executed after the problem is transformed. The propagator may, e.g., use this call to
3058 * In this function, the propagator should free all resources that have been allocated for the solving process in PROPINIT.
3062 * The PROPINITPRE callback is executed before the preprocessing is started, even if presolving is turned off.
3063 * The propagator may use this call to initialize its presolving data before the presolving process begins.
3067 * The PROPEXITPRE callback is executed after the preprocessing has been finished, even if presolving is turned off.
3073 * The PROPINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
3087 * To inform SCIP that the presolving function found a reduction the result pointer has to be set in a proper way.
3090 * - SCIP_UNBOUNDED : at least one variable is not bounded by any constraint in objective direction
3091 * - SCIP_CUTOFF : at least one domain reduction that renders the problem infeasible has been found
3104/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
3108 * Branching rules are used to split the problem at the current node into smaller subproblems. Branching rules can be called at three
3111 * - the LP solution of the current problem is fractional. In this case, the integrality constraint handler calls the
3113 * - the list of external branching candidates is not empty. This will only be the case if branching candidates were added
3114 * by a user's \ref RELAX "relaxation handler" or \ref CONS "constraint handler" plugin, calling SCIPaddExternBranchCand().
3116 * - if an integral solution violates one or more constraints and this infeasibility could not be resolved in the callbacks
3117 * \ref CONSENFOLP and \ref CONSENFOPS of the corresponding constraint handlers. In this case, the \ref BRANCHEXECPS function will be called. This is the
3118 * standard case, if you use SCIP as a pure CP or SAT solver. If the LP or any other type of relaxation is used, then
3121 * The idea of branching rules is to take a global view on the problem. In contrast, branching paradigms which are
3122 * specific to one type of constraint are best implemented within the enforcement callbacks of your constraint handler.
3123 * See, e.g., the constraint specific branching rules provided by the constraint handlers for special ordered sets
3126 * All branching rules that come with the default distribution of SCIP create two subproblems by splitting a single
3127 * variable's domain. It is, however, fully supported to implement much more general branching schemes, for example by
3128 * creating more than two subproblems, or by adding additional constraints to the subproblems instead of tightening the
3131 * A complete list of all branching rules contained in this release can be found \ref BRANCHINGRULES "here".
3132 * However, note that constraint handlers can implement their own branching when enforcing constraints.
3133 * In particular the handler for nonlinear constraints currently does not use the branching plugins for spatial branching
3134 * by default. Its behavior can be adjusted with the parameters in category constraints/nonlinear/branching.
3136 * We now explain how users can add their own branching rules. Take the most infeasible LP branching rule
3137 * (src/scip/branch_mostinf.c) as an example. As all other default plugins, it is written in C. C++ users can easily
3138 * adapt the code by using the scip::ObjBranchrule wrapper base class and implement the scip_...() virtual methods instead of
3141 * Additional documentation for the callbacks of a branching rule can be found in the file type_branch.h.
3147 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
3148 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
3149 * -# Use `SCIPincludeBranchruleMybranchingrule()` in order to include the branching rule into your SCIP instance,
3150 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
3151 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
3152 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mybranchingrule".
3157 * -# Implement the additional callbacks (see \ref BRANCHRULE_ADDITIONALCALLBACKS). This is optional.
3162 * At the top of the new file "branch_mybranchingrule.c" you can find the branching rule properties.
3164 * In the C++ wrapper class, you have to provide the branching rule properties by calling the constructor
3170 * Additionally, if you are searching for a branching rule with SCIPfindBranchrule(), this name is looked up.
3177 * In the subproblem processing, the branching rules are called in decreasing order of their priority until
3178 * one succeeded to branch. Since most branching rules are able to generate a branching in all situations,
3180 * BRANCHRULE_MAXBOUNDDIST settings, however, interesting strategies can be easily employed. For example,
3181 * the user can set the priority of the "full strong branching" strategy to the highest value and assign the
3182 * second highest value to the "reliable pseudo cost" rule. If (s)he also sets the maximal depth for the
3183 * "full strong branching" to 5, in the top 5 depth levels of the search tree the "full strong branching" is
3186 * Note that the BRANCHRULE_PRIORITY property only specifies the default value of the priority. The user can
3189 * \par BRANCHRULE_MAXDEPTH: the default value for the maximal depth level of the branching rule.
3190 * This parameter denotes the maximal depth level in the branch-and-bound tree up to which the branching function of the
3193 * Note that this property only specifies the default value. The user can change this value arbitrarily.
3195 * \par BRANCHRULE_MAXBOUNDDIST: the default value for the maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying branching.
3196 * At the current branch-and-bound node, the relative distance from its dual bound (local dual bound)
3197 * to the primal bound compared to the best node's dual bound (global dual bound) is considered. The branching function of
3198 * the branching rule will only be applied at the node if this relative distance does not exceed BRANCHRULE_MAXBOUNDDIST.
3200 * For example, if the global dual bound is 50 and the primal bound is 60, BRANCHRULE_MAXBOUNDDIST = 0.25 means that
3201 * branching is only applied if the current node's dual bound is in the first quarter of the interval [50,60], i.e., if it
3202 * is less than or equal to 52.5. In particular, the values 0.0 and 1.0 mean that the branching rule is applied at the
3205 * Note that the BRANCHRULE_MAXBOUNDDIST property only specifies the default value of the maximal bound distance.
3211 * Below the header "Data structures" you can find a struct which is called "struct SCIP_BranchruleData".
3212 * In this data structure, you can store the data of your branching rule. For example, you should store the adjustable
3214 * If you are using C++, you can add branching rule data as usual as object variables to your class.
3221 * At the bottom of "branch_mybranchingrule.c", you can find the interface function SCIPincludeBranchruleMybranchingrule(),
3223 * SCIPincludeBranchruleMybranchingrule() is called by the user, if (s)he wants to include the branching rule,
3227 * It is responsible for notifying SCIP of the presence of the branching rule. For this, you can either call
3229 * or SCIPincludeBranchruleBasic() since SCIP version 3.0. In the latter variant, \ref BRANCHRULE_ADDITIONALCALLBACKS "additional callbacks"
3230 * must be added via setter functions as, e.g., SCIPsetBranchruleCopy(). We recommend this latter variant because
3231 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
3232 * variant must be manually adjusted with every SCIP release containing new callbacks for branchrule in order to compile.
3235 * If you are using branching rule data, you have to allocate the memory for the data at this point.
3242 * You may also add user parameters for your branching rule, see the function SCIPincludeBranchruleRelpscost() in
3249 * In most cases, however, you want to implement the \ref BRANCHEXECLP function and sometimes the \ref BRANCHEXECPS function.
3254 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
3255 * implemented for most applications, they can be used, for example, to initialize and free private data.
3256 * Additional callbacks can either be passed directly with SCIPincludeBranchrule() to SCIP or via specific
3257 * <b>setter functions</b> after a call of SCIPincludeBranchruleBasic(), see also @ref BRANCHRULE_INTERFACE.
3266 * The BRANCHEXECLP callback is executed during node processing if a fractional LP solution is available. It should
3267 * split the current problem into smaller subproblems. Usually, the branching is done in a way such that the current
3268 * fractional LP solution is no longer feasible in the relaxation of the subproblems. It is, however, possible to
3269 * create a child node for which the fractional LP solution is still feasible in the relaxation, for example, by
3270 * branching on a variable with integral LP value. In every case, you have to make sure that each subproblem is a
3271 * proper restriction of the current problem. Otherwise, you risk to produce an infinite path in the search tree.
3273 * The user gains access to the branching candidates, i.e., to the fractional variables, and their LP solution values by
3274 * calling the function SCIPgetLPBranchCands(). Furthermore, SCIP provides two functions for performing the actual
3277 * Given an integral variable \f$x\f$ with fractional LP solution value \f$x^*\f$, the function SCIPbranchVar() creates
3278 * two child nodes; one contains the bound \f$x \le \lfloor x^* \rfloor\f$ and the other one contains the bound \f$x \ge
3279 * \lceil x^* \rceil\f$, see the BRANCHEXECLP callback in src/scip/branch_mostinf.c for an example. In addition, if a
3280 * proven lower objective bound of a created child node is known, like after strong branching has been applied, the user
3281 * may call the function SCIPupdateNodeLowerbound() in order to update the child node's lower bound.
3287 * The BRANCHEXECEXT callback is executed during node processing if no LP solution is available and the list of
3288 * external branching candidates is not empty. It should split the current problem into smaller subproblems. If you
3289 * do not use relaxation handlers or constraints handlers that provide external branching candidates, you do not need to
3292 * In contrast to the LP branching candidates and the pseudo branching candidates, the list of external branching
3293 * candidates will not be generated automatically. The user has to add all variables to the list by calling
3294 * SCIPaddExternBranchCand() for each of them. Usually, this will happen in the execution function of a relaxation handler or in the
3297 * The user gains access to these branching candidates by calling the function SCIPgetExternBranchCands(). Furthermore,
3298 * SCIP provides two functions for performing the actual branching with a given solution value, namely SCIPbranchVarVal()
3299 * and SCIPcreateChild(). SCIPbranchVarVal() allows users to specify the branching point for a variable in contrast to
3302 * This paragraph contains additional information regarding how the function SCIPbranchVarVal() works. For external branching candidates,
3304 * - Given a continuous variable \f$x\f$ with solution value \f$x^*\f$, the function SCIPbranchVarVal() creates
3305 * two child nodes; one contains the bound \f$x \le x^* \f$ and the other one contains the bound \f$x \ge x^* \f$.
3307 * SCIPbranchVarVal() creates two child nodes; one contains the bound \f$x \le \lfloor x^* \rfloor\f$ and the other
3309 * - Given an integer variable \f$x\f$ with integral solution value \f$x^*\f$, the function SCIPbranchVarVal()
3310 * creates three child nodes; one contains the bound \f$x \le x^* -1\f$, one contains the bound \f$x \ge x^* +1\f$,
3313 * See the BRANCHEXECEXT callback in src/scip/branch_random.c for an example. In addition, if a proven lower bound of a
3314 * created child node is known the user may call the function SCIPupdateNodeLowerbound() in order to update the child
3321 * The BRANCHEXECPS callback is executed during node processing if no LP solution is available and at least one of the
3322 * integer variables is not yet fixed. It should split the current problem into smaller subproblems. PS stands for
3323 * pseudo solution which is the vector of all variables set to their locally best (w.r.t. the objective function)
3326 * The user gains access to the branching candidates, i.e., to the non-fixed integer variables, by calling the function
3327 * SCIPgetPseudoBranchCands(). Furthermore, SCIP provides two functions for performing the actual branching, namely
3330 * Given an integer variable \f$x\f$ with bounds \f$[l,u]\f$ and not having solved the LP, the function SCIPbranchVar()
3332 * - If both bounds are finite, then the two children will contain the domain reductions \f$x \le x^*\f$, and \f$x \ge
3333 * x^*+1\f$ with \f$x^* = \lfloor \frac{l + u}{2}\rfloor\f$. The current pseudo solution will remain feasible in one
3335 * - If only one of the bounds is finite, the variable will be fixed to that bound in one of the child nodes. In the
3337 * - If both bounds are infinite, three children will be created: \f$x \le 1\f$, \f$x \ge 1\f$, and \f$x = 0\f$.
3340 * See the BRANCHEXECPS callback in src/scip/branch_random.c for an example. In addition, if a proven lower bound of a
3341 * created child node is known, the user may call the function SCIPupdateNodeLowerbound() in order to update the child
3348 * In order to apply more general branching schemes, one should use the function SCIPcreateChild().
3349 * After having created a child node, the additional restrictions of the child node have to be added with calls to
3352 * In the function SCIPcreateChild(), the branching rule has to assign two values to the new nodes: a node selection
3353 * priority for each node and an estimate for the objective value of the best feasible solution contained in the subtree
3354 * after applying the branching. If the function SCIPbranchVar() is used, these values are automatically assigned. For
3355 * variable based branching schemes, one might use the functions SCIPcalcNodeselPriority() and the function
3358 * In some cases, the branching rule can tighten the current subproblem instead of producing a branching. For example,
3359 * strong branching might have proven that rounding up a variable would lead to an infeasible LP relaxation and thus,
3360 * the variable must be rounded down. Therefore, the BRANCHEXECLP, BRANCHEXECPS and BRANCHEXECREL callbacks may also
3365 * - adding an additional constraint (e.g. a conflict constraint) (result SCIP_CONSADDED; note that this action
3367 * - reducing the domain of a variable such that the current LP solution becomes infeasible (result SCIP_REDUCEDDOM)
3371 * Only the BRANCHEXECLP callback has the possibility to add a cutting plane to the LP (result SCIP_SEPARATED).
3375 * If you are using branching rule data, you have to implement this function in order to free the branching rule data.
3380 * If you have allocated memory for fields in your branching rule data, remember to free this memory
3402 * In this function, the branching rule should free all resources that have been allocated for the solving process in
3407 * The BRANCHINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
3418/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
3423 * For more information on how SCIP manages cuts, see "What is the difference between a sepastore and the cutpool?" in the
3426 * A complete list of all cut selectors contained in this release can be found \ref CUTSELECTORS "here".
3430 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjCutsel wrapper
3431 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_CUTSEL... callbacks.
3433 * Additional documentation for the callbacks of a cut selector can be found in the file type_cutsel.h.
3436 * -# Copy the template files src/scip/cutsel_xyz.c and src/scip/cutsel_xyz.h into files named "cutsel_mycutselector.c"
3439 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
3440 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
3441 * -# Use SCIPincludeCutselMycutselector() in order to include the cut selector into your SCIP instance,
3442 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
3443 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
3444 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mycutselector".
3449 * -# Implement the additional callbacks (see \ref CUTSEL_ADDITIONALCALLBACKS). This is optional.
3454 * At the top of the new file "cutsel_mycutselector.c" you can find the cut selector properties.
3456 * In the C++ wrapper class, you have to provide the cut selector properties by calling the constructor
3462 * Additionally, if you are searching for a cut selector with SCIPfindCutsel(), this name is looked up.
3469 * After all cuts have been collected in the sepastore, SCIP asks the cut selectors to select cuts.
3470 * The cut selectors are sorted by priority (highest goes first) and are called, in this order, until the first one
3473 * Note that this property only defines the default value of the priority. The user may change this value arbitrarily by
3474 * adjusting the corresponding parameter setting. Whenever, even during solving, the priority of a cut selector is
3480 * Below the header "Data structures" you can find a struct which is called "struct SCIP_CutselData".
3481 * In this data structure, you can store the data of your cut selector. For example, you should store the adjustable
3483 * If you are using C++, you can add cut selector data as usual as object variables to your class.
3490 * At the bottom of "cutsel_mycutselector.c", you can find the interface function SCIPincludeCutselMycutselector(),
3492 * SCIPincludeCutselMycutselector() is called by the user, if they want to include the cut selector, i.e., if they want
3496 * It is responsible for notifying SCIP of the presence of the cut selector. For this, you can either call
3498 * or SCIPincludeCutselBasic(). In the latter variant, \ref CUTSEL_ADDITIONALCALLBACKS "additional callbacks"
3499 * must be added via setter functions as, e.g., SCIPsetCutselCopy(). We recommend this latter variant because
3500 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
3501 * variant must be manually adjusted with every SCIP release containing new callbacks for cut selectors in order to compile.
3504 * If you are using cut selector data, you have to allocate the memory for the data at this point.
3511 * You may also add user parameters for your cut selector, see the function SCIPincludeCutselHybrid() in
3517 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
3519 * They are passed together with the cut selector itself to SCIP using SCIPincludeCutsel() or SCIPincludeCutselBasic(),
3523 * This function has to be implemented for every cut selector; the other callbacks are optional.
3524 * It implements the single contribution every selector has to provide: Selecting cuts to be added to the relaxation.
3525 * In the C++ wrapper class scip::ObjCutsel, the scip_select() function is a virtual abstract member function.
3526 * You have to implement it in order to be able to construct an object of your cut selector class.
3531 * The callback receives the arrays of cuts to select from. This array must be re-sorted and the first nselectedcuts from
3533 * In addition to the aforementioned cuts, the list of forced cuts is also given as an argument. This array can be used
3534 * to help with the selection algorithm. Note, however, that this array should not be tampered with.
3540 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
3541 * implemented for most applications. They can be used, for example, to initialize and free private data.
3542 * Additional callbacks can either be passed directly with SCIPincludeCutsel() to SCIP or via specific
3543 * <b>setter functions</b> after a call of SCIPincludeCutselBasic(), see also @ref CUTSEL_INTERFACE.
3547 * If you are using cut selector data, you have to implement this function in order to free the cut selector data.
3552 * If you have allocated memory for fields in your cut selector data, remember to free this memory
3564 * The CUTSELCOPY callback is executed when a SCIP instance is copied, e.g., to solve a sub-SCIP. By defining this
3565 * callback as <code>NULL</code> the user disables the execution of the specified cut selector for all copied SCIP
3571 * In this function, the cut selector should free all resources that have been allocated for the solving process
3576 * The CUTSELINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
3586/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
3590 * Node selectors are used to decide which of the leaves in the current branching tree is selected as next subproblem
3591 * to be processed. The ordering relation of the tree's leaves for storing them in the leaf priority queue is also
3594 * A complete list of all node selectors contained in this release can be found \ref NODESELECTORS "here".
3598 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjNodesel wrapper
3599 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_NODESEL... callbacks.
3601 * Additional documentation for the callbacks of a node selector can be found in the file type_nodesel.h.
3604 * -# Copy the template files src/scip/nodesel_xyz.c and src/scip/nodesel_xyz.h into files named "nodesel_mynodeselector.c"
3607 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
3608 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
3609 * -# Use SCIPincludeNodeselMynodeselector() in order to include the node selector into your SCIP instance,
3610 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
3611 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
3612 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mynodeselector".
3617 * -# Implement the additional callbacks (see \ref NODESEL_ADDITIONALCALLBACKS). This is optional.
3622 * At the top of the new file "nodesel_mynodeselector.c" you can find the node selector properties.
3624 * In the C++ wrapper class, you have to provide the node selector properties by calling the constructor
3630 * Additionally, if you are searching for a node selector with SCIPfindNodesel(), this name is looked up.
3637 * The first step of each iteration of the main solving loop is the selection of the next subproblem to be processed.
3638 * The node selector of highest priority (the active node selector) is called to do this selection.
3639 * In particular, if you implemented your own node selector plugin which you want to be applied, you should choose a priority
3641 * Note that SCIP has two different operation modes: the standard mode and the memory saving mode. If the memory
3642 * limit - given as a parameter by the user - is almost reached, SCIP switches from the standard mode to the memory saving
3643 * mode in which different priorities for the node selectors are applied. NODESEL_STDPRIORITY is the priority of the
3646 * Note that this property only defines the default value of the priority. The user may change this value arbitrarily by
3649 * \par NODESEL_MEMSAVEPRIORITY: the default priority of the node selector in the memory saving mode.
3650 * The priority NODESEL_MEMSAVEPRIORITY of the node selector has the same meaning as the priority NODESEL_STDPRIORITY, but
3652 * Usually, you want the best performing node selector, for example best estimate search, to have maximal
3653 * standard priority, while you want a node selector which tends to keep the growth of the search tree limited, for example
3656 * Note that this property only defines the default value of the priority. The user may change this value arbitrarily by
3662 * Below the header "Data structures" you can find a struct which is called "struct SCIP_NodeselData".
3663 * In this data structure, you can store the data of your node selector. For example, you should store the adjustable
3665 * If you are using C++, you can add node selector data as usual as object variables to your class.
3672 * At the bottom of "nodesel_mynodeselector.c", you can find the interface function SCIPincludeNodeselMynodeselector(),
3674 * SCIPincludeNodeselMynodeselector() is called by the user, if (s)he wants to include the node selector,
3678 * It is responsible for notifying SCIP of the presence of the node selector. For this, you can either call
3680 * or SCIPincludeNodeselBasic() since SCIP version 3.0. In the latter variant, \ref NODESEL_ADDITIONALCALLBACKS "additional callbacks"
3681 * must be added via setter functions as, e.g., SCIPsetNodeselCopy(). We recommend this latter variant because
3682 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
3683 * variant must be manually adjusted with every SCIP release containing new callbacks for node selectors in order to compile.
3686 * If you are using node selector data, you have to allocate the memory for the data at this point.
3693 * You may also add user parameters for your node selector, see the function SCIPincludeNodeselRestartdfs() in
3699 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
3701 * They are passed together with the node selector itself to SCIP using SCIPincludeNodesel() or SCIPincludeNodeselBasic(),
3704 * Node selector plugins have two fundamental callbacks, namely the NODESELSELECT function and the NODESELCOMP function.
3705 * These functions have to be implemented for every node selector; the other callbacks are optional.
3706 * They implement the two requirements every node selector has to fulfill: Selecting a node from the queue to be processed
3707 * next and, given two nodes, deciding which of both is favored by the node selector's selection rule. The first
3708 * task is implemented in the NODESELSELECT callback, the second one in the NODESELCOMP callback.
3709 * In the C++ wrapper class scip::ObjNodesel, the scip_select() function and the scip_comp() function (which correspond to the
3710 * NODESELSELECT callback and the NODESELCOMP callback, respectively) are virtual abstract member functions.
3711 * You have to implement them in order to be able to construct an object of your node selector class.
3717 * The NODESELSELECT callback is the first function called in each iteration in the main solving loop. It should decide
3718 * which of the leaves in the current branching tree is selected as the next subproblem to be processed.
3719 * It can arbitrarily decide between all leaves stored in the tree, but for performance reasons,
3720 * the current node's children and siblings are often treated different from the remaining leaves.
3721 * This is mainly due to the warm start capabilities of the simplex algorithm and the expectation that the bases of
3724 * have a large impact on the solver's performance, because it influences the finding of feasible solutions and the
3727 * Besides the ranking of the node selector, every node gets assigned a node selection priority by the branching rule
3728 * that created the node. See the \ref BRANCHEXECLP and \ref BRANCHEXECPS callbacks of the branching rules for details.
3729 * For example, the node where the branching went in the same way as the deviation from the branching variable's
3730 * root solution could be assigned a higher priority than the node where the branching went in the opposite direction.
3733 * - SCIPgetPrioChild() returns the child of the current node with the largest node selection priority, as assigned by the
3735 * If no child is available (for example, because the current node was pruned), a NULL pointer is returned.
3736 * - SCIPgetBestChild() returns the best child of the current node with respect to the node selector's ordering relation as
3737 * defined by the \ref NODESELCOMP callback. If no child is available, a NULL pointer is returned.
3738 * - SCIPgetPrioSibling() returns the sibling of the current node with the largest node selection priority.
3739 * If no sibling is available (for example, because all siblings of the current node have already been processed), a NULL
3741 * Note that in binary branching every node has at most one sibling, but since SCIP supports arbitrary branching rules,
3743 * - SCIPgetBestSibling() returns the best sibling of the current node with respect to the node selector's ordering relation
3744 * as defined by the \ref NODESELCOMP callback. If no sibling is available, a NULL pointer is returned.
3745 * - SCIPgetBestNode() returns the best leaf from the tree (children, siblings, or other leaves) with respect to the node
3746 * selector's ordering relation as defined by the \ref NODESELCOMP callback. If no open leaf exists, a NULL pointer is
3747 * returned. In this case, the optimization is finished, and the node selector should return a NULL pointer as 'selnode'.
3748 * - SCIPgetBestboundNode() returns a leaf from the tree (children, siblings, or other leaves) with the smallest lower (dual)
3749 * objective bound. If the queue is empty, a NULL pointer is returned. In this case, the optimization is finished, and the
3755 * The NODESELCOMP callback is called to compare two leaves of the current branching tree (say node 1 and node 2)
3765 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
3766 * implemented for most applications, they can be used, for example, to initialize and free private data.
3767 * Additional callbacks can either be passed directly with SCIPincludeNodesel() to SCIP or via specific
3768 * <b>setter functions</b> after a call of SCIPincludeNodeselBasic(), see also @ref NODESEL_INTERFACE.
3772 * If you are using node selector data, you have to implement this function in order to free the node selector data.
3777 * If you have allocated memory for fields in your node selector data, remember to free this memory
3799 * In this function, the node selector should free all resources that have been allocated for the solving process
3804 * The NODESELINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
3815/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
3819 * Feasible solutions can be found in two different ways during the traversal of the branch-and-bound tree. On one
3820 * hand, the solution of a node's relaxation may be feasible with respect to the constraints (including the integrality).
3823 * A complete list of all primal heuristics contained in this release can be found \ref PRIMALHEURISTICS "here".
3825 * Diving heuristics are primal heuristics that explore an auxiliary search tree in a depth-first manner. Since SCIP
3826 * version 3.2, it is easy to integrate further diving heuristics by using a special controller for the scoring,
3830 * Take the simple and fast LP rounding heuristic (src/scip/heur_simplerounding.c) as an example.
3831 * The idea of simple rounding is to iterate over all fractional variables of an LP solution and round them down,
3832 * if the variables appears only with nonnegative coefficients in the system Ax <= b and round them up if
3834 * If one of both conditions applies for each of the fractional variables, this will give a feasible solution.
3835 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjHeur wrapper
3836 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_HEUR... callbacks.
3838 * Additional documentation for the callbacks of a primal heuristic can be found in the file type_heur.h.
3841 * -# Copy the template files src/scip/heur_xyz.c and src/scip/heur_xyz.h into files named "heur_myheuristic.c"
3844 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
3845 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
3846 * -# Use `SCIPincludeHeurMyheuristic()` in order to include the heuristic into your SCIP instance,
3847 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
3848 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
3849 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "myheuristic".
3859 * At the top of the new file "heur_myheuristic.c" you can find the primal heuristic properties.
3861 * In the C++ wrapper class, you have to provide the primal heuristic properties by calling the constructor
3863 * Of course, all of them are of relevant, but the most important ones for controlling the performance
3869 * Additionally, if you are searching for a primal heuristic with SCIPfindHeur(), this name is looked up.
3873 * This string is printed as a description of the primal heuristic in the interactive shell when you call "display heuristics".
3876 * In the interactive shell, this character is printed in the first column of a status information row, if the primal
3877 * heuristic found the feasible solution belonging to the primal bound. Note that a star '*' stands for an integral
3879 * It is recommended to select a lower or upper case letter as display character. The default primal heuristics of
3880 * SCIP use characters that describe the class to which the heuristic belongs. As an example all LP rounding heuristics
3886 * At each of the different entry points of the primal heuristics during the solving process (see HEUR_TIMING), they are
3889 * The priority of a primal heuristic should be set according to the complexity of the heuristic and the likelihood to find
3890 * feasible solutions: primal heuristics that provide fast algorithms that often succeed in finding a feasible solution should have
3891 * a high priority (like simple rounding). In addition, the interaction between different types of primal heuristics should be taken into account.
3892 * For example, improvement heuristics, which try to generate improved solutions by inspecting one or more of the feasible
3893 * solutions that have already been found, should have a low priority (like Crossover which by default needs at least 3 feasible solutions).
3896 * The frequency together with the frequency offset (see HEUR_FREQOFS) defines the depth levels at which the execution
3897 * function of the primal heuristic \ref HEUREXEC is called. For example, a frequency of 7 together with a frequency offset
3898 * of 5 means, that the \ref HEUREXEC callback is executed for subproblems that are in depth 5, 12, 19, ... of the branching tree. A
3899 * frequency of 0 together with a frequency offset of 3 means, that the execution function is only called at those nodes that are in
3902 * the heuristic is only called at the root node and a frequency of -1 which disables the heuristic.
3904 * The frequency can be adjusted by the user. This property of the primal heuristic only defines the default value of the
3905 * frequency. If you want to have a more flexible control of when to execute the primal heuristic, you have to assign
3906 * a frequency of 1 and implement a check at the beginning of your execution function whether you really want to search for feasible
3907 * solutions or not. If you do not want to execute the function, set the result code to SCIP_DIDNOTRUN.
3910 * The frequency offset defines the depth of the branching tree at which the primal heuristic is executed for the first
3911 * time. For example, a frequency of 7 (see HEUR_FREQ) together with a frequency offset of 10 means, that the
3912 * callback is executed for subproblems that are in depth 10, 17, 24, ... of the branching tree. In particular, assigning
3913 * different offset values to heuristics of the same type, like diving heuristics, can be useful for evenly spreading the
3915 * Note that if the frequency is equal to 1, the heuristic is applied for all nodes with depth level larger or equal to
3919 * This parameter denotes the maximal depth level in the branching tree up to which the execution function of the primal
3923 * Primal heuristics have different entry points during the solving process and the execution timing parameter defines the
3930 * - after the processing of a node <em>with solved LP</em> was finished (SCIP_HEURTIMING_AFTERLPNODE)
3931 * - after the processing of a node <em>without solved LP</em> was finished (SCIP_HEURTIMING_AFTERPSEUDONODE)
3932 * - after the processing of the last node in the current plunge was finished, <em>and only if the LP was solved for
3934 * - after the processing of the last node in the current plunge was finished, <em>and only if the LP was not solved
3938 * The flags listed above can be combined to call the heuristic at multiple times by concatenating them with a bitwise OR.
3940 * - after the processing of a node was finished (SCIP_HEURTIMING_AFTERNODE; combines SCIP_HEURTIMING_AFTERLPNODE and
3942 * - after the processing of the last node in the current plunge was finished (SCIP_HEURTIMING_AFTERPLUNGE; combines
3945 * Calling a primal heuristic "before the processing of the node starts" is particularly useful for heuristics
3946 * that do not need to access the LP solution of the current node. If such a heuristic finds a feasible solution, the
3947 * leaves of the branching tree exceeding the new primal bound are pruned. It may happen that even the current node can
3948 * be cut off without solving the LP relaxation. Combinatorial heuristics, like the farthest insert heuristic for the TSP
3951 * Very fast primal heuristics that require an LP solution can also be called "after each LP solve during the
3956 * (e.g. expensive rounding heuristics like RENS), or even only after a full plunge was finished (e.g., diving heuristics).
3959 * Some heuristics and separators solve MIPs or SAT problems using a secondary SCIP instance. Examples are
3960 * Large Neighborhood Search heuristics such as RINS and Local Branching or the CGMIP separator. To avoid recursion,
3961 * these plugins usually deactivate all other plugins that solve MIPs. If a heuristic uses a secondary SCIP instance,
3962 * this parameter has to be TRUE and it is recommended to call SCIPsetSubscipsOff() for the secondary SCIP instance.
3964 * Computational experiments indicate that for the overall performance of a MIP solver, it is important to evenly
3965 * spread the application of the heuristics across the branch-and-bound tree. Thus, the assignment of the parameters
3968 * Note that all diving heuristics in the SCIP distribution (see, e.g., src/scip/heur_guideddiving.c) check whether other diving
3969 * heuristics have already been called at the current node. This can be done by comparing SCIPgetLastDivenode(scip) and
3970 * SCIPgetNNodes(scip). If the two are equal, and if the current node is not the root node (SCIPgetDepth(scip) > 0), diving
3971 * heuristics should be delayed by returning the result code 'SCIP_DELAYED'. This is an additional contribution to the goal of
3977 * Below the header "Data structures" you can find a struct which is called "struct SCIP_HeurData".
3978 * In this data structure, you can store the data of your primal heuristic. For example, you should store the adjustable
3980 * If you are using C++, you can add primal heuristic data as usual as object variables to your class.
3987 * At the bottom of "heur_myheuristic.c", you can find the interface function SCIPincludeHeurMyheuristic(),
3993 * It is responsible for notifying SCIP of the presence of the heuristic. For this, you can either call
3995 * or SCIPincludeHeurBasic() since SCIP version 3.0. In the latter variant, \ref HEUR_ADDITIONALCALLBACKS "additional callbacks"
3996 * must be added via setter functions as, e.g., SCIPsetHeurCopy(). We recommend this latter variant because
3997 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
3998 * variant must be manually adjusted with every SCIP release containing new callbacks for heuristics in order to compile.
4000 * If you are using primal heuristic data, you have to allocate the memory for the data at this point.
4007 * You may also add user parameters for your primal heuristic, see the function SCIPincludeHeurFeaspump() in
4013 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
4015 * They are passed together with the primal heuristic itself to SCIP using SCIPincludeHeur() or SCIPincludeHeurBasic(),
4020 * This function has to be implemented for every primal heuristic; the other callbacks are optional.
4021 * In the C++ wrapper class scip::ObjHeur, the scip_exec() method (which corresponds to the HEUREXEC callback) is a virtual
4022 * abstract member function. You have to implement it in order to be able to construct an object of your primal heuristic
4029 * The HEUREXEC callback is called at different positions during the node processing loop, see HEUR_TIMING. It should
4030 * search for feasible solutions and add them to the solution pool. For creating a new feasible solution, the
4031 * functions SCIPcreateSol() and SCIPsetSolVal() can be used. Afterwards, the solution can be added to the storage by
4034 * The HEUREXEC callback gets a SCIP pointer, a pointer to the heuristic itself, the current point in the
4040 * - stating that the primal heuristic searched, but did not find a feasible solution (result SCIP_DIDNOTFIND)
4042 * - stating that the primal heuristic was skipped, but should be called again (result SCIP_DELAYED).
4047 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
4048 * implemented for most applications, they can be used, for example, to initialize and free private data.
4049 * Additional callbacks can either be passed directly with SCIPincludeHeur() to SCIP or via specific
4050 * <b>setter functions</b> after a call of SCIPincludeHeurBasic(), see also @ref HEUR_INTERFACE.
4054 * If you are using primal heuristic data, you have to implement this function in order to free the primal heuristic data.
4059 * If you have allocated memory for fields in your primal heuristic data, remember to free this memory
4081 * In this function, the primal heuristic should free all resources that have been allocated for the solving process in
4086 * The HEURINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
4087 * begin. The primal heuristic may use this call to initialize its branch-and-bound specific data.
4091 * The HEUREXITSOL callback is executed before the branch-and-bound process is freed. The primal heuristic should use this
4095/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4099 * IIS finders are used to generate an (I)IS ((irreducible) infeasible subsystem) for an infeasible instance.
4101 * A complete list of all iis finders contained in this release can be found \ref IISFINDERS "here".
4105 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjIISfinder wrapper
4106 * base class and implement the `scip_...()` virtual methods instead of the `SCIP_DECL_IISFINDER...` callbacks.
4108 * Additional documentation for the callbacks of an iis finder can be found in the file type_iisfinder.h.
4111 * -# Copy the template files `src/scip/iisfinder_xyz.c` and `src/scip/iisfinder_xyz.h` into files named `iisfinder_myiisfinder.c`
4114 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
4115 * If you are adding a new default plugin for SCIP, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
4116 * -# Use `SCIPincludeIIsfinderMyiisfinder()` in order to include the iis finder into your SCIP instance,
4117 * e.g., in the main file of your project (see, e.g., `src/cmain.c` in the Binpacking example). \n
4118 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
4119 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "myiisfinder".
4124 * -# Implement the additional callbacks (see \ref IISFINDER_ADDITIONALCALLBACKS). This is optional.
4131 * In the C++ wrapper class, you have to provide the iis finder properties by calling the constructor
4137 * Additionally, if you are searching for an iis finder with SCIPfindIISfinder(), this name is looked up.
4145 * The iis finders are then called in this order (highest goes first), until depending on the users settings,
4146 * one succeeds in finding an infeasible subsystem, an irreducible infeasible subsystem is found,
4149 * Note that this property only defines the default value of the priority. The user may change this value arbitrarily by
4150 * adjusting the corresponding parameter setting. Whenever, even during solving, the priority of an iis finder is
4151 * changed, then when a call is made to generate an IIS, the iis finders are resorted by the new priorities.
4156 * Below the header "Data structures" you can find a struct which is called `struct SCIP_IISfinderData`.
4157 * In this data structure, you can store the data of your iis finder. For example, you should store the adjustable
4159 * If you are using C++, you can add iis finder data as usual as object variables to your class.
4166 * At the bottom of `iisfinder_myiisfinder.c`, you can find the interface function `SCIPincludeIISfinderMyiisfinder()`,
4168 * `SCIPincludeIISfinderMyiisfinder()` is called by the users, if they want to include the iis finder, i.e., if they want
4172 * It is responsible for notifying SCIP of the presence of the iis finder. For this, you can either call
4174 * or SCIPincludeIISfinderBasic(). In the latter variant, \ref IISFINDER_ADDITIONALCALLBACKS "additional callbacks"
4175 * must be added via setter functions as, e.g., SCIPsetIISfinderCopy(). We recommend this latter variant because
4176 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
4177 * variant must be manually adjusted with every SCIP release containing new callbacks for iis finders in order to compile.
4180 * If you are using iis finder data, you have to allocate the memory for the data at this point.
4187 * You may also add user parameters for your iis finder, see the function SCIPincludeIISfinderGreedy() in
4193 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
4195 * They are passed together with the iis finder itself to SCIP using SCIPincludeIISfinder() or SCIPincludeIISfinderBasic(),
4200 * It implements the single contribution every iis finder has to provide: Generating an (I)IS from an infeasible instance.
4201 * In the C++ wrapper class scip::ObjIISfinder, the scip_exec() method is a virtual abstract member function.
4202 * You have to implement it in order to be able to construct an object of your iis finder class.
4207 * The callback receives the IIS object, which contains the infeasible subscip that should be reduced in size,
4209 * The contained subscip should be transformed such that it remains infeasible and decreases in size,
4210 * and information about the current state of the subscip, e.g., is it still infeasible, should be recorded.
4216 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
4217 * implemented for most applications. They can be used, for example, to initialize and free private data.
4218 * Additional callbacks can either be passed directly with SCIPincludeIISfinder() to SCIP or via specific
4219 * <b>setter functions</b> after a call of SCIPincludeIISfinderBasic(), see also @ref IISFINDER_INTERFACE.
4223 * If you are using iis finder data, you have to implement this function in order to free the iis finder data.
4228 * If you have allocated memory for fields in your iis finder data, remember to free this memory
4235 * The IISFINDERCOPY callback is executed when a SCIP instance is copied, e.g., to solve a sub-SCIP. By defining this
4236 * callback as `NULL` the user disables the execution of the specified iis finder for all copied SCIP
4240/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4244 * Expression handlers define basic expression types and provide additional functionality to work with expressions,
4246 * A complete list of all expression handlers contained in this release can be found \ref EXPRHDLRS "here".
4247 * In addition to expression handlers, higher level nonlinear structures are handled by nonlinear handlers, see \ref NLHDLR.
4250 * -# Copy the template files `src/scip/expr_xyz.c` and `src/scip/expr_xyz.h` into files `expr_myfunc.c` and `expr_myfunc.h`, respectively. \n
4251 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
4252 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
4253 * -# Use `SCIPincludeExprhdlrMyfunc()` in order to include the expression handler into your SCIP instance,
4255 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
4258 * -# Define the expression handler data and expression data (see \ref EXPRHDLR_DATA). This is optional.
4261 * -# Implement the additional callbacks (see \ref EXPRHDLR_ADDITIONALCALLBACKS), where necessary.
4263 * Additional documentation for the callbacks of an expression handler, in particular for the input parameters,
4266 * For a complete implementation of an expression handler, take the one for exponential expressions (src/scip/expr_exp.c) as an example.
4268 * It is very easy to transfer the C explanation to C++; whenever a function should be implemented using the
4269 * SCIP_DECL_EXPRHDLR... notion, reimplement the corresponding virtual member function of the abstract scip::ObjExprhdlr
4276 * In the C++ wrapper class, you have to provide the expression handler properties by calling the constructor
4282 * Additionally, if you or a parsing routine is searching for an expression handler with SCIPfindExprhdlr(), this name is looked up.
4289 * Precedence of the expression operation relative to other expressions when printing the expression.
4293 * Below the header "Data structures" you can find structs called `struct SCIP_ExprhdlrData` and `struct SCIP_ExprData`.
4295 * For example, you should store the adjustable parameters of the expression handler in this data structure.
4299 * Defining expression handler data and expression data is optional. You can leave these structs empty.
4305 * At the bottom of `expr_myfunc.c`, you can find the interface function `SCIPincludeExprhdlrMyfunc()`,
4307 * `SCIPincludeExprhdlrMyfunc()` is called by the user, if (s)he wants to include the expression handler,
4312 * The function only expects the properties and fundamental callbacks of the expression handler as arguments.
4313 * \ref EXPRHDLR_ADDITIONALCALLBACKS "Additional callbacks" must be added via setter functions as, e.g., SCIPexprhdlrSetCopyFreeHdlr().
4315 * If you are using expression handler data, you have to allocate the memory for the data at this point.
4323 * You may also add user parameters for your expression handler, see \ref PARAM for how to add user parameters.
4331 * This function is called by the user, if (s)he wants to create an expression that is handled by this expression handler.
4332 * Typically, the creation function takes the operands of the expression (the children) as arguments.
4333 * `SCIPcreateExprMyfunc()` may further be extended to take parameters of an expression into account.
4336 * In the implementation of `SCIPcreateExprMyfunc()`, the expression data shall be allocated and initialized, if the expression has data
4339 * This function takes the expression handler, expression data, children, and ownercreate callback as arguments.
4342 * The `ownercreate` and `ownercreatedata` that are passed to `SCIPcreateExprMyfunc()` need to be passed on to SCIP.
4343 * The owner of the expression that is created uses these arguments to store additional data in an expression.
4345 * However, if the \ref EXPRPARSE callback is implemented, then `SCIPcreateExprMyfunc()` may need to be called with a non-NULL value
4347 * This will be the case if, for example, the constraint handler for nonlinear constraint parses an expression.
4348 * The constraint handler will then own the expression and needs to store some data in the expression.
4356 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
4358 * They are passed to SCIP when the expression handler is created and included in SCIP via SCIPincludeExprhdlr(),
4360 * In the C++ wrapper class scip::ObjExprhdlr, the fundamental callbacks are virtual abstract member functions.
4361 * You have to implement them in order to be able to construct an object of your expression handler class.
4363 * Expression handlers have one fundamental callback, @ref EXPREVAL, that needs to be implemented.
4364 * However, expression handlers with stateful expressions (expressions that have data) need to implement also the
4367 * Additional documentation for the callbacks, in particular relating to their input parameters,
4372 * The expression evaluation callback defines the mathematical operation that the expression handler represents.
4373 * Its purpose is to evaluate an expression by taking the values of its children (operands) into account.
4375 * The children of the expression can be retrieved via SCIPexprGetChildren() and SCIPexprGetNChildren().
4376 * The value (a `SCIP_Real`) for each child can be retrieved via function SCIPexprGetEvalValue().
4377 * The value of the expression should be stored in the argument `val` that is passed to the callback.
4381 * When an expression cannot be evaluated w.r.t. the values of its children, such a domain error must be signaled
4383 * SCIP then aborts evaluation. It is thus not necessary to check in the evaluation callback whether any child
4385 * For example, the evaluation in the expression handler for logarithm expressions is doing the following:
4389 * It is used by the expression handler for variables to retrieve the value of a variable expression.
4394 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
4395 * implemented for most applications; they can be used, for example, to initialize and free private data.
4397 * <b>setter functions</b> after a call of SCIPincludeExprhdlr(), see also @ref EXPRHDLR_INCLUDE.
4404 * By not implementing this callback, the expression handler will not be available in copied SCIP instances.
4405 * If a nonlinear constraint uses expressions of this type, it will not be possible to copy them.
4410 * If you are using expression handler data (see \ref EXPRHDLR_DATA and \ref EXPRHDLR_INCLUDE), you have to implement this function
4436 * when the expression is visited the first time, before each child of the expression is visited,
4437 * after each child of the expression has been visited, and when the iterator leaves the expression
4440 * The given precedence of the parent expression can be used to decide whether parenthesis need to be printed.
4442 * For example, the pow expression prints `(f(x))^p` where `f(x)` is a print of the child of the pow expression and `p` is the exponent:
4445 * The pow expression handler does not yet take expression precedence into account to decide whether the parenthesis around `f(x)` can be omitted.
4449 * If this callback is not implemented, the expression is printed as `<hdlrname>(<child1>, <child2>, ...)`.
4453 * This callback is called when an expression is parsed from a string and an operator with the name of the expression handler is found.
4454 * The given string points to the beginning of the arguments of the expression, that is, the beginning of "..." in the string `myfunc(...)`.
4455 * The callback shall interpret "..." and create an expression, probably via `SCIPcreateExprMyfunc()`, and return this created expression
4457 * When creating an expression, the given `ownercreate` and `ownercreatedata` shall be passed on.
4459 * The string "..." likely contains one or several other expressions that will be the children of the `myfunc` expression.
4462 * For an expression that takes only one argument and has no parameters, the parsing routine is straightforward.
4471 * For instance, `.cip` files with nonlinear constraints that use this expression cannot be read.
4476 * It is important to note that the callback is given a desired curvature (convex, concave, or both (=linear))
4477 * and the callback is required to return whether the given expression has the desired curvature.
4478 * In addition, it can state conditions on the curvature of the children under which the desired curvature
4480 * SCIPevalExprActivity() and SCIPexprGetActivity() shall be used to evaluate and get bounds on a child expression.
4489 * This callback is called when an expression is checked for its monotonicity with respect to a given child.
4490 * It is given the index of the child and shall return whether the expression is monotonically increasing or decreasing with respect to this child,
4498 * If this callback is not implemented, the expression is assumed to be not monotone in any child.
4504 * An implementation usually uses SCIPexprGetIntegrality() or SCIPexprIsIntegral() to evaluate the integrality of a
4505 * feasible child expression. The function SCIPexprGetIntegrality() distinguishes the integrality types none, weak, and strong. Weak
4508 * For example, a sum expression is returned to be integral if all coefficients and all children are integral:
4516 * The hash is used to quickly identify expressions that may be equal (or better: to identify expressions that cannot be pairwise equal).
4519 * To achieve this, the hashing algorithm shall use the expression type, expression data, and hash of children as input.
4522 * For example, for the sum expression, the coefficients and the hashes of all children are taken into account:
4527 * If this callback is not implemented, a hash is computed from the expression handler name and the hashes of all children.
4531 * This callback is called when two expressions (expr1 and expr2) that are handled by the expression handlers need to be compared.
4543 * If this callback is not implemented, a comparison is done based on the children of expr1 and expr2 only.
4548 * This callback is called when the gradient or Hessian of a function that is represented by an expression is computed.
4550 * The function shall compute the partial derivative of the expression w.r.t. a child with specified childidx.
4556 * See also \ref SCIP_EXPR_DIFF "Differentiation functions in scip_expr.h" for more details on automatic differentiation of expressions.
4561 * If this callback is not implemented, gradients and Hessian of functions that involve this expression cannot be computed.
4562 * This can be hurtful for performance because linear relaxation routines that rely on gradient evaluation (e.g., nlhdlr_convex) cannot be used.
4566 * This callback is called when the Hessian of a function that is represented by an expression is computed.
4569 * The function shall evaluate the directional derivative of the expression when interpreted as an operator
4575 * where \f$ u \f$ is the direction (given to the callback) and \f$ D_u c_i \f$ is the directional derivative of the i-th child,
4579 * See also \ref SCIP_EXPR_DIFF "Differentiation functions in scip_expr.h" for more details on automatic differentiation of expressions.
4581 * For a product, \f$f(x) = c\prod_i x_i\f$, the directional derivative is \f$c\sum_j \prod_{i\neq j} x_i x^{\text{dot}}_j\f$:
4584 * If this callback is not implemented, routines (in particular primal heuristics) that rely on solving NLPs cannot be used, as they currently rely on using forward differentiation for gradient computations.
4588 * This callback is called when the Hessian of a function that is represented by an expression is computed.
4590 * The function computes the total derivative, w.r.t. its children, of the partial derivative of expr w.r.t. childidx.
4593 * The expression should be interpreted as an operator \f$ f(c_1, \ldots, c_n) \f$, where \f$ c_1, \ldots, c_n \f$ are the children,
4598 * where \f$ u \f$ is the direction (given to the callback) and \f$ D_u c_i \f$ is the directional derivative of the i-th child,
4601 * Thus, if \f$ n = 1 \f$ (i.e., the expression represents a univariate operator), the function should return
4606 * See also \ref SCIP_EXPR_DIFF "Differentiation functions in scip_expr.h" for more details on automatic differentiation of expressions.
4609 * \f$c\partial_k \sum_j \prod_{i \neq j} x_i x^{\text{dot}}_j = c\sum_{j \neq k} \prod_{i \neq j, k} x_i x^{\text{dot}}_j\f$:
4613 * In a future version, not implementing this callback would mean that Hessians are not available for NLP solvers, in which case they may have to work with approximations.
4618 * It shall compute an (as tight as possible) overestimate on the range that the expression values take w.r.t. bounds (given as \ref SCIP_INTERVAL) for the children.
4625 * If this callback is not implemented, the performance of domain propagation for nonlinear constraints and other routines that rely on bounds of expressions will be impacted severely.
4631 * The estimator shall be as tight as possible at a given point and must be valid w.r.t. given (local) bounds.
4632 * If the value of the estimator in the reference point is smaller (larger) than a given targetvalue
4636 * The callback shall also indicate whether the estimator is also valid w.r.t. given global bounds and for which
4642 * If this callback is not implemented, updating the linear relaxation for nonlinear constraints that use this expression will not be possible, which has a severe impact on performance.
4648 * A usecase for this callback is the construction of an initial linear relaxation of nonlinear constraints.
4650 * For the absolute-value expression, the following initial under- and overestimators are computed:
4653 * If this callback is not implemented, the initial linear relaxation for nonlinear constraints may be less tight.
4654 * This can have a minor effect on performance, as long as \ref EXPRESTIMATE has been implemented and the linear relaxation
4662 * If no simplification is possible, then it can return the original expression, but needs to capture it.
4663 * When creating a new expression, it shall pass on the given ownerdata creation callback and its data.
4665 * A simplification that should be implemented by every expression handler at the moment is constant-folding, i.e.,
4672 * If this callback is not implemented, reducing the problem size when variables are fixed may not be possible, which can have an impact on performance.
4677 * This callback is called when given bounds on an expression shall be propagated over the children of an expression.
4683 * for each child \f$i\f$, given bounds on f and initial intervals \f$c_i, i=1,\ldots,n,\f$, for the children.
4685 * For univariate expressions, the implementation can be rather straightforward, e.g., for absolute value:
4691 * If this callback is not implemented, the performance of domain propagation for nonlinear constraints will be impacted severely.
4694/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4698 * Nonlinear handlers define the extended formulations of nonlinear constraints and provide domain propagation and separation routines on this extended formulation.
4699 * In difference to \ref EXPRHDLR "expression handlers", they do not define a function, but instead identify a
4700 * structure in an existing expression and provide bound tightening and separation on this structure similar to \ref EXPRINTEVAL, \ref EXPRREVERSEPROP, \ref EXPRINITESTIMATES, and \ref EXPRESTIMATE.
4704 * They resemble constraint handlers in some sense, but are specific to the handling of nonlinear constraints.
4705 * We suggest to read section "New Handler for Nonlinear Constraints" in the SCIP 8.0 release report (2021)
4708 * A complete list of all nonlinear handlers contained in this release can be found \ref NLHDLRS "here".
4709 * In difference to many other plugins in SCIP, nonlinear handlers are not handled by the SCIP core but by the constraint handler for nonlinear constraints.
4712 * -# Copy the template files `src/scip/nlhdlr_xyz.c` and `src/scip/nlhdlr_xyz.h` into files `nlhdlr_mystruct.c` and `nlhdlr_mystruct.h`, respectively. \n
4713 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
4714 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
4715 * -# Use `SCIPincludeNlhdlrMystruct()` in order to include the nonlinear handler into your SCIP instance, e.g., in the main file of your project. \n
4716 If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
4719 * -# Define the nonlinear handler data and nonlinear handler expression data (see \ref NLHDLR_DATA). This is optional.
4722 * -# Implement the additional callbacks (see \ref NLHDLR_ADDITIONALCALLBACKS), where necessary.
4724 * Additional documentation for the callbacks of a nonlinear handler, in particular for the input parameters,
4729 * At the top of the new file `nlhdlr_mystruct.c`, you can find the nonlinear handler properties.
4735 * Additionally, if you are searching for a nonlinear handler with SCIPfindNlhdlrNonlinear(), this name is looked up.
4742 * This priority decides when the \ref NLHDLRDETECT callback of the nonlinear handler is called, relative to other nonlinear handlers, on an expression.
4744 * This is because the nonlinear handler "default" (having detection priority 0) will not become active on expressions that are already handled by other nonlinear handlers.
4746 * \par NLHDLR_ENFOPRIORITY: the priority of the nonlinear handler when enforcing constraints in the extended formulations.
4747 * This priority decides when the callbacks that help on domain propagation and separation are called for an expression for which the nonlinear handler detected a structure.
4753 * Below the header "Data structures" you can find structs called `struct SCIP_NlhdlrData` and `struct SCIP_NlhdlrExprData`.
4755 * For example, you should store the adjustable parameters of the nonlinear handler in this data structure.
4756 * In the second data structure, you can store data that is unique to an expression for which the nonlinear handler detected a structure.
4757 * For example, the nonlinear handler for quotients stores a representation of a detected quotient in this data structure.
4759 * Defining nonlinear handler data and nonlinear handler expression data is optional. You can leave these structs empty.
4763 * At the bottom of `nlhdlr_mystruct.c`, you can find the interface function `SCIPincludeNlhdlrXyz()`,
4765 * `SCIPincludeNlhdlrXyz()` is called by the user, if (s)he wants to include the nonlinear handler,
4770 * The function only expects the properties and fundamental callbacks of the nonlinear handler as arguments.
4771 * \ref NLHDLR_ADDITIONALCALLBACKS "Additional callbacks" must be added via setter functions as, e.g., SCIPnlhdlrSetCopyHdlr().
4773 * If you are using nonlinear handler data, you have to allocate the memory for the data at this point and initialize it.
4775 * You may also add user parameters or statistic tables for your nonlinear handler, see \ref PARAM for how to add user parameters.
4783 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
4785 * They are passed to SCIP when the nonlinear handler is created and included in SCIP via SCIPincludeNlhdlrNonlinear(),
4794 * This callback is called by the handler for nonlinear constraints when extended formulations are constructed.
4797 * The nonlinear handler shall analyze the given expression (`expr`) and decide whether it wants to contribute
4798 * in enforcing the relation between bounds or an auxiliary variable (`auxvar`) associated with this expression and
4799 * its descendants (e.g., children) via linear under- or overestimation, cut generation, and/or activity computation and propagation.
4800 * For linear under- or overestimation and cut generation, an auxiliary variable can be assumed to
4801 * be associated with the expression and auxiliary variables may be requested for descendant expressions.
4804 * - \ref SCIP_NLHDLR_METHOD_SEPABELOW : linear underestimation of `expr` or cut generation for the relation `expr` ≤ `auxvar` (denoted as "below")
4805 * - \ref SCIP_NLHDLR_METHOD_SEPAABOVE : linear overestimation of `expr` or cut generation for the relation `expr` ≥ `auxvar` (denoted as "above")
4806 * - \ref SCIP_NLHDLR_METHOD_ACTIVITY : domain propagation (i.e., constant under/overestimation) for `expr`.
4809 * - it is not necessary to have such a method, e.g., because no `auxvar` will exist for `expr`, or no one uses or sets activities of this expression,
4810 * or because analysis of the expression has shown that a relation like `expr` ≥ `auxvar` is not necessary to be satisfied,
4811 * - or there already exists a nonlinear handler that will provide this method in an "enforcement" sense, that is,
4812 * it believes that no one else could provide this method in a stronger sense. (This is mainly used by the nonlinear handler "default" to check whether
4813 * it should still reach out to the expression handler or whether it would be dominated by some nonlinear handler.)
4815 * The DETECT callback shall augment the `enforcing` bitmask by setting the enforcement methods it wants to provide in an "enforcement" sense.
4817 * Additionally, the `participating` bitmask shall be set if the nonlinear handler wants to be called on this expression at all.
4818 * Here, it shall set all methods that it wants to provide, which are those set in `enforcing`, but additionally those where it wants
4820 * This can be useful for nonlinear handlers that do not implement a complete enforcement, e.g., a handler that only contributes
4823 * A nonlinear handler will be called only for those callbacks that it mentioned in `participating`, which is
4824 * - \ref NLHDLRENFO and/or \ref NLHDLRESTIMATE will be called with `overestimate==FALSE` if \ref SCIP_NLHDLR_METHOD_SEPABELOW has been set
4825 * - \ref NLHDLRENFO and/or \ref NLHDLRESTIMATE will be called with `overestimate==TRUE` if \ref SCIP_NLHDLR_METHOD_SEPAABOVE has been set
4826 * - \ref NLHDLRINTEVAL and/or \ref NLHDLRREVERSEPROP will be called if \ref SCIP_NLHDLR_METHOD_ACTIVITY has been set
4828 * If \ref SCIP_NLHDLR_METHOD_SEPABELOW or \ref SCIP_NLHDLR_METHOD_SEPAABOVE has been set, then at least one of the
4831 * If \ref SCIP_NLHDLR_METHOD_ACTIVITY has been set, then at least one of \ref NLHDLRINTEVAL and \ref NLHDLRREVERSEPROP needs to be implemented.
4832 * If the nonlinear handler chooses not to participate, then it must not set `nlhdlrexprdata` and can leave `participating` at its
4835 * Additionally, a nonlinear handler that decides to participate in any of the enforcement methods must call
4836 * @ref SCIPregisterExprUsageNonlinear() for every subexpression that it will use and indicate whether
4839 * - it will use activity for some subexpressions when in \ref NLHDLRINTEVAL or \ref NLHDLRREVERSEPROP.
4841 * Note that auxiliary variables do not exist in subexpressions during DETECT and are not created by a call to @ref SCIPregisterExprUsageNonlinear().
4844 * For an example, see the implementation of the DETECT callback for the nonlinear handler for quotients (src/scip/nlhdlr_quotient.c).
4848 * This callback is called by the constraint handler for nonlinear constraints when the violation of constraints in the extended formulation
4850 * During constraint enforcement, this violation value is used to decide whether estimation and separation callbacks should be called.
4852 * The function shall evaluate the expression w.r.t. the auxiliary variables that were introduced by the nonlinear handler (if any).
4860 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
4861 * implemented for most applications, they can be used, for example, to initialize and free private data.
4863 * <b>setter functions</b> after a call of SCIPincludeNlhdlrNonlinear(), see also @ref NLHDLR_INTERFACE.
4867 * This callback is called when doing a copy of the constraint handler for nonlinear constraints.
4872 * If you are using nonlinear handler data (see \ref NLHDLR_DATA and \ref NLHDLR_INTERFACE), you have to implement this function
4877 * If you are using nonlinear handler expression data (see \ref NLHDLR_DATA and \ref NLHDLRDETECT), you have to implement this function
4883 * This callback is called when the constraint handler for nonlinear constraints is initialized, that is, after the problem was transformed.
4884 * The nonlinear handler can use this callback to initialize or reset some data for the upcoming solve.
4888 * This callback is called when the constraint handler for nonlinear constraints is deinitialized, that is, before the transformed problem is freed.
4889 * The nonlinear handler can use this callback to free some data that was used for the previous solve only.
4894 * It is called for expressions for which the nonlinear handler registered to participate in \ref SCIP_NLHDLR_METHOD_ACTIVITY in \ref NLHDLRDETECT.
4895 * The function is given the currently available bounds to the expression and can return possibly tighter bounds.
4897 * For a univariate quotient ((ax+b)/(cx+d)), the interval evaluation is implemented as follows:
4902 * This callback is called when bounds on a given expression shall be propagated to its successors.
4903 * It is called for expressions for which the nonlinear handler registered to participate in \ref SCIP_NLHDLR_METHOD_ACTIVITY in \ref NLHDLRDETECT.
4904 * The tighter intervals should be passed to the corresponding expression via SCIPtightenExprIntervalNonlinear().
4911 * This callback is called when the constraint handler for nonlinear constraints initializes the LP relaxation (@ref CONSINITLP).
4912 * It is called for expressions for which the nonlinear handler registered to participate in \ref SCIP_NLHDLR_METHOD_SEPABELOW or \ref SCIP_NLHDLR_METHOD_SEPAABOVE in \ref NLHDLRDETECT.
4913 * The function shall initialize the separation data of the nonlinear handler, if any, and add initial cuts to the LP relaxation.
4914 * It can assume that auxiliary variables are available for expressions for which auxiliary variables were requested via SCIPregisterExprUsageNonlinear() in \ref NLHDLRDETECT.
4918 * This callback is called when the solving process is finished and the branch and bound process data is freed (@ref CONSEXITSOL).
4919 * It is called for expressions for which the nonlinear handler registered to participate in \ref SCIP_NLHDLR_METHOD_SEPABELOW or \ref SCIP_NLHDLR_METHOD_SEPAABOVE in \ref NLHDLRDETECT and \ref NLHDLRINITSEPA was called.
4924 * This callback is called when the constraint handler requires that the relation between the given expression and its auxiliary variable
4925 * (`expr` ≤ `auxvar` or `expr` ≥ `auxvar`) is violated by a given solution and this solution needs to be separated.
4926 * It is called for expressions for which the nonlinear handler registered to participate in \ref SCIP_NLHDLR_METHOD_SEPABELOW or \ref SCIP_NLHDLR_METHOD_SEPAABOVE in \ref NLHDLRDETECT.
4930 * - bound tightening, i.e., changing bounds on a variable so that the given point is outside the updated domain, or
4935 * If the nonlinear handler always separates by computing a linear under- or overestimator of `expr`,
4938 * Note, that the nonlinear handler may also choose to separate for a relaxation of the mentioned sets,
4942 * The constraint handler ensures that `lhs` ≤ lowerbound(`auxvar`) and upperbound(`auxvar`) ≤ `rhs`.
4944 * The constraint handler may call this callback first with `allowweakcuts` = FALSE and repeat later with
4946 * If in enforcement and the nonlinear handler cannot enforce by separation or bound tightening, it should register
4947 * branching scores for those expressions where branching may help to compute tighter cuts in children.
4956 * This callback is called when the constraint handler requires that the relaxation between the given expression and its auxiliary variable
4957 * (`expr` ≤ `auxvar` or `expr` ≥ `auxvar`) is violated by a given solution and this solution needs to be separated.
4958 * It is called for expressions for which the nonlinear handler registered to participate in \ref SCIP_NLHDLR_METHOD_SEPABELOW or \ref SCIP_NLHDLR_METHOD_SEPAABOVE in \ref NLHDLRDETECT.
4959 * This function is a simpler alternative to \ref NLHDLRENFO and is called if \ref NLHDLRENFO is not implemented or does not succeed.
4961 * The function shall compute one or several linear under- or overestimator of `expr` that are as tight as possible at a given point.
4965 * If successful, it shall store the estimators in the given `rowpreps` data structure and set the
4970 * The callback may also be required to indicate for which expression a reduction in the local bounds (usually by branching) would improve the estimator.
4978 * This callback is called by the constraint handler when it has caught a solution event from SCIP and option constraints/nonlinear/linearizeheursol has been enabled.
4979 * The constraint handler then calls the nonlinear handlers for all expressions they currently handle.
4980 * The nonlinear handler may use this opportunity to add a cut that supports its nonlinear function in the given solution to the cutpool.
4981 * For convex functions, this may help to accellerate proving optimality for a solution found by a NLP solver.
4984/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4988 * Diving heuristics are an important addon to the branch-and-cut search. A diving heuristic explores a single probing
4989 * path down the search tree. In contrast to the regular search guided by branching rule(s) and the selected
4990 * node selector, the diving is performed in an auxiliary tree originating from the focus node of the main
4991 * search tree where the heuristic was called. The advantage of this approach is that many different scoring mechanisms
4992 * can be safely tried as diving heuristic and may probably lead to better solutions. SCIP has a lot of diving heuristics
4996 * Since SCIP version 3.2, the diving heuristics have been redesigned to contain mainly the scoring function used by the
4997 * heuristic. In order to implement a user-defined diving heuristic, it is possible to create one (or several)
4998 * divesets that control the scoring mechanism and add them to the primal heuristic. This has the advantage that
4999 * less code is necessary to create a working diving heuristic. The SCIP statistics now also display some interesting statistics
5003 * This page contains the necessary steps to understand and include a diveset into ones primal diving heuristic plugin. As
5004 * a prerequisite, you should understand the basic implementation steps for a primal heuristic, see \ref HEUR.
5005 * In order to make use of divesets, they must be included _after_ the primal heuristic to which they should belong
5006 * has been included, by using SCIPincludeDiveset(). This will create the data structure for the diveset and
5007 * append it to the list of divesets belonging to the heuristic, which can be retrieved later together with their number
5008 * by using SCIPheurGetDivesets() and SCIPheurGetNDivesets(), respectively. No further memory allocation or deletion is needed;
5009 * As a member of the heuristic, SCIP automatically takes care of freeing the diveset when it is exiting.
5012 * Before the inclusion, one may think of adjusting the various properties that a diveset offers to control
5016 * It is mandatory to implement the fundamental scoring callback of the diveset, which is explained in more detail
5021 * has been defined, use the function SCIPperformGenericDivingAlgorithm() inside the execution callback (\ref HEUREXEC) of the primal
5022 * heuristic to which the diveset belongs, after checking possible preliminaries that may not be met at all times of the search.
5025 * For a code example, we refer to \ref heur_guideddiving.h, which guides the diving into the direction of the current incumbent solution.
5026 * Before it calls SCIPperformGenericDivingAlgorithm(), it checks whether an incumbent is available, and returns if there is none.
5031 * Every diveset controls the diving behavior through a set of user-defined parameters, which are explained in the following:
5034 * the minimal relative depth (to the maximum depth explored during regular search) of the current focus node to start diving
5037 * the maximal relative depth (to the maximum depth explored during regular search) of the current focus node to start diving
5040 * maximal fraction of diving LP iterations compared to node LP iterations that this dive controller may consume
5063 * parameter to control LP resolve dynamically based on this percentage of observed bound changes relative to all variables or
5064 * the LP branching candidates (integer variables with fractional solution values) from the last node where an LP has been solved.
5068 * LP solve frequency for diveset, use a positive integer k to solve an LP at every k'th depth of the diving search (ie. 1 causes the
5069 * diveset to solve _all_ intermediate LPs) or 0 to only resolve the LP relaxation after propagation found at least a certain percentage
5073 * Set this property to TRUE if only LP branching candidates be considered for the execution of the diving algorithm instead of the slower but
5077 * bit mask that represents all supported dive types. Irrelevant if only LP branching candidates should be scored, otherwise, different
5078 * constraint handlers may ask the diveset if it supports their preferred divetype. See \ref type_heur.h for a list of
5087 * The scoring callback expects a candidate variable and calculates a score value and a preferred direction. The selected
5089 * If the diveset should support more than one possible type of diving, it may use the divetype argument as a hint how
5090 * the caller of the score function (could be the diving algorithm itself or one of the constraint handlers that
5095 * This is all there is to extend the SCIP set of diving heuristics by a new one. For further information, please see
5096 * diveset related functions in \ref type_heur.h, \ref pub_heur.h, \ref heuristics.h, and \ref heur_guideddiving.h or
5100/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5104 * SCIP provides specific support for LP relaxations of constraint integer programs. In addition, relaxation handlers,
5105 * also called relaxators, can be used to include other relaxations, e.g. Lagrange relaxations or semidefinite
5106 * relaxations. The relaxation handler manages the necessary data structures and calls the relaxation solver to generate dual
5109 * However, the data to define a single relaxation must either be extracted by the relaxation handler itself (e.g., from
5110 * the user defined problem data, the LP information, or the integrality conditions), or it must be provided by the constraint
5111 * handlers. In the latter case, the constraint handlers have to be extended to support this specific relaxation.
5114 * We now explain how users can add their own relaxation handlers using the C interface. As an example, look into the NLP
5115 * relaxation handler of the \ref RELAXATOR_MAIN "Relaxator example" (examples/Relaxator/src/relax_nlp.c). It is very easy to
5116 * transfer the C explanation to C++: whenever a function should be implemented using the SCIP_DECL_RELAX... notion,
5117 * reimplement the corresponding virtual member method of the abstract scip::ObjRelax wrapper base class.
5119 * Additional documentation for the callbacks of a relaxation handler can be found in the file type_relax.h.
5122 * -# Copy the template files src/scip/relax_xyz.c and src/scip/relax_xyz.h into files named "relax_myrelaxator.c"
5125 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
5126 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
5127 * -# Use `SCIPincludeRelaxMyrelaxator()` in order to include the relaxation handler into your SCIP instance,
5128 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
5129 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
5130 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "myrelaxator".
5135 * -# Implement the additional callbacks (see \ref RELAX_ADDITIONALCALLBACKS). This is optional.
5140 * At the top of the new file "relax_myrelaxator.c" you can find the relaxation handler properties,
5142 * In the C++ wrapper class, you have to provide the relaxation handler properties by calling the constructor
5148 * Additionally, if you are searching for a relaxation handler with SCIPfindRelax(), this name is looked up.
5156 * price-and-cut loop for solving the LP relaxation are called in a predefined order, which is given by the priorities
5158 * First, the relaxation handlers with non-negative priority are called in the order of decreasing priority.
5160 * Finally, the relaxation handlers with negative priority are called in the order of decreasing priority.
5162 * Usually, you will have only one relaxation handler in your application and thus only have to decide whether it should
5163 * be called before or after solving the LP relaxation. For this decision you should consider the complexity of
5164 * the relaxation solving algorithm and the impact of the resulting solution: if your relaxation handler provides a fast
5166 * feasible region of the subproblem and the solution severely improves the dual bound), it should have a non-negative
5169 * Note that for certain applications, it is useful to disable the LP relaxation and only use your custom relaxation.
5173 * The frequency defines the depth levels at which the relaxation solving function \ref RELAXEXEC is called.
5174 * For example, a frequency of 7 means, that the relaxation solving callback is executed for subproblems that are in depth
5175 * 0, 7, 14, ... of the branching tree. A frequency of 0 means that the callback is only executed at the root node, i.e.,
5176 * only the relaxation of the root problem is solved. A frequency of -1 disables the relaxation handler.
5182 * Below the header "Data structures" you can find a struct which is called "struct SCIP_RelaxData".
5183 * In this data structure, you can store the data of your relaxation handler. For example, you should store the adjustable
5185 * If you are using C++, you can add relaxation handler data as usual as object variables to your class.
5192 * At the bottom of "relax_myrelaxator.c", you can find the interface function SCIPincludeRelaxMyrelaxator(),
5194 * SCIPincludeRelaxMyrelaxator() is called by the user, if (s)he wants to include the relaxation handler,
5198 * It is responsible for notifying SCIP of the presence of the relaxation handler. For this, you can either call
5200 * or SCIPincludeRelaxBasic() since SCIP version 3.0. In the latter variant, \ref RELAX_ADDITIONALCALLBACKS "additional callbacks"
5201 * must be added via setter functions as, e.g., SCIPsetRelaxCopy(). We recommend this latter variant because
5202 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
5203 * variant must be manually adjusted with every SCIP release containing new callbacks for relaxation handlers in order to compile.
5205 * If you are using relaxation handler data, you have to allocate the memory for the data at this point.
5212 * You may also add user parameters for your relaxation handler, see the function SCIPincludeConshdlrKnapsack() in
5213 * the \ref cons_knapsack.h "knapsack constraint handler" for an example of how to add user parameters.
5218 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
5220 * They are passed together with the relaxation handler itself to SCIP using SCIPincludeRelax() or SCIPincludeRelaxBasic(),
5224 * Relaxation handler plugins have only one fundamental callback, namely the \ref RELAXEXEC function.
5225 * This function has to be implemented for every relaxation handler; the other callbacks are optional.
5226 * In the C++ wrapper class scip::ObjRelax, the scip_exec() method (which corresponds to the \ref RELAXEXEC callback) is a virtual
5228 * You have to implement it in order to be able to construct an object of your relaxation handler class.
5236 * Note that, like the LP relaxation, the relaxation handler should only operate on variables for which the corresponding
5237 * column exists in the transformed problem. Typical functions called by a relaxation handler are SCIPconstructLP() and SCIPflushLP() to
5238 * make sure that the LP of the current node is constructed and its data can be accessed via calls to SCIPgetLPRowsData()
5239 * and SCIPgetLPColsData(), and SCIPseparateSol() to call the cutting plane separators for a given primal solution.
5241 * The lowerbound computed by the relaxation should be returned in the lowerbound pointer. If the relaxation improves on the best
5242 * relaxation already computed (either <code>SCIPisRelaxSolValid()</code> returns FALSE, meaning that no relaxation solution
5243 * is available so far, or the lowerbound is larger than the value returned by <code>SCIPgetRelaxSolObj()</code>), then the primal
5244 * solution of the relaxation should be stored inside the data structures of SCIP with <code>SCIPsetRelaxSolVal()</code>,
5245 * <code>SCIPsetRelaxSolVals()</code> or <code>SCIPsetRelaxSolValsSol()</code>. If you set the values one by one, you will need to call
5246 * <code>SCIPmarkRelaxSolValid()</code> to inform SCIP that the solution is complete and valid. With the "includeslp" argument of
5247 * <code>SCIPsetRelaxSolVals()</code>, <code>SCIPsetRelaxSolValsSol()</code> and <code>SCIPmarkRelaxSolValid()</code> you need to tell SCIP
5248 * whether the relaxation included all lp rows. In this case, the solution will be enforced and, if feasible, added to the solution storage if the
5249 * lowerbound of this relaxator is larger than the LP's. You may also call SCIPtrySolFree() directly from the
5250 * relaxation handler to make sure that a solution is added to the solution storage if it is feasible, even if the relaxator does not
5251 * include the LP or another relaxator produced a stronger bound. Also note that when setting the values of the relaxation solution one by one,
5252 * the objective value of the relaxation solution will be updated incrementally. If the whole solution should be updated, using SCIPsetRelaxSolVals()
5253 * instead or calling SCIPclearRelaxSolVals() before setting the first value to reset the solution and the objective value to 0 may help the numerics.
5254 * Furthermore, there is a list of external branching candidates, that can be filled by relaxation handlers and constraint handlers,
5255 * allowing branching rules to take these candidates as a guide on how to split the problem into subproblems. If the relaxation
5256 * solution is enforced, the integrality constraint handler will add external branching candidates for the relaxation solution
5257 * automatically, but the relaxation handler can also directly call <code>SCIPaddExternBranchCand()</code>.
5259 * Usually, the RELAXEXEC callback only solves the relaxation and provides a lower (dual) bound through the corresponding pointer and
5261 * However, it may also produce domain reductions, add additional constraints or generate cutting planes. It has the
5263 * - detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
5264 * - adding an additional constraint and stating that the relaxation handler should not be called again on the same
5266 * - reducing a variable's domain and stating that the relaxation handler should not be called again on the same
5268 * - adding a cutting plane to the LP and stating that the relaxation handler should not be called again on the same
5270 * - stating that the relaxation handler solved the relaxation and should not be called again on the same relaxation
5272 * - interrupting the solving process to wait for additional input, e.g., cutting planes (result SCIP_SUSPENDED)
5275 * In the above criteria, "the same relaxation" means that the LP relaxation stayed unmodified. This means in particular
5276 * that no row has been added and no bounds have been modified. For example, changing the bounds of a variable will, as
5277 * long as it was a COLUMN variable, lead to a modification in the LP such that the relaxation handler is called again
5278 * after it returned with the result code SCIP_REDUCEDDOM. If the relaxation solution should be enforced, the relaxation
5279 * handler has to produce a new solution in this case which satisfies the updated LP. If a relaxation handler should only run
5280 * once per node to compute a lower bound, it should store the node of the last relaxation call itself and return
5286 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
5287 * implemented for most applications, they can be used, for example, to initialize and free private data.
5288 * Additional callbacks can either be passed directly with SCIPincludeRelax() to SCIP or via specific
5289 * <b>setter functions</b> after a call of SCIPincludeRelaxBasic(), see also @ref RELAX_INTERFACE.
5293 * If you are using relaxation handler data, you have to implement this function in order to free the relaxation handler
5298 * If you have allocated memory for fields in your relaxation handler data, remember to free this memory
5320 * In this function, the relaxation handler should free all resources that have been allocated for the solving process in
5325 * The RELAXINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
5326 * begin. The relaxation handler may use this call to initialize its branch-and-bound specific data.
5334/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5338 * Mainly, file readers are called to parse an input file and generate a constraint integer programming model. They
5339 * create constraints and variables and activate variable pricers if necessary. However, they can also be called, for
5340 * example, to parse an input file containing information about a primal solution or fixing of variables. Besides that
5341 * it is possible to use some of them for writing (exporting) the problem in a specific format. \n A complete list of
5356 * Take the file reader for MIPs in IBM's Mathematical Programming System format (src/scip/reader_mps.c) as an example.
5357 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjReader wrapper
5358 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_READER... callbacks.
5360 * Additional documentation for the callbacks of a file reader can be found in the file type_reader.h.
5366 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
5367 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
5369 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
5370 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
5383 * In the C++ wrapper class, you have to provide the file reader properties by calling the constructor
5389 * Additionally, if you are searching for a file reader with SCIPfindReader(), this name is looked up.
5396 * Each file reader is hooked to a single file name extension. It is automatically called if the user wants to read in a
5398 * Note that the additional extension '.gz', '.z', or '.Z' (indicating a gzip compressed file) are ignored for assigning
5402 * It is, however, not necessary to implement the same (parsing/writing) functions more than once, if you want to
5409 * Below the header "Data structures" you can find a struct which is called "struct SCIP_ReaderData".
5410 * In this data structure, you can store the data of your file reader. For example, you should store the adjustable
5412 * If you are using C++, you can add file reader data as usual as object variables to your class.
5419 * At the bottom of "reader_myreader.c", you can find the interface function SCIPincludeReaderMyreader(),
5425 * It is responsible for notifying SCIP of the presence of the reader. For this, you can either call
5427 * or SCIPincludeReaderBasic() since SCIP version 3.0. In the latter variant, \ref READER_ADDITIONALCALLBACKS "additional callbacks"
5428 * must be added via setter functions as, e.g., SCIPsetReaderCopy(). We recommend this latter variant because
5429 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
5430 * variant must be manually adjusted with every SCIP release containing new callbacks for readers in order to compile.
5432 * If you are using file reader data, you have to allocate the memory for the data at this point.
5439 * You may also add user parameters for your file reader, see the function SCIPincludeReaderLp() in
5450 * functions \ref READERCOPY and \ref READERFREE are optional. In the C++ wrapper class scip::ObjReader, the
5460 * Additional callbacks can either be passed directly with SCIPincludeReader() to SCIP or via specific
5461 * <b>setter functions</b> after a call of SCIPincludeReaderBasic(), see also @ref READER_INTERFACE.
5465 * \ref READERWRITE, \ref READERFREE, and \ref READERCOPY. Therefore, these are not needed to be implemented. However,
5472 * The READERREAD callback is called when the user invokes SCIP to read in a file with file name extension
5473 * corresponding to the READER_EXTENSION property of the file reader. This is usually triggered by a call to the function
5475 * The READERREAD callback should parse the input file and perform the desired action, which usually means
5476 * generating a constraint integer programming model, adding a primal solution, fixing variables
5483 * - creating the variables: SCIPcreateVar(), SCIPchgVarType(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPaddVar(), and
5486 * - creating the constraints: SCIPcreateConsLinear(), SCIPaddCoefLinear(), SCIPchgLhsLinear(), SCIPchgRhsLinear(),
5489 * Primal solutions can only be created for the transformed problem. Therefore, the user has to call SCIPtransformProb()
5490 * before (s)he reads in the file containing the solution and adds it to the solution pool via the function SCIPreadSol().
5495 * The READERWRITE callback is called when the user invokes SCIP to write a problem (original or transformed)
5496 * in the format the reader supports. This is only possible if this callback is implemented. To write the problem
5497 * all necessary information is given through the parameters of this callback (see type_reader.h). This
5498 * information should be used to output the problem in the requested format. This callback is usually
5499 * triggered by the call of the functions SCIPwriteOrigProblem(), SCIPwriteTransProblem(), SCIPprintOrigProblem(),
5503 * integer programming model is SCIPinfoMessage(). This function outputs a given string into a file
5511 * The READERCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
5512 * callback as <code>NULL</code> the user disables the execution of the specified reader for all copied SCIP
5513 * instances. The question might arise why to copy that plugin. In case of debugging it is nice to be able to
5514 * write/display the copied instances. Since the reader is in charge of that, you might want to copy the plugin. Below
5521 * If you are using file reader data, you have to implement this function in order to free the file reader data.
5526 * If you have allocated memory for fields in your file reader data, remember to free this memory
5533/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5537 * SCIP comes with a command line shell which allows the user to read in problem instances, modify the solver's
5538 * parameters, initiate the optimization and display certain statistics and solution information. This shell consists
5539 * of dialogs, which are organized as a tree in SCIP. A node of this tree which is not a leaf represents a menu in
5540 * the shell and the children of this node correspond to the entries of this menu (which can again be menus). All
5541 * different dialogs are managed by a dialog handler, which, in particular, is responsible for executing the dialog
5542 * corresponding to the user's command in the shell. The concept of a dialog handler is different to that
5543 * of a constraint handler, which is used to manage objects of the same structure, see \ref CONS. In particular, SCIP
5544 * features only one dialog handler (dialog_default.h), whereas there may exist different constraint handlers.
5549 * We give the explanation for creating your own source file for each additional dialog. Of course, you can collect
5550 * different dialogs in one source file. Take src/scip/dialog_default.c, where all default dialog plugins are collected, as an
5552 * As all other default plugins, the default dialog plugin and the template dialog are written in C. C++ users can easily
5553 * adapt the code by using the scip::ObjDialog wrapper base class and implement the scip_...() virtual methods instead of the
5556 * Additional documentation for the callbacks of a dialog can be found in the file type_dialog.h.
5559 * -# Copy the template files src/scip/dialog_xyz.c and src/scip/dialog_xyz.h into files named "dialog_mydialog.c"
5562 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
5563 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
5564 * -# Use `SCIPincludeDialogMydialog()` in order to include the dialog handler into your SCIP instance,
5565 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
5566 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
5579 * In the C++ wrapper class, you have to provide the dialog properties by calling the constructor
5584 * In the interactive shell, this name appears as the command name of the dialog in the parent dialog.
5585 * Additionally, if you are searching an entry in a menu with SCIPdialogFindEntry(), this name is looked up.
5586 * Names within one menu have to be unique: no two dialogs in the same menu may have the same name.
5589 * This string is printed as a description of the dialog in the interactive shell if the additional
5593 * This parameter states whether the dialog is a menu in the interactive shell, i.e., is the parent of further
5599 * Below the header "Data structures" you can find a struct which is called "struct SCIP_DialogData".
5608 * At the bottom of "dialog_mydialog.c" you can find the interface function SCIPincludeDialogMydialog(), which also appears
5612 * It is responsible for notifying SCIP of the presence of the dialog, which can be done by the following lines of code:
5616 * Here "parentdialog" has to be an existing dialog which is defined to be a menu (see DIALOG_ISSUBMENU), e.g.,
5619 * The interface function is called by the user, if (s)he wants to include the dialog, i.e., if (s)he wants to use the dialog in
5623 * default dialogs plugin</b>, i.e., the SCIPincludeDialogMydialog() call has to occur after the
5624 * SCIPincludeDialogDefault() call. The SCIPincludeDialogDefault() function is called from within the SCIPincludeDefaultPlugins()
5625 * function. Therefore, it suffices to include your dialog plugins after you have called SCIPincludeDefaultPlugins().
5641 * Consider the following example. The user wants to add a "drawgraph" command to the root menu of SCIP.
5642 * (S)he copies the "dialog_xyz.c" and "dialog_xyz.h" files into files "dialog_drawgraph.c" and "dialog_drawgraph.h", respectively.
5643 * Then, (s)he puts the following code into the SCIPincludeDialogDrawgraph() function, compare SCIPincludeDialogDefault() in
5647 * Using this code, it is even possible to call SCIPincludeDialogDrawgraph() before including the default dialog plugins,
5648 * and you can also call it multiple times without causing inconsistencies in the dialog structure.
5655 * In the C++ wrapper class scip::ObjDialog, the scip_exec() method (which corresponds to the \ref DIALOGEXEC callback) is a virtual
5663 * The DIALOGEXEC function is invoked, if the user selected the dialog's command name in the parent's menu. It should
5664 * execute what is stated in DIALOG_DESC, e.g., the display constraint handlers dialog should display information about
5667 * For typical functions called by the execution function, have a look at src/scip/dialog_default.c.
5669 * The callback has to return which dialog should be processed next. This can be, for example, the root dialog
5670 * (SCIPdialoghdlrGetRoot()), the parent dialog (SCIPdialogGetParent()) or NULL, which stands for closing the interactive
5681 * If you are using dialog data, you have to implement this function in order to free the dialog data.
5692 * This function is called when the help menu of the parent is displayed. It should output (usually a single line of)
5695 * If this callback is not implemented, the description string of the dialog (DIALOG_DESC) is displayed instead.
5699 * The DIALOGCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
5700 * callback as <code>NULL</code> the user disables the execution of this dialog for all copied SCIP instances. In
5701 * general there is no need to copy any dialog since it is most unlikely to start the interactive shell of the copied
5706/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5710 * While solving a constraint integer program, SCIP displays status information in a column-like fashion. The current
5711 * number of processed branching tree nodes, the solving time, and the relative gap between primal and dual bound are
5712 * examples of such display columns. There already exists a wide variety of display columns which can be activated or
5713 * deactivated on demand, see src/scip/disp_default.c. Additionally, the user can implement his/her own display columns
5719 * We give the explanation for creating your own source file for each additional display column. Of course, you can collect
5721 * Take src/scip/disp_default.c, where all default display columns are collected, as an example.
5722 * As all other default plugins, the default display column plugins and the display column template are written in C.
5723 * C++ users can easily adapt the code by using the scip::ObjDisp wrapper base class and implement the scip_...() virtual methods
5727 * Additional documentation for the callbacks of a display column can be found in the file type_disp.h.
5729 * Here is what you have to do to implement a display column (assuming your display column is named "mydisplaycolumn"):
5730 * -# Copy the template files src/scip/disp_xyz.c and src/scip/disp_xyz.h into files named "disp_mydisplaycolumn.c"
5733 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
5734 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
5735 * -# Use `SCIPincludeDispMydisplaycolumn()` in order to include the display column into your SCIP instance,
5736 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
5737 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
5738 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mydisplaycolumn".
5748 * At the top of the new file "disp_mydisplaycolumn.c" you can find the display column properties.
5750 * In the C++ wrapper class, you have to provide the display column properties by calling the constructor
5756 * Additionally, if you are searching for a display column with SCIPfindDisp(), this name is looked up.
5763 * This string is printed as the header of the display column in the status information display.
5766 * This parameter defines the width (number of characters) of the display column. The value of the parameter has to be
5770 * The total width of status information lines is bounded by the parameter "display width". The display columns actually contained
5771 * in the status information display are selected in decreasing order of their priority. Furthermore, the user can force
5772 * columns to be displayed or not to be displayed in the status information display. For that, (s)he has to switch the value
5773 * of the display column's parameter "active" from "auto" (its default value) to "on" or "off", respectively.
5776 * In the status information display, the display columns are arranged from left to right in increasing order of their
5779 * \par DISP_STRIPLINE: the default for whether the display column should be separated with a line from its right neighbor.
5780 * This parameter states whether the display column should be separated with the string "|" from its right neighbor. In so
5785 * Below the header "Data structures" you can find a struct which is called "struct SCIP_DispData".
5786 * In this data structure, you can store the data of your display column. For example, you should store the adjustable
5788 * If you are using C++, you can add display column data as usual as object variables to your class.
5795 * At the bottom of "disp_mydisplaycolumn.c" you can find the interface function SCIPincludeDispMydisplaycolumn(), which also
5799 * It is responsible for notifying SCIP of the presence of the display column by calling the function
5802 * The interface function is called by the user, if (s)he wants to include the display column, i.e., if (s)he wants to use the display column in his
5805 * If you are using display column data, you have to allocate the memory for the data at this point.
5812 * Although this is very uncommon, you may also add user parameters for your display column, see the function
5813 * SCIPincludeConshdlrKnapsack() in the \ref cons_knapsack.h "knapsack constraint handler" for an example.
5818 * Display column plugins have only one fundamental callback, namely the \ref DISPOUTPUT function.
5819 * This function has to be implemented for every display column; the other callbacks are optional.
5820 * In the C++ wrapper class scip::ObjDisp, the scip_output() method (which corresponds to the \ref DISPOUTPUT callback) is a virtual
5822 * You have to implement it in order to be able to construct an object of your display column class.
5828 * The DISPOUTPUT callback is called after each pricing loop during node processing and after a node has been processed.
5829 * In addition, at the root node, the callback is executed after each iteration of the price-and-cut loop.
5830 * It should write the display column information for the current node to a given output file stream.
5832 * Typical functions called by a display column are, for example, SCIPdispLongint(), SCIPdispInt(), SCIPdispTime(), and
5843 * The DISPCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback
5844 * as <code>NULL</code> the user disables the execution of the specified column. In general it is probably not needed to
5845 * implement that callback since the output of the copied instance is usually suppressed. In the other case or for
5851 * If you are using display column data, you have to implement this function in order to free the display column data.
5855 * If you have allocated memory for fields in your display column data, remember to free this memory
5868 * In this function, the display column should free all resources that have been allocated for the solving process in
5873 * The DISPINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
5874 * begin. The display column may use this call to initialize its branch-and-bound specific data.
5878 * The DISPEXITSOL callback is executed before the branch-and-bound process is freed. The display column should use this
5882/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5886 * While solving a constraint integer program, SCIP drops thousands of events such as SCIP_EVENTTYPE_VARFIXED (a
5887 * complete list of all events is given in type_event.h). These events can be caught and used to do something after a
5888 * certain event happens. Events can be used to speed up the solution process. For example, the set partitioning
5889 * constraint is only worth propagating if one of the involved variables is fixed. This can be detected by
5890 * catching the event SCIP_EVENTTYPE_VARFIXED. To be able to catch an event it is necessary to write an event handler
5893 * We now explain how users can add their own event handlers. We give the explanation for creating your own
5894 * source file for each additional event handler. Of course, you can collect different event handlers in one source file
5895 * or you can put the event handler directly into the constraint handler. In a \ref EVENTUSAGE "second step" we discuss
5896 * the usage of an event handler. This means how to catch and drop events. \ref EVENTTYPES "Finally", we give some notes on the existing
5899 * Take src/scip/cons_logior.c, where the event handler is directly included into the constraint handler. As all other
5900 * default plugins, the event handlers are written in C. C++ users can easily adapt the code by using the scip::ObjEventhdlr
5901 * wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_EVENT... callbacks.
5903 * Additional documentation for the callbacks of an event handler can be found in the file type_event.h. There is
5904 * also an example written in C which deals with an event handler. You find this example in the directory
5905 * "examples/Eventhdlr/". An C++ example can be found within the TSP project (examples/TSP/src/EventhdlrNewSol.cpp).
5907 * Here is what you have to do to implement an event handler (assuming your event handler is named "bestsol"):
5908 * -# Copy the template files src/scip/event_xyz.c and src/scip/event_xyz.h into files named "event_bestsol.c"
5911 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
5912 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
5913 * -# Use `SCIPincludeEventBestsol()` in order to include the event handler into your SCIP instance,
5914 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
5915 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
5927 * In the C++ wrapper class, you have to provide the event handler properties by calling the constructor
5932 * This name has to be unique with respect to all other event handlers. If you are searching for an event handler with
5940 * Below the header "Data structures" you can find a struct which is called "struct SCIP_EventhdlrData".
5941 * In this data structure, you can store the data of your event handler. For example, you should store the adjustable
5943 * If you are using C++, you can add event handler data as usual as object variables to your class.
5950 * At the bottom of "event_bestsol.c", you can find the interface function SCIPincludeEventBestsol(),
5952 * SCIPincludeEventBestsol() is called by the user, if (s)he wants to include the event handler,
5956 * It is responsible for notifying SCIP of the presence of the event handler. For this, you can either call
5958 * or SCIPincludeEventhdlrBasic() since SCIP version 3.0. In the latter variant, \ref EVENT_ADDITIONALCALLBACKS "additional callbacks"
5959 * must be added via setter functions as, e.g., SCIPsetReaderCopy(). We recommend this latter variant because
5960 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
5961 * variant must be manually adjusted with every SCIP release containing new callbacks for event handlers in order to compile.
5963 * If you are using event handler data, you have to allocate the memory for the data at this point.
5970 * Although this is very uncommon, you may also add user parameters for your event handler, see the function
5971 * SCIPincludeConshdlrKnapsack() in the \ref cons_knapsack.h "knapsack constraint handler" for an example.
5976 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
5978 * They are passed together with the event handler itself to SCIP using SCIPincludeEventhdlr() or SCIPincludeEventhdlrBasic(),
5982 * Event handler plugins have only one fundamental callback, namely the \ref EVENTEXEC function. This function has
5983 * to be implemented for every event handler; the other callbacks are optional. In the C++ wrapper class
5984 * scip::ObjEventhdlr, the scip_exec() method (which corresponds to the \ref EVENTEXEC callback) is a virtual abstract member
5985 * function. You have to implement it in order to be able to construct an object of your event handler class.
5991 * The EVENTEXEC callback is called after the requested event happened. Then the event handler can do some action in
5994 * Typical the execution function sets a parameter to TRUE to indicate later in solving process that something happened
5995 * which should be analyzed further. In the \ref cons_knapsack.h "knapsack constraint handler" you find such a typical
6000 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
6001 * implemented for most applications, they can be used, for example, to initialize and free private data.
6002 * Additional callbacks can either be passed directly with SCIPincludeEventhdlr() to SCIP or via specific
6003 * <b>setter functions</b> after a call of SCIPincludeEventhdlrBasic(), see also @ref EVENT_INTERFACE.
6007 * The EVENTCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
6008 * callback as <code>NULL</code> the user disables the execution of the specified event handler for all copied SCIP
6009 * instances. Note that in most cases the event handler in the copied instance will be initialize by those objects (such
6010 * as constraint handlers or propagators) which need this event handler (see \ref cons_knapsack.h). In these cases the copy
6012 * (SCIP_EVENTTYPE_BESTSOLFOUND), you might want to implement that callback. The event handler example which you find
6019 * If you are using event handler data, you have to implement this function in order to free the event handler data.
6024 * If you have allocated memory for fields in your event handler data, remember to free this memory
6038 * In this function, the event handler should free all resources that have been allocated for the solving process in
6043 * The EVENTINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
6048 * The EVENTEXITSOL callback is executed before the branch-and-bound process is freed. The event handler should use this
6053 * After you have implemented the event handler, you have to tell SCIP for which events this event handler should be
6054 * used. This can be a general events, such as <code>SCIP_EVENTTYPE_BESTSOLFOUND</code>, or a variable event which is the most common
6057 * In case of a general (not variable) event you use the function SCIPcatchEvent() to attach to an event and
6068 * If you want trigger some variable event, you use the function SCIPcatchVarEvent() to attach the variable event and
6081 * All available events are listed in type_event.h. There are atomic events such as <code>SCIP_EVENTTYPE_VARFIXED</code>
6082 * and combined events such as <code>SCIP_EVENTTYPE_VARCHANGED</code>. The events are encoded via bit masks. Each atomic
6085 * SCIP only throws atomic events. However, an event handler might be interested in bunch of events. Through the
6086 * underlying bit masks it is possible to combine the atomic events. For example, <code>SCIP_EVENTTYPE_VARCHANGED</code>
6087 * is an event which combines the events <code>SCIP_EVENTTYPE_VARFIXED</code>, <code>SCIP_EVENTTYPE_VARUNLOCKED</code>,
6092 * #define SCIP_EVENTTYPE_VARCHANGED (SCIP_EVENTTYPE_VARFIXED | SCIP_EVENTTYPE_VARUNLOCKED | SCIP_EVENTTYPE_OBJCHANGED
6096 * Depending on the event type, the event offers different information. The functions which can be used to gain
6101/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
6106 * It is used, e.g., to solve convex relaxations of the problem or to find locally optimal solutions of
6110 * While the NLPI itself corresponds to the solver interface, the NLPIPROBLEM corresponds to the
6112 * An NLP is specified as a set of indexed variables with variable bounds, an objective function,
6113 * and a set of constraints, where each constraint is specified as a function which is restricted to lie
6116 * The linear part is specified via variable indices and coefficients, while the nonlinear part is specified via an expression.
6117 * That is, the user of the NLPI does not provide function evaluation callbacks but an algebraic representation of the NLP.
6118 * Interfaces for solvers that require function evaluations can make use of the \ref NLPIOracle "NLPIORACLE", which
6119 * provides functionality to store a NLP and compute functions values, gradients, Jacobians, and Hessians.
6127 * Additional documentation for the callbacks of an NLPI, in particular for their input parameters,
6131 * -# Copy the template files src/scip/nlpi_xyz.c and src/scip/nlpi_xyz.h into files named "nlpi_mysolver.c" and "nlpi_mysolver.h".
6132 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
6133 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
6134 * -# Use `SCIPincludeNlpSolverMysolver()` in order to include the NLPI into your SCIP instance,
6135 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
6136 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
6163 * solvers that provide fast algorithms that are usually successful on a wide range of problems should have a high priority.
6164 * An easy way to list the priorities of all NLPIs is to type "display nlpis" in the interactive shell of SCIP.
6168 * Below the header "Data structures" you can find structs which are called `struct SCIP_NlpiData` and `struct SCIP_NlpiProblem`.
6169 * In these data structures, you can store the data of your solver interface and of a specific NLP problem.
6170 * For example, you could store a pointer to your NLP solver environment object in the `SCIP_NlpiData` data structure
6175 * At the bottom of "nlpi_mysolver.c", you can find the interface function SCIPincludeNlpSolverXyz(),
6181 * SCIPincludeNlpSolverXyz() is called by the user (e.g., SCIP), if (s)he wants to use this solver interface in his/her application.
6194 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
6202 * The NLPIFREE callback is executed if the NLP solver interface data structure should be freed, e.g., when a SCIP instance is freed.
6207 * The callback should initialize a SCIP_NlpiProblem struct here that corresponds to an empty NLP.
6216 * The NLPIADDVARS callback is executed if a set of variables with lower and upper bounds and names should be added to a particular NLP.
6218 * If NULL is given for the lower bounds arguments, -infinity is assumed as lower bound for each new variable.
6219 * If NULL is given for the upper bounds arguments, +infinity is assumed as upper bound for each new variable.
6224 * The NLPIADDCONSTRAINTS callback is executed if a set of constraints should be added to a particular NLP.
6225 * Constraints are specified by providing left- and right-hand-sides, linear coefficients, expressions, and constraint names.
6226 * All of these arguments are optional, giving NULL for left-hand-sides corresponds to -infinity, giving NULL for right-hand-sides corresponds to +infinity.
6234 * The NLPICHGVARBOUNDS callback is executed to change the bounds on a set of variables of an NLP.
6238 * The NLPICHGCONSSIDES callback is executed to change the sides on a set of constraints of an NLP.
6243 * The caller provides an array in which for each variable it is marked whether it should be deleted.
6244 * In the same array, the function should return the new position of each variable in the NLP, or -1 if it was deleted.
6249 * The caller provides an array in which for each constraint it is marked whether it should be deleted.
6250 * In the same array, the function should return the new position of each constraint in the NLP, or -1 if it was deleted.
6254 * The NLPICHGLINEARCOEFS callback is executed to change the coefficients in the linear part of the objective function or a constraint of an NLP.
6258 * The NLPICHGEXPR callback is executed to replace the expression of the objective function or a constraint of an NLP.
6262 * The NLPICHGOBJCONSTANT callback is executed to change the constant offset of the objective function of an NLP.
6273 * The NLPIGETSOLSTAT callback can be used to request the solution status (solved, infeasible, ...) after an NLP has been solved.
6277 * The NLPIGETTERMSTAT callback can be used to request the termination reason (normal, iteration limit, ...) after an NLP has been solved.
6281 * The NLPIGETSOLUTION callback can be used to request the primal and dual solution values after an NLP solve.
6283 * It is possible to return only primal values for the variables, but no values for the dual variables, e.g., if a solver does not compute such values.
6287 * The NLPIGETSTATISTICS callback can be used to request the statistical values (number of iterations, time, ...) after an NLP solve.
6296 * The NLPICOPY callback is executed if the plugin should be copied, e.g., when a SCIP instance is copied.
6303 * The NLPIGETSOLVERPOINTER callback can be used to pass a pointer to a solver specific data structure to the user.
6308 * The NLPIGETPROBLEMPOINTER callback can be used to pass a pointer to a solver specific data structure of the NLP to the user.
6312 * The NLPISETINITIALGUESS callback is executed to provide primal and dual initial values for the variables and constraints of an NLP.
6313 * For a local solver, it is strongly advisable to implement this callback, as these values should be used as a starting point for the search.
6314 * It is possible to pass a NULL pointer for any of the arguments (primal values of variables, dual values of variable bounds, dual values of constraints).
6315 * In this case, the solver should clear previously set starting values and setup its own starting point.
6319/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
6323 * An expression interpreter is a tool to compute point-wise the function values, gradients, and
6326 * It is used, e.g., by an NLP solver interface to compute Jacobians and Hessians for the solver.
6328 * The expression interpreter interface in SCIP has been implemented similar to those of the LP solver interface (LPI).
6330 * The expression interpreter API has been designed such that it can be used independently from a SCIP problem.
6332 * A complete list of all expression interpreters contained in this release can be found \ref EXPRINTS "here".
6338 * Additional documentation for the callbacks of an expression interpreter, in particular for their input parameters,
6343 * Make sure to adjust your build system such that this file is compiled and linked to your project instead of exprinterpret implementations. \n
6344 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
6358 * In your "exprinterpret_myad.c", these functions are mostly dummy functions that return error codes.
6366 * The SCIPexprintGetDesc() function should return a short description of the expression interpreter, e.g., the name of the developer of the code.
6370 * The SCIPexprintGetCapability() function should return a bitmask that indicates the capabilities of the expression interpreter,
6375 * The SCIPexprintCreate() function is called to create an expression interpreter data structure.
6385 * The SCIPexprintCompile() function is called to initialize the data structures that are required to evaluate a particular expression.
6386 * The expression interpreter can create and return data that is particular to a given expression in the argument `exprintdata`.
6390 * The SCIPexprintFreeData() function is called to free the data that is particular to a given expression and was possibly created in SCIPexprintCompile().
6394 * The SCIPexprintGetExprCapability() function is called to request the capability to evaluate a specific expression by the expression interpreter.
6396 * In cases of user-given expressions, higher order derivatives may not be available for the user-expression,
6397 * even if the expression interpreter could handle these. This function allows to recognize that, e.g., the
6398 * Hessian for an expression is not available because it contains a user expression that does not provide
6403 * The SCIPexprintEval() function is called when the value of an expression should be computed for a point.
6407 * The SCIPexprintGrad() function is called when the gradient of an expression represented by an expression should be computed for a point.
6411 * The SCIPexprintHessianSparsity() function is called when the sparsity structure of the Hessian matrix should be computed and returned.
6412 * Only the position of nonzero entries in the lower-triangular part of Hessian should be reported.
6416 * The SCIPexprintHessian() function is called when the Hessian of an expression should be computed for a point.
6419/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
6423 * After solving a constraint integer program, SCIP can display statistics tables with information about, e.g., the solving time,
6424 * number of nodes, LP iterations or the number of calls and successes of different plugins via "display statistics" in the shell
6425 * or via SCIPprintStatistics() in the C-interface. There already exists a wide variety of statistics tables which can be activated
6426 * or deactivated on demand, see src/scip/table_default.c. Additionally, the user can implement his/her own statistics tables
6429 * A complete list of all statistics tables contained in this release can be found \ref TABLES "here".
6432 * We give the explanation for creating your own source file for each additional statistics table. Of course, you can collect
6434 * Take src/scip/table_default.c, where all default statistics tables are collected, as an example.
6435 * As all other default plugins, the default statistics table plugins and the statistics table template are written in C.
6436 * C++ users can easily adapt the code by using the scip::ObjTable wrapper base class and implement the scip_...() virtual methods
6440 * Additional documentation for the callbacks of a statistics table can be found in the file type_table.h.
6442 * Here is what you have to do to implement a statistics table (assuming your statistics table is named "mystatisticstable"):
6443 * -# Copy the template files src/scip/table_xyz.c and src/scip/table_xyz.h into files named "table_mystatisticstable.c"
6446 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
6447 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
6448 * -# Use SCIPincludeTableMystatisticstable() in order to include the statistics table into your SCIP instance,
6449 * e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
6450 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
6451 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mystatisticstable".
6461 * At the top of the new file "table_mystatisticstable.c" you can find the statistics table properties.
6463 * In the C++ wrapper class, you have to provide the statistics table properties by calling the constructor
6469 * Additionally, if you are searching for a statistics table with SCIPfindTable(), this name is looked up.
6476 * In the statistics output, the statistics tables will be ordered by increasing position. Compare with the
6477 * default statistics tables in "table_default.c" to find a value which will give you the desired position
6478 * between the default statistics tables. If you give your table a negative position value, it will appear
6479 * before all SCIP statistcs, with a value larger than 20000 it will appear after all default statistics.
6481 * \par TABLE_EARLIEST_STAGE: output of the statistics table is only printed from this stage onwards
6482 * The output routine of your statistics table will only be called if SCIP has reached this stage. For
6483 * example, the default table "tree" will only output information starting from SCIP_STAGE_SOLVING, because
6484 * there is no meaningful information available before, while the "presolver" table can already be called
6489 * Below the header "Data structures" you can find a struct which is called "struct SCIP_TableData".
6490 * In this data structure, you can store the data of your statistics table. For example, you should store the adjustable
6492 * If you are using C++, you can add statistics table data as usual as object variables to your class.
6499 * At the bottom of "table_mystatisticstable.c" you can find the interface function SCIPincludeTableMystatisticstable(), which also
6503 * It is responsible for notifying SCIP of the presence of the statistics table by calling the function
6506 * The interface function is called by the user, if (s)he wants to include the statistics table, i.e., if (s)he wants to use the statistics table in an
6509 * If you are using statistics table data, you have to allocate the memory for the data at this point.
6516 * Although this is very uncommon, you may also add user parameters for your statistics table, see the function
6517 * SCIPincludeConshdlrKnapsack() in the \ref cons_knapsack.h "knapsack constraint handler" for an example.
6524 * If the output function is not implemented, then SCIP tries to print the data that is retrieved from the collect callback in table form.
6525 * In the C++ wrapper class scip::ObjTable, the scip_output() method (which corresponds to the \ref TABLEOUTPUT callback) and
6526 * scip_collect() method (which corresponds to the \ref TABLECOLLECT callback) are virtual member functions.
6533 * The TABLEOUTPUT callback is called whenever SCIP is asked to print statistics (because the user typed "display statistics"
6534 * in the shell or called SCIPprintStatistics()). In this callback, the table should print all of its information to the given file
6537 * Typical functions called by a statistics table are, for example, SCIPdispLongint(), SCIPdispInt(), SCIPdispTime(), and
6542 * The TABLECOLLECT callback is called when the statistics table should collect its information in a SCIP_DATATREE.
6544 * To implement the TABLECOLLECT callback, `SCIPinsertDatatree*()` functions should be used to insert information
6545 * into the given SCIP_DATATREE. Currently, inserting data of different types is supported: long, double, char*,
6546 * another SCIP_DATATREE*, or arrays of long, double, and char*. See also scip_datatree.h and pub_datatree.h.
6556 * The TABLECOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback
6557 * as <code>NULL</code> the user disables the execution of the specified column. In general it is probably not needed to
6558 * implement that callback since the output of the copied instance is usually suppressed. In the other case or for
6564 * If you are using statistics table data, you have to implement this function in order to free the statistics table data.
6568 * If you have allocated memory for fields in your statistics table data, remember to free this memory
6581 * In this function, the statistics table should free all resources that have been allocated for the solving process in
6586 * The TABLEINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
6587 * begin. The statistics table may use this call to initialize its branch-and-bound specific data.
6591 * The TABLEEXITSOL callback is executed before the branch-and-bound process is freed. The statistics table should use this
6595/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
6599 * Benders' decomposition is a very popular mathematical programming technique that is applied to solve structured
6600 * problems. Problems that display a block diagonal structure are particularly amenable to the application of Benders'
6616 * The variables \f$x\f$ and \f$y\f$ are described as the first and second stage variables respectively. In the
6617 * classical use of Benders' decomposition, it is a requirement that the all second stage variables are continuous.
6618 * Extensions to the classical Benders' decomposition approach have permitted the use of more general second stage
6621 * The application of Benders' decomposition to the above problem results in a subproblem, given by
6633 * where \f$\bar{x}\f$ is a solution vector of the first stage variables. As such, the subproblem is a problem only in
6634 * \f$y\f$. The dual solution to the subproblem, either an extreme point or extreme ray, is used to generate cuts that
6635 * are added to the master problem. Let \f$\lambda\f$ be the vector of dual variables associated with the set of
6636 * constraints from the subproblem. If, for a given \f$\bar{x}\f$, the subproblem is infeasible, then \f$\lambda\f$
6643 * which eliminates \f$\bar{x}\f$ from the master problem. If, for a given \f$\bar{x}\f$, the subproblem is feasible,
6650 * where \f$\varphi\f$ is an auxiliary variable added to the master problem as an underestimator of the optimal
6653 * Given \f$\Omega^{p}\f$ and \f$\Omega^{r}\f$ as the sets of dual extreme points and rays of the subproblem,
6671 * The Benders' decomposition framework of SCIP allows the user to provide a custom implementation of many aspects of
6672 * the Benders' decomposition algorithm. It is possible to implement multiple Benders' decompositions that work in
6673 * conjunction with each other. Such a situation is where you may have different formulations of the Benders'
6676 * The current list of all Benders' decomposition implementations available in this release can be found \ref BENDERS
6680 * Take the default Benders' decomposition implementation (src/scip/benders_default.c) as an example. Same as all other
6681 * default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjBenders wrapper base
6682 * class and implement the scip_...() virtual methods instead of the SCIP_DECL_BENDERS... callbacks.
6684 * Additional documentation for the callbacks of a Benders' decomposition implementation, in particular for the
6688 * -# Copy the template files src/scip/benders_xyz.c and src/scip/benders_xyz.h into files "benders_mybenders.c" and
6691 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
6692 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
6693 * -# Use SCIPincludeBendersMybenders() in order to include the Benders' decomposition into your SCIP instance, e.g., in
6695 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
6696 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mybenders".
6701 * -# Implement the additional callbacks (see \ref BENDERS_ADDITIONALCALLBACKS). This is optional.
6706 * At the top of the new file "benders_mybenders.c", you can find the Benders' decomposition properties.
6708 * In the C++ wrapper class, you have to provide the Benders' decomposition properties by calling the constructor
6714 * Additionally, if you are searching for a Benders' decomposition with SCIPfindBenders(), this name is looked up.
6718 * This string is printed as a description of the Benders' decomposition in the interactive shell.
6721 * During the enforcement and checking of solutions in src/scip/cons_benders.c and src/scip/cons_benderslp.c, every
6722 * active Benders' decompositions are called. The execution function of the Benders' decomposition calls each of the
6723 * subproblems and generates cuts from their solutions. So the active Benders' decompositions are called in order of
6726 * The priority of the Benders' decomposition should be set according to the difficulty of solving the subproblems and
6727 * the generation of cuts. However, it is possible to prioritise the Benders' decompositions with respect to the
6730 * \par BENDERS_CUTLP: should Benders' decomposition cuts be generated during the enforcement of LP solutions.
6731 * This is a flag that is used by src/scip/cons_benders.c and src/scip/cons_benderslp.c to idicate whether the
6732 * enforcement of LP solutions should involve solving the Benders' decomposition subproblems. This should be set to TRUE
6733 * to have an exact solution algorithm. In the presence of multiple Benders' decomposition, it may be desired to enforce
6736 * \par BENDERS_CUTRELAX: should Benders' decomposition cuts be generated during the enforcement of relaxation solutions.
6737 * This is a flag that is used by src/scip/cons_benders.c and src/scip/cons_benderslp.c to idicate whether the
6738 * enforcement of relaxation solutions should involve solving the Benders' decomposition subproblems. This should be
6739 * set to TRUE to have an exact solution algorithm. In the presence of multiple Benders' decomposition, it may be desired
6740 * to enforce the relaxation solutions for only a subset of those implemented. This parameter will only take effect if
6743 * \par BENDERS_CUTPSEUDO: should Benders' decomposition subproblems be solved during the enforcement of pseudo solutions.
6744 * This is a flag that is used by src/scip/cons_benders.c and src/scip/cons_benderslp.c to indicate whether the
6745 * enforcement of pseudo solutions should involve solving the Benders' decomposition subproblems. This should be set to
6746 * TRUE, since not enforcing pseudo solutions could result in an error or suboptimal result. During the enforcement of
6747 * pseudo solutions, no cuts are generated. Only a flag to indicate whether the solution is feasible or if the LP should
6750 * \par BENDERS_SHAREAUXVARS: should this Benders' decomposition use the auxiliary variables from the highest priority
6752 * This parameter only takes effect if multiple Benders' decompositions are implemented. Consider the case that two Benders'
6753 * decompositions are implemented with different formulations of the subproblem. Since the subproblems in each of the
6754 * decomposition will have the same optimal solution, then it is useful to only have a single auxiliary variable for the
6755 * two different subproblems. This means that when an optimality cut is generated in the lower priority Benders'
6756 * decomposition, the auxiliary variable from the highest priority Benders' decomposition will be added to the right
6761 * Below the header "Data structures" you can find a struct which is called "struct SCIP_BendersData".
6762 * In this data structure, you can store the data of your Benders' decomposition. For example, you should store the adjustable
6763 * parameters of the Benders' decomposition in this data structure. In a Benders' decomposition, user parameters for the
6770 * At the bottom of "benders_mybenders.c", you can find the interface function SCIPincludeBendersMybenders(),
6772 * SCIPincludeBendersMybenders() is called by the user, if (s)he wants to include the Benders' decomposition,
6776 * It is responsible for notifying SCIP of the presence of the Benders' decomposition. For this, you can either call SCIPincludeBenders(),
6777 * or SCIPincludeBendersBasic() since SCIP version 3.0. In the latter variant, \ref BENDERS_ADDITIONALCALLBACKS "additional callbacks"
6778 * must be added via setter functions as, e.g., SCIPsetBendersCopy(). We recommend this latter variant because
6779 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
6780 * variant must be manually adjusted with every SCIP release containing new callbacks for Benders' decompositions in order to compile.
6787 * You also have to initialize the fields in "struct SCIP_BendersData" afterwards. For freeing the
6790 * You may also add user parameters for your Benders' decomposition, see \ref PARAM for how to add user parameters and
6793 * It is advised to disable presolving for the Benders' decomposition master problem by calling SCIPsetPresolving() with
6794 * the parameter SCIP_PARAMSETTING_OFF. Presolving should be disabled because reductions on the master problem could be
6795 * invalid since constraints have been transferred to the subproblems. It is not necessary to disable all presolving,
6798 * The Benders' decomposition constraint handler, see src/scip/cons_benders.c, includes a presolver for tightening the
6799 * bound on the auxiliary variables. This presolver can be enabled with by setting "presolving/maxround" to 1 and
6800 * "constraints/benders/maxprerounds" to 1. This presolver solves the Benders' decomposition subproblems without fixing
6806 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
6808 * They are passed together with the Benders' decomposition itself to SCIP using SCIPincludeBenders() or SCIPincludeBendersBasic(),
6811 * Benders' decomposition plugins have two callbacks, @ref BENDERSGETVAR and @ref BENDERSCREATESUB that must be implemented.
6818 * The BENDERSGETVAR callback provides a mapping between the master problem variables and their corresponding subproblem
6819 * variables, and vice versa. The parameters of this function include the variable for which the mapped variable is
6820 * desired and the problem number for the mapped variable. When requesting a subproblem variable for a given master
6821 * problem variable, the master variable is input with the appropriate subproblem index. If a master problem variable is
6822 * requested for a given subproblem variable, then the subproblem variable is input with the subproblem index given as
6825 * An example of how to implement the mapping between the master and subproblem variables is shown by
6829 * In the above code snippet, the hashmaps providing the mapping between the master and subproblem variables are
6832 * The requested variable is returned via the mappedvar parameter. There may not exist a corresponding master
6833 * (subproblem) variable for every input subproblem (master) variable. In such cases were no corresponding variable
6836 * The mapped variables are retrieved by calling SCIPgetBendersMasterVar() and SCIPgetBendersSubproblemVar().
6838 * The variable mapping must be created before <code>SCIP_STAGE_PRESOLVE</code> stage. This is because the variable
6843 * The BENDERSCREATESUB callback is executed during the <code>SCIP_STAGE_INIT</code> stage. In this function, the
6844 * user must register the SCIP instances for each subproblem. The BENDERSCREATESUB callback is executed once for each
6847 * It is possible to build the SCIP instance for the subproblem during the execution of this callback. However, it may
6848 * be more convenient to build the subproblem instances during the problem creation stage of the master problem and
6849 * store the subproblem SCIP instances in SCIP_BendersData. This approach is used in src/scip/benders_default.c.
6851 * @section BENDERS_ADDITIONALCALLBACKS Additional Callbacks of a Benders' decomposition implementation
6853 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
6854 * implemented for most applications, they can be used, for example, to initialize and free private data.
6855 * Additional callbacks can either be passed directly with SCIPincludeBenders() to SCIP or via specific
6856 * <b>setter functions</b> after a call of SCIPincludeBendersBasic(), see also @ref BENDERS_INTERFACE.
6860 * If you are using Benders' decomposition data (see \ref BENDERS_DATA and \ref BENDERS_INTERFACE), you have to
6861 * implement this function in order to free the Benders' decomposition data. This can be done by the following procedure:
6865 * If you have allocated memory for fields in your Benders' decomposition data, remember to free this memory
6879 * If a user wishes to employ the Large Neighbourhood Benders' Search, it is necessary for the BENDERSCOPY callback to
6880 * be implemented. This is required because the sub-SCIP instances of large neighbourhood search heuristics can only
6886 * The Benders' decomposition implementation may, e.g., use this call to initialize its Benders' decomposition data. In
6887 * src/scip/benders_default.c BENDERSINIT is used to create the mapping between the master and subproblem variables.
6894 * In this function, the Benders' decomposition implementation should free all resources that have been allocated for
6899 * The BENDERSINITPRE callback is executed before the preprocessing is started, even if presolving is turned off.
6900 * The Benders' decomposition may use this call to initialize its presolving data before the presolving process begins.
6904 * The BENDERSEXITPRE callback is executed after the preprocessing has been finished, even if presolving is turned off.
6905 * The Benders' decomposition implementation may use this call, e.g., to clean up its presolving data.
6910 * The BENDERSINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
6911 * begin. The Benders' decomposition implementation may use this call to initialize its branch-and-bound specific data.
6915 * The BENDERSEXITSOL callback is executed before the branch-and-bound process is freed. The Benders' decomposition
6920 * The BENDERSPRESUBSOLVE callback is provided to give the user an opportunity in each iteration to perform any setup
6921 * operations prior to solving the subproblems. This callback also allows the user to skip the subproblem solve for the
6923 * - the subproblem was not solved in this iteration. Other decompositions will be checked (SCIP_DIDNOTRUN).
6924 * - a constraint has been added to the master problem. No other decompositions will be checked (SCIP_CONSADDED).
6925 * - a cut has been added to the master problem. No other decompositions will be checked (SCIP_SEPARATED).
6926 * - feasibility of the solution is reported to SCIP. Other decompositions will be checked (SCIP_FEASIBLE).
6927 * - infeasibility of the solution is reported to SCIP. No other decompositions will be checked (SCIP_INFEASIBLE).
6931 * Two different subproblem solving functions are provide in the Benders' decomposition framework, BENDERSSOLVESUBCONVEX
6932 * and BENDERSSOLVESUB. These two solving functions are used in the two solving loops of the Benders' decomposition
6933 * framework. The first solving loop solves convex subproblems and convex relaxations of CIPs. The BENDERSSOLVESUBCONVEX
6934 * callback is executed only during the FIRST solving loop. Benders' cut generating functions suitable for convex
6935 * subproblems are executed during this solving loop. If a cut is found, then the second solve loop is not executed. If
6936 * your decomposition does not have any convex subproblems, then it is not necessary to implement the
6937 * BENDERSSOLVESUBCONVEX callback. However, it may be computationally beneficial to solve the convex relaxation of CIP
6942 * If you implement the BENDERSSOLVESUBCONVEX callback, it is necessary to implement the BENDERSFREESUB callback.
6944 * The objective function value after the subproblem solve and the result must be returned. The permissible results
6953 * The BENDERSSOLVESUB is executed only during the SECOND solve loop. This callback is used to solve CIP
6954 * subproblems. If your decomposition does not have any CIP subproblems, then it is not necessary to implement the
6957 * If you implement the BENDERSSOLVESUB callback, it is necessary to implement the BENDERSFREESUB callback.
6959 * The objective function value after the subproblem solve and the result must be returned. The permissible results
6968 * The BENDERSPOSTSOLVE callback is executed after the subproblems have been solved and any required cuts have been
6969 * generated, but before the subproblems are freed. This callback provides the user an opportunity to interact the
6970 * subproblems at a global level. For example, the user is able to construct a solution to the original problem by
6973 * Additionally, the user is able to merge subproblems into the master problem during the execution of this callback.
6974 * The merging of subproblems into the master problem could be desired if it is too time consuming to satisfy the
6975 * feasibility of a subproblem or the appropriate cutting functions are not available for the provided subproblem. A list
6976 * of indicies of subproblems suitable for merging are given in the mergecands array. The first npriomergecands are the
6977 * merge candidates that must be merged into the master problem. If they are not, then the solution process will
6978 * terminate with an error. These merge candidates arise if a cut could not be generated due to numerical difficulties.
6979 * The remaining nmergecands - npriomergecands are subproblems that could be merged into the master problem if desired
6984 * The BENDERSFREESUB callback is executed to clean up the subproblems after the solving process and prepare them for
6985 * the next iteration. Typically, SCIPfreeTransform() is called for each subproblem to free the transformed problem.
6989/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
6993 * The Benders' decomposition framework of SCIP allows the user to provide a custom implementation of cut generation
6994 * method. The Benders' decomposition cut methods are linked to the Benders' decomposition implementations, not the
6995 * master problem SCIP instance. As such, you are able to have different Benders' decomposition cut methods for each
6997 * The current list of all Benders' decomposition cut generation methods available in this release can be found
7000 * We now explain how users can add their own Benders' decomposition cut methods. Take the default Benders'
7001 * decomposition cut method (src/scip/benderscut_opt.c) as an example. This Benders' decomposition cut method generates
7002 * a classical optimality cut from the optimal dual solution to the convex relaxation of the Benders' decomposition
7003 * subproblem. Same as all other default plugins, it is written in C. C++ users can easily adapt the code by using the
7004 * scip::ObjBenderscut wrapper base class and implement the scip_...() virtual methods instead of the
7007 * Additional documentation for the callbacks of a Benders' decomposition cut methods, in particular for the
7011 * -# Copy the template files src/scip/benderscut_xyz.c and src/scip/benderscut_xyz.h into files "benderscut_mybenderscut.c" and
7014 * Make sure to adjust your build system such that these files are compiled and linked to your project. \n
7015 * If you are adding a new default plugin, this means updating the `src/CMakeLists.txt` and `Makefile` files in the SCIP distribution.
7016 * -# Use SCIPincludeBenderscutMybenderscut() in order to include the Benders' decomposition cut method into your SCIP
7017 * instance, e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example). \n
7018 * If you are adding a new default plugin, this include function must be added to `src/scipdefplugins.c`.
7019 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mybenderscut".
7024 * -# Implement the additional callbacks (see \ref BENDERSCUT_ADDITIONALCALLBACKS). This is optional.
7029 * At the top of the new file "benderscut_mybenderscut.c", you can find the Benders' decomposition cut methods
7031 * In the C++ wrapper class, you have to provide the Benders' decomposition properties by calling the constructor
7037 * Additionally, if you are searching for a Benders' decomposition cut method with SCIPfindBenderscut(), this name is
7038 * looked up. Names have to be unique: no two Benders' decomposition cut methods linked to the same Benders'
7042 * This string is printed as a description of the Benders' decomposition cut method in the interactive shell.
7045 * In each of the Benders' decomposition subproblem solving loops, the included Benders' decomposition cut methods are
7046 * called in order of priority. The priority is important because once a cut is generated for a subproblem, no other
7049 * The priority of the Benders' decomposition should be set according to the order in which the cut should be generated.
7050 * For example, the priority of the included cuts attempt to generation feasibility cuts (src/scip/benderscut_feas.c
7053 * \par BENDERSCUT_LPCUT: Can this cut be applied to convex subproblems and convex relaxations of CIP subproblems?
7054 * Since the Benders' decomposition framework executes two different solving loops, one for convex subproblems and the
7055 * other for CIP subproblems, the Benders' decomposition cut methods must be partitioned by their suitability for each
7056 * subproblem type. If BENDERSCUT_LPCUT is set to TRUE, then this cut is only applied to convex subproblems and convex
7061 * Below the header "Data structures" you can find a struct which is called "struct SCIP_BenderscutData".
7062 * In this data structure, you can store the data of your Benders' decomposition. For example, you should store the adjustable
7063 * parameters of the Benders' decomposition in this data structure. In a Benders' decomposition, user parameters for the
7070 * At the bottom of "benderscut_mybenderscut.c", you can find the interface function SCIPincludeBenderscutMybenderscut(),
7072 * SCIPincludeBenderscutMybenderscut() is called by the user, if (s)he wants to include the Benders' decomposition,
7076 * It is responsible for notifying SCIP of the presence of the Benders' decomposition. For this, you can either call SCIPincludeBenderscut(),
7077 * or SCIPincludeBenderscutBasic() since SCIP version 3.0. In the latter variant, \ref BENDERSCUT_ADDITIONALCALLBACKS "additional callbacks"
7078 * must be added via setter functions as, e.g., SCIPsetBenderscutCopy(). We recommend this latter variant because
7079 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
7080 * variant must be manually adjusted with every SCIP release containing new callbacks for Benders' decompositions in order to compile.
7087 * You also have to initialize the fields in "struct SCIP_BenderscutData" afterwards. For freeing the
7090 * You may also add user parameters for your Benders' decomposition, see \ref PARAM for how to add user parameters and
7094 * @section BENDERSCUT_FUNDAMENTALCALLBACKS Fundamental Callbacks of a Benders' decomposition cut function
7096 * The fundamental callbacks of the plugins are the ones that have to be implemented in order to obtain
7098 * They are passed together with the Benders' decomposition itself to SCIP using SCIPincludeBenderscut() or SCIPincludeBenderscutBasic(),
7101 * Benders' decomposition cut methods have only one callback, @ref BENDERSCUTEXEC, that must be implemented.
7108 * The BENDERSCUTEXEC callback is called during the cut generation process within the Benders' decomposition subproblem
7109 * solving loop. This function must generate a cut for the given subproblem if the associated subsystem is not optimal
7112 * When generating cuts, it is possible to store these within the SCIP_BendersData of the associated Benders'
7113 * decomposition. This is achieved by calling SCIPstoreBenderscutCons() (SCIPstoreBenderscutCut() if the Benders'
7114 * decomposition cut is added as a cutting plane instead as a constraint). The storing of cuts can be useful when using
7115 * the large neighbourhood Benders' search, where the cut generated in the sub-SCIP solve are transferred to the main
7118 * The BENDERSCUTEXEC callback must return the result of the cut generation. The permissable results are:
7120 * - if the Benders' cut was run, but there was an error in generating the cut (SCIP_DIDNOTFIND).
7121 * - if the Benders' decomposition cut algorithm has not generated a constraint or cut (SCIP_FEASIBLE).
7122 * - an additional constraint for the Benders' decomposition cut was generated (SCIP_CONSADDED).
7123 * - a cutting plane representing the Benders' decomposition cut was generated (SCIP_SEPARATED).
7125 * If the BENDERSCUTEXEC callback returns SCIP_DIDNOTFIND due to an error in the cut generation, if no other subproblems
7126 * generate a cut during the same iteration of the Benders' decomposition algorithm, then this could result in an
7127 * error. It is possible to avoid the error by merging the subproblem into the master problem (see \ref
7132 * The additional callbacks do not need to be implemented in every case. However, some of them have to be
7133 * implemented for most applications, they can be used, for example, to initialize and free private data.
7134 * Additional callbacks can either be passed directly with SCIPincludeBenderscut() to SCIP or via specific
7135 * <b>setter functions</b> after a call of SCIPincludeBenderscutBasic(), see also @ref BENDERSCUT_INTERFACE.
7139 * If you are using Benders' decomposition cut data (see \ref BENDERSCUT_DATA and \ref BENDERSCUT_INTERFACE), you have
7142 * If you have allocated memory for fields in your Benders' decomposition cut data, remember to free this memory
7156 * If the Benders' decomposition cuts are included by calling SCIPincludeBendersDefaultCuts() in the include function of
7157 * the Benders' decomposition implementation, such as SCIPincludeBendersDefault(), then it is not necessary to implement
7158 * BENDERSCUTCOPY. The copy function could be implemented to copy Benders' decomposition cut data from the original SCIP
7164 * The BENDERSCUTINIT callback is executed after the problem is transformed The Benders' decomposition cut method may,
7165 * e.g., use this call to initialize its Benders' decomposition cut data. The difference between the original and the
7166 * transformed problem is explained in "What is this thing with the original and the transformed problem about?" on \ref
7171 * The BENDERSCUTEXIT callback is executed before the transformed problem is freed. In this function, the Benders'
7172 * decomposition cut method should free all resources that have been allocated for the solving process in
7177 * The BENDERSCUTINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
7178 * begin. The Benders' decomposition implementation may use this call to initialize its branch-and-bound specific data.
7182 * The BENDERSCUTEXITSOL callback is executed before the branch-and-bound process is freed. The Benders' decomposition
7186/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7190 * Conflict analysis is a way to automatically use the information obtained from infeasible nodes
7193 * Once a node is declared infeasible, SCIP automatically tries to infer a constraint that explains the reason for the
7194 * infeasibility, in order to avoid similar situations later in the search. This explanation essentially consists of a
7195 * constraint stating that at least one of its variables should have a bound different from the current infeasible node,
7196 * because the current setting led to infeasibility. Clearly, all variables that are fixed in the current infeasible
7197 * node would yield such a constraint (since this leads to infeasibility). The key point rather is to infer a "small"
7198 * constraint that does the same job. SCIP handles this by several heuristics. For this, SCIP sets up a
7199 * so-called (directed) conflict graph. The nodes in this graph correspond to bound changes of variables and an arc (@a
7200 * u, @a v) means that the bound change corresponding to @a v is based on the bound change of @a u. In general, a node
7201 * will have several ingoing arcs which represent all bound changes that have been used to infer (propagate) the bound
7202 * change in question. The graph also contains source nodes for each bound that has been changed during branching and an
7203 * artificial target node representing the conflict, i.e., the infeasibility. Essentially, SCIP heuristically constructs
7204 * a cut in this graph that involves few "branching nodes". For details on the techniques that SCIP uses,
7212 * -# If one detects infeasibility, one should initiate conflict analysis, see \ref INITCONFS "below".
7216 * If this functionality is not implemented, SCIP will still work correctly, but cannot use the information of the constraint
7217 * handler or the propagator for conflict analysis. In this case, each bound reduction performed by the constraint
7224 * -# Inform SCIP about the variable bounds that are the reason for the detection of infeasibility
7226 * SCIPaddConflictBinvar(). If there is more than one valid explanation of infeasibility, either one can be used.
7228 * -# Call SCIPanalyzeConflict() from a propagator or SCIPanalyzeConflictCons() from a constraint
7235 * When propagating variable domains, SCIP needs to be informed that the deduced variable bounds should be
7237 * SCIPinferVarUbCons(), and SCIPinferBinvarCons() for constraint handlers and SCIPinferVarLbProp(),
7244 * Reverse Propagation is used to build up the conflict graph. Essentially, it provides an algorithm to detect the arcs
7245 * leading to a node in the conflict graph, i.e., the bound changes responsible for the new bound change deduced during
7248 * These callbacks receive the following information: the variable which is under investigation (@p
7249 * infervar), the corresponding bound change (@p bdchgidx, @p boundtype), and the integer (@p inferinfo) that has been
7252 * One can use SCIPgetVarUbAtIndex() or SCIPgetVarLbAtIndex() to detect the bounds before or after the propagation that
7253 * should be investigated. Then the bounds that were involved should be passed to SCIP via SCIPaddConflictLb() and
7254 * SCIPaddConflictUb(). If there is more than one valid explanation of infeasibility, either one can be used.
7264 * (see @p example/LOP directory). This constraint handler propagates the equations \f$x_{ij} + x_{ji} =
7267 * When propagating the equation and <code>vars[i][j]</code> is fixed to 1, the constraint handler uses
7269 * SCIP_CALL( SCIPinferBinvarCons(scip, vars[j][i], FALSE, cons, i*n + j, &infeasible, &tightened) );
7271 * Thus, variable <code>vars[j][i]</code> is fixed to 0 (@p FALSE), and it passes <code>i*n + j </code> as @p inferinfo.
7273 * When it propagates the triangle inequality and both <code>vars[i][j]</code> and <code>vars[j][k]</code>
7276 * SCIP_CALL( SCIPinferBinvarCons(scip, vars[k][i], FALSE, cons, n*n + i*n*n + j*n + k, &infeasible, &tightened) );
7278 * Thus, in this case, variable <code>vars[k][i]</code> is fixed to 0 and <code>n*n + i*n*n + j*n + k</code> is
7281 * In reverse propagation, the two cases can be distinguished by @p inferinfo: if it is less than @p n*n,
7282 * we deal with an equation, otherwise with a triangle inequality. The constraint handler can then extract the
7285 * In the first case, it has to distinguish whether <code>vars[i][j]</code> is fixed to 0 or 1 –
7287 * or SCIPaddConflictUb(), respectively, with variable <code>vars[j][i]</code>. In the second case, it is clear that the only
7288 * possible propagation is to fix <code>vars[i][j]</code> to 0 when both <code>vars[k][i]</code> and <code>vars[j][k]</code>
7293/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7297 * The reoptimization feature of SCIP can be used to solve a sequence of optimization problems \f$(P_{i})_{i \in I}\f$ with
7299 * (P_i) \quad \min \{ c_i^T x \;|\; A^ix \geq b^i,\; x_{j} \in \mathbb{Z}\;\forall j \in \mathcal{I} \}
7301 * such that between two problems \f$P_i\f$ and \f$P_{i+1}\f$ the space of solutions gets restricted and/or the objective
7302 * function changes. To use reoptimization the user has to change the parameter <code>reoptimization/enable</code> to
7303 * <code>TRUE</code> before the solving process of the first problem of the sequence starts, i.e., in stage
7304 * <code>SCIP_STAGE_INIT</code> or <code>SCIP_STAGE_PROBLEM</code>. This can be done via the interactive shell or by
7305 * calling SCIPenableReoptimization(). In both cases SCIP changes some parameters and fixes them:
7307 * -# set the limit <code>maxorigsol</code> of stored solutions to zero because this is handled by a special solution tree provided
7311 * -# disable dual reductions within presolvers and propagators (<code>misc/allowdualreds = FALSE</code>)
7314 * In contrast to the presolving and propagating functions that are using dual information, performing strong branching is
7315 * allowed. The bound tightenings resulting from strong branching are handeled in a special way. After changing the objective
7316 * function and solving the modified problem the feasible region that was pruned by strong branching will be reconstructed
7319 * If the reoptimization feature is enabled SCIP tries to reuse the search tree, especially the search frontier at the end
7320 * of the solving process, to speed up the solving process of the following problems. Therefore, the current release
7321 * provides the branching rule <code>branch_nodereopt</code> to reconstruct the tree. SCIP triggers a restart of the
7334 * Before SCIP discards all the stored information and solves the problem from scratch it tries to compress the search
7335 * tree. Therefore, the current release provides compression heuristics that try to find a good and much smaller
7338 * After a problem in the sequence of optimization problems was solved, the objective function can be changed in two ways:
7339 * -# Using the provided reader <code>reader_diff</code> the objective function can be changed via using the interactive
7345 * -# The objective function can be changed within the code. Therefore, the transformed problem needs to be freed by
7346 * calling SCIPfreeReoptSolve(). Afterwards, the new objective function can be installed by calling
7351 * \note Currently, the compression heuristics used between two successive reoptimization runs only support pure binary
7360/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7366 * In \SCIP 4.0 a new feature has been added that allows to run multiple \SCIP instances with different settings
7367 * on one problem in parallel. To use this feature \SCIP has to be compiled with an additional make option to
7369 * Then, a concurrent solve can be started by using the <code>concurrentopt</code> command instead of the <code>optimize</code> command
7371 * To configure the behavior of the concurrent solving mode there are new parameters in the category <code>concurrent/</code>
7376 * The parameters <code>parallel/maxnthreads</code> and <code>parallel/minnthreads</code> can be used to configure the number of threads
7377 * that sould be used for solving. \SCIP will try to use the configured maximum number of threads. If the
7378 * problem that is currently read is too large \SCIP will automatically use fewer threads, but never
7383 * The parameters <code>concurrent/scip.../prefprio</code> configure which concurrent solvers should be used.
7384 * The concurrent solver <code>scip</code> will use the same settings as the \SCIP instance configured by the user.
7385 * The other concurrent solvers, e.g. <code>scip-feas</code>, will load the corresponding emphasis setting.
7386 * The behavior of the prefprio parameter is as follows: If it is set to 1.0 for <code>scip-feas</code> and
7387 * <code>scip-opti</code>, and to 0.0 for every other concurrent solver, then the threads will be evenly
7388 * distributed between the two types <code>scip-feas</code> and <code>scip-opti</code>. An example: if 4 threads are used each of these concurrent
7389 * solvers will use 2 threads. If the <code>prefprio</code> for one solver is set to 0.33 and the other is set to 1.0, then the former will use 1 thread
7394 * To use custom settings for the concurrent solvers there is the parameter <code>concurrent/paramsetprefix</code>. If custom parameters
7395 * should be loaded by the concurrent solvers, then it must point to the folder where they are located (including a path separator at the end).
7396 * The parameter settings must be named after the concurrent solvers, e.g. if only the concurrent solver <code>scip</code> is used
7397 * they should be named <code>scip-1</code>, <code>scip-2</code>, <code>scip-3</code>. When different types of concurrent solvers are used the counter
7401/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7405 * It is a common problem for integer programming practitioners to (unexpectedly) encounter infeasible instances.
7406 * Often it desirable to better understand exactly why the instance is infeasible. Was it an error in the
7407 * input data, was the underlying formulation incorrect, or is my model simply infeasible by construction?
7411 * This produces an infeasible problem, which contains a subset of constraints and variable bounds from
7412 * the original problem. The infeasible problem is also irreducible, in that removing any additional
7413 * constraints results in the problem becoming feasible. This is a fantastic method for debugging
7414 * problems, and for determining what needs to be changed in the formulation. To use this functionality
7428 * Secondly there is the MinUC (minimize number of unsatisfied constraints) functionality in SCIP.
7429 * This produces a minimum set of constraints, such that if those constraints were relaxed, the original
7437 * unsatisfied constraints. The primal bound during solving corresponds to current best solution,
7440 * have value 1. The variables in the new problem have naming conventions `originalconsname_master`.
7448/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7452 * Most mixed-integer programs have sparse constraint matrices in the sense that most columns and rows have only very few nonzero entries,
7454 * A decomposition identifies subproblems (subsets of rows and columns) that are only linked to each other via a set of linking rows and/or linking
7456 * The special case of completely independent subproblems (with no linking rows and columns), for example, can be solved by solving
7458 * This case has already been integrated into SCIP as a successful presolving technique (see @ref cons_components.c).
7459 * Another use of decomposition within SCIP is the @ref BENDDECF "Benders Decomposition framework".
7461 * Since SCIP 7.0, it is easier to pass user decompositions to SCIP that can be used within Benders decomposition or by user algorithms.
7466 * In the following, we present decompositions of mixed-integer programs. However, the generalization to Constraint Integer Programs is straightforward.
7468 * Concretely, for \f$k \geq 0\f$ we call a partition \f$\mathcal{D}=(D^{\text{row}},D^{\text{col}})\f$ of the rows and columns of the constraint matrix \f$A\f$ into \f$k + 1\f$ pieces each,
7471 * D^{\text{row}} = (D^{\text{row}}_{1},\dots,D^{\text{row}}_{k},L^{\text{row}}), \quad D^{\text{col}} = (D^{\text{col}}_{1},\dots,D^{\text{col}}_{k},L^{\text{col}})
7473 * a decomposition of \f$A\f$ if \f$D^{\text{row}}_{q} \neq \emptyset\f$, \f$D^{\text{col}}_{q} \neq \emptyset\f$ for \f$q \in \{1,\dots,k\}\f$ and if it holds for all \f$i\in D^{\text{row}}_{q_{1}}, j\in D^{\text{col}}_{q_{2}}\f$ that \f$a_{i,j} \neq 0 \Rightarrow q_{1} = q_{2}\f$.
7474 * The special rows \f$L^{\text{row}}\f$ and columns \f$L^{\text{col}}\f$, which may be empty, are called linking rows and linking columns, respectively.
7538 * After passing one or more decompositions, see below, one can access all available decompositions with SCIPgetDecomps().
7539 * The labels can be obtained by calling SCIPdecompGetVarsLabels() and SCIPdecompGetConsLabels().
7540 * If some variables/constraints are not labeled, these functions will mark them as linking variables/constraints.
7541 * There are several functions to get more information about one decomposition, see @ref DecompMethods.
7543 * A decomposition can be used to split the problem into several subproblems which, in general, are easier to solve.
7546 * A_{[D^{\text{row}}_{q},D^{\text{col}}_{q}]}\; x_{[D^{\text{col}}_{q}]} \geq b_{[D^{\text{row}}_{q}]}
7548 * is part of subproblem \f$q\f$, the handling of the linking variables/constraints depends on the chosen application context.
7549 * For example, in the heuristic @ref heur_padm.c several smaller subproblems are solved multiple times to get a feasible solution.
7550 * Also the @ref BENDDECF "Benders' decomposition framework" was extended with release 7.0 to use user decompositions.
7557 * To create it with the API, the user must first create a decomposition with SCIPcreateDecomp() specifying
7558 * whether the decomposition belongs to the original or transformed problem and the number of blocks.
7559 * Then the variables and constraints can be assigned to one block or to the linking rows/columns by calling
7561 * To complete the decomposition or to ensure that it is internally consistent, SCIPcomputeDecompVarsLabels() or
7563 * Note that SCIPcomputeDecompVarsLabels() will ignore the existing variable labels and computes again the labels based on the constraint labels only;
7564 * SCIPcomputeDecompConsLabels() works in the same way and ignores the existing constraint labels.
7566 * After the decomposition has been successfully created, it can be saved for later use in the DecompStore using SCIPaddDecomp().
7571 * Alternatively, after a problem has been read, a related decomposition can be read from a dec-file.
7572 * Please refer to the @ref reader_dec.h "DEC file reader" for further information about the required file format.
7573 * Upon reading a valid dec-file, a decomposition structure is created, where the corresponding variable labels are inferred from the constraint labels, giving precedence to block over linking constraints.
7577 * If the variables should be labeled for the application of @ref BENDDECF "Benders' decomposition", the decomposition must be explicitly flagged by setting the parameter decomposition/benderslabels to TRUE.
7578 * With this setting, the variable's labeling takes place giving precedence to its presence in linking constraints over its presence in named blocks.
7582 * As the problem's constraints are constantly changing, or possibly deleted, during presolving, the constraints' labeling must be triggered again.
7583 * Therefore, SCIP automatically transforms all user decompositions at the beginning of the root node based on the variables' labels.
7587 * Further useful measures and statistics about the decomposition are computed within SCIPcomputeDecompStats().
7593 * This score is also used by GCG to rank decompositions during the automatic detection procedure.
7599 * \lvert D^{\text{col}}_{q} \rvert + n\lvert L^{\text{row}} \rvert + m\lvert L^{\text{col}} \rvert -
7603 * In the case of a mixed-integer program, the area score intuitively measures the coverage of the rearranged matrix by 0's.
7604 * Decompositions with few linking variables and/or constraints and many small blocks \f$A_{[D^{\text{row}}_{q},D^{\text{col}}_{q}]}\f$
7605 * will have an area score close to \f$1\f$, whereas coarse decompositions of a matrix have smaller area scores.
7608 * This measure is used to assess the quality of the community structure within a decomposition.
7615 * where \f$e_{q}\f$ is the number of inner edges within block \f$q\f$ and \f$m\f$ is the total number of edges.
7616 * The presence of an inner edge is identified through the presence of a variable in a constraint,
7618 * - the block graph statistics: A block graph is constructed with the aim of depicting the connection between the different blocks in a decomposition through the existing linking variables in the constraints.
7621 * Each vertex in the graph represents a block in the decomposition; \f$V = \{v_{1},\dots,v_{k}\}\f$.
7622 * An edge \f$e = \{ v_{s},v_{t} \}\f$ is added to \f$G\f$, if and only if there exists a column \f$\ell \in L^{\text{col}}\f$, a row \f$i \in D^{\text{row}}_{s}\f$
7623 * and a row \f$j \in D^{\text{row}}_{t}\f$, such that \f$a_{i,\ell} \neq 0\f$ and \f$a_{j,\ell} \neq 0\f$.
7624 * From the constructed graph, the number of edges, articulation points and connected components are computed, together with the maximum and minimum degree.
7625 * Note that building the block graph can become computationally expensive with large and dense decompositions.
7626 * Thus, it is possible through a user parameter <code>decomposition/maxgraphedge</code> to define a maximum edge limit.
7627 * The construction process will be interrupted once this limit is reached, in which case only approximate estimations of the block graph statistics will be displayed and accompanied with a warning message.
7631/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7636 * Benders' decomposition is a very popular mathematical programming technique that is applied to solve structured
7637 * problems. Problems that display a block diagonal structure are particularly amenable to the application of Benders'
7653 * The variables \f$x\f$ and \f$y\f$ are described as the first and second stage variables respectively. In the
7654 * classical use of Benders' decomposition, it is a requirement that the all second stage variables are continuous.
7655 * Extensions to the classical Benders' decomposition approach have permitted the use of more general second stage
7658 * The application of Benders' decomposition to the above problem results in a subproblem, given by
7670 * where \f$\bar{x}\f$ is a solution vector of the first stage variables. As such, the subproblem is a problem only in
7671 * \f$y\f$. The dual solution to the subproblem, either an extreme point or extreme ray, is used to generate cuts that
7672 * are added to the master problem. Let \f$\lambda\f$ be the vector of dual variables associated with the set of
7673 * constraints from the subproblem. If, for a given \f$\bar{x}\f$, the subproblem is infeasible, then \f$\lambda\f$
7680 * which eliminates \f$\bar{x}\f$ from the master problem. If, for a given \f$\bar{x}\f$, the subproblem is feasible,
7687 * where \f$\varphi\f$ is an auxiliary variable added to the master problem as an underestimator of the optimal
7690 * Given \f$\Omega^{p}\f$ and \f$\Omega^{r}\f$ as the sets of dual extreme points and rays of the subproblem,
7723 * - the subproblem is convex: \f$g_i(x,y)\f$ convex on \f$X\times Y\f$ if \f$u_i<\infty\f$, \f$g_i(x,y)\f$ concave on \f$X\times Y\f$ if \f$\ell_i>-\infty\f$, and \f$Y=\mathbb{R}^m\f$, or
7727 * ways: inputting an instance in the SMPS file format, using the default Benders' decomposition implementation
7728 * (see src/scip/benders_default.c), implementing a custom Benders' decomposition plugin (see \ref BENDER), or by using
7734 * As part of the Benders' decomposition framework development, a reader for instances in the SMPS file format has been
7735 * implemented (see src/scip/reader_smps.c). The details regarding the SMPS file format can be found at:
7742 * - A core file (.cor): a problem instance in MPS format that is the core problem of a stochastic program.
7743 * - A time file (.tim): partitions the variables and constraints into the different stages of the stochastic program
7746 * The STO reader (see src/scip/reader_sto.c) constructs the stochastic program using the information from the core and
7747 * time files. By default, the STO reader will construct the deterministic equivalent of the stochastic program. A
7748 * parameter is provided "reading/sto/usebenders" that will inform the STO reader to apply Benders' decomposition to the
7753 * Benders' decomposition can be applied from a user-provided decomposition structure. Details about the decomposition
7754 * structure and how to provide it to SCIP can be found at @ref DECOMP. Prior to reading the decomposition structure
7755 * into SCIP, it is necessary to inform SCIP that the variables and constraints must be labelled for Benders'
7756 * decomposition. This is achieved by setting the parameter "decomposition/benderslabels" to "TRUE". Following this,
7757 * Benders' decomposition will be applied if the parameter "decomposition/applybenders" is set to "TRUE".
7759 * When Benders' decomposition is applied using the decomposition structure, the Benders' decomposition algorithm is
7760 * executed within a relaxator (see @ref RELAX). The relaxator is called when processing the root node of the original
7761 * SCIP instance, before the first LP solve. Within the relaxator, a sub-SCIP is created, upon which the Benders'
7762 * decomposition is applied. The default Benders' decomposition plugin (see @ref BENDERSDEFAULT) is used for applying
7763 * the decomposition. The master problem sub-SCIP is solved and then the solution from the Benders' decomposition
7766 * If the problem is solved to optimality by the Benders' decomposition algorithm, then the original SCIP instance
7767 * terminates. There are cases where the Benders' decomposition algorithm terminates without an optimal solution. As a
7768 * result, the original SCIP instance would continue solving. These cases are: reaching node, memory or solution limits,
7769 * or numerical issues meaning that the Benders' solution is not optimal for the original problem. The parameter
7770 * "relaxing/benders/continueorig" is provided to inform SCIP whether the original SCIP instance should continue solving
7771 * following the completion of the Benders' algorithm. By default, solving in the original SCIP instance is interrupted
7774 * The parameter setting and limits from the original SCIP instance are copied across to the master problem
7775 * sub-SCIP in the Benders' decomposition relaxator. It is possible to set a separate node limit for the Benders'
7776 * algorithm within the relaxator. This is achieved by using the parameter "relaxing/benders/nodelimit". A possible use
7777 * case for a separate Benders' node limit is that the Benders' algorithm could be used as an initial heuristics for the
7780 * An advantage over using the decomposition structure compared to an instance in the SMPS format is that the solution
7781 * to the original problem is easily accessible. At the completion of the Benders' decomposition algorithm, the best
7782 * know solution is copied back to the original SCIP instance. Note that using a decomposition structure is not the only
7783 * way to get the original problem solution from the Benders' decomposition algorithm. Whichever method you use, it is
7784 * possible to solve the Benders' decomposition subproblems by calling SCIPsetupBendersSubproblem() and then
7785 * SCIPsolveBendersSubproblem() for each subproblem using the best solution from the master problem. An example of this
7790 * A default implementation of a Benders' decomposition plugin has been included in \SCIP 6.0 (see
7791 * src/scip/benders_default.c). In order to use the default plugin, the user must create SCIP instances of the master
7792 * problem and subproblems. The subproblems must also contain a copy of the master problem variables, since these are
7793 * fixed to the master problem solution values during the subproblem solving loop. These SCIP instances for the master
7796 * The mapping between the master and subproblem variables is performed automatically. The default solving and cut
7797 * generation methods are applied to solve the input problem. It is important to note that the mapping between the
7798 * master and subproblem variables relies on the variable names. The variables of the subproblem corresponding to
7801 * The CAP (stochastic capacitated facility location problem) example demonstrates the use of the default Benders'
7806 * A custom Benders' decomposition requires the implementation of a Benders' decomposition plugin. The key aspects for
7811 * In GCG 3.0, a Benders' decomposition mode has been implemented. This mode takes the decomposition found by the
7812 * detection schemes of GCG and applies Benders' decomposition. Using GCG it is possible to apply Benders' decomposition
7817 * Classically, the application of Benders' decomposition results in the inclusion of an auxiliary variable to provide an
7818 * underestimation of the subproblem objective value. If the subproblem can be separated into disjoint problems, then
7819 * this auxiliary variable can be substituted with the sum of auxiliary variables (one for each subproblem).
7821 * While the summation of auxiliary variables is theoretically possible for all applications of Benders' decomposition,
7822 * there are problems where an alternative objective may be beneficial. An example is a multiple machine scheduling
7823 * problem with a makespan objective. To accommodate different objective types, the Benders' decomposition framework
7824 * allows for the objective types of summation (the classical method) or the minimum of the maximum subproblem auxiliary
7825 * variables. The objective type can be set using the function SCIPsetBendersObjectiveType(). Note that the different
7826 * objective types only have an impact if more than one subproblem is used in the Benders' decomposition.
7830/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7834 * SCIP contains two methods to perform a temporary dive in the branch-and-bound tree: the diving mode and the probing mode.
7835 * Both methods enable the modification of variable bounds, addition of new constraints, or adjustments to the objective function.
7836 * Whereas the diving mode works directly on the LP structure, the probing mode creates temporary branch-and-bound nodes, which makes it possible to perform backtracks during a dive.
7837 * Probing allows to perform domain propagation at the temporary nodes and provides the ability to solve the LP by column generation if a pricer plugin is implemented; neither is possible in diving mode.
7839 * After entering diving or probing mode by calling SCIPstartDive() and SCIPstartProbing(), respectively, there exist various functions that allow the user to temporarily change the LP.
7840 * An overview for diving can be found here[https://www.scipopt.org/doc/html/group__PublicLPDivingMethods.php] and for the probing mode here[https://scipopt.org/doc/html/group__PublicProbingMethods.php].
7841 * To reset all changes, the respective mode needs to be ended by calling SCIPendDive() and SCIPendProbing(), respectively.
7843 * Note that, although the state of the LP and the problem is reset after ending probing and diving, both modes can have several effects on the subsequent solving process.
7844 * In some situations, when the LP is infeasible for example, conflict analysis will be run in both probing and diving modes, which can lead to globally valid conflict constraints that are then added to the main solving process.
7845 * Similarly, the function SCIPpropagateProbing() might find globally valid bound changes, which are added to the main SCIP and considered in the subsequent solving process.
7846 * Another way to leverage insights found during probing or diving is to update pseudo costs during both modes, helping make better branching decisions.
7847 * This is controlled by setting the parameter "divingpscosts" to TRUE, which is done in the default settings of SCIP.
7848 * Moreover, if the LP was not solved to optimality before entering diving mode (or the parameter "resolverestore" is set to TRUE), the LP is resolved to reset the solution.
7849 * In some cases, such as when dealing with a numerically difficult instance, this might lead to a different LP state.
7850 * Finally, during probing, global variable statistics can be collected by calling SCIPenableVarHistory() after starting probing.
7851 * Since these statistics can be used for decision-making in SCIP, enabling their collection can have an effect on the solving process after probing ends.
7854/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7858 * As a feature standing out among today's MIP solvers, \SCIP offers the option to solve mixed-integer linear programs
7859 * in a numerically exact solving mode, in which it uses rational, extended-precision, and safe floating-point
7860 * computation in order to guarantee that results are not affected by roundoff errors from unsafe floating-point
7866 * - [Boost](https://www.boost.org/) multiprecision library for rationals in SCIP (and PaPILO, if linked),
7867 * - [MPFR](https://www.mpfr.org/) for approximating rationals with floating-point numbers in SCIP,
7870 * Enabling the exact solving mode is done by setting the parameter `exact/enable = TRUE` or calling the API function
7871 * `SCIPenableExactSolving()`. Note that this has to be done <b>before</b> reading a problem instance. Further advanced
7874 * Optionally, the output of a certificate (also known as proof logging) can be enabled by specifying
7876 * [VIPR](https://github.com/scipopt/vipr) or a formally verified version in [CakeML](https://cakeml.org/checkers.html).
7877 * Note that certificate files are incomplete if cutting plane separation is enabled (as by default). In this case, the
7880 * All plugins that want to participate in exact solving mode need to be marked as safe to use when included.
7885/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7892 * reference counter to one. Capturing an object (e.g., by calling SCIPcaptureVar()) increases the reference counter,
7893 * releasing it (e.g., by calling SCIPreleaseVar()) decreases the counter. If the reference counter gets zero, the
7899 * When a data object is added to SCIP (e.g., by calling SCIPaddVar()) , it is captured again, such that a
7909 * the reference counter will be 1 afterwards, and the variable will be destroyed, if SCIP frees the problem.
7910 * If the user wants to use this variable, e.g. for extracting statistics after SCIP was finished, the user must not call
7914/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7937 * If this is the case, the user can define a function by the PARAMCHGD callback and use this function as
7938 * the @c paramchgd parameter of the @c SCIPaddXyzParam() function, also giving a pointer to the data, which is
7939 * needed in this function, as @c paramdata. If this function is not NULL, it is called every time
7943/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
7949 * -# <b>buffer memory:</b> efficient handling of memory that needs to locally be allocated and freed
7954 * In the following, we provide a brief description of these methods. We refer the reader to the dissertation of Tobias
7960 * - <em>Accounting:</em> Using its own functions, SCIP knows the total size of memory allocated internally and can change its
7961 * behavior: for instance, it can change to "memory saving mode" (using depth first search (DFS) and possibly do a garbage
7963 * - <em>Speed:</em> SCIP often needs to allocate a very large number of small blocks of similar sizes (often powers of
7964 * two). Depending on the operating system and compiler, the methods implemented in SCIP can be faster, since blocks
7965 * of the same size are grouped together. Especially at the end of the 1990ies the standard malloc/free methods were
7966 * quite ineffective. The experiments of Tobias Achterberg in 2007 show a speed improvement of 11 % when using block
7968 * - <em>Efficiency:</em> Since blocks are groups in sizes, the blocks do not need to store their sizes within each
7969 * block. In comparison, standard malloc/free stores the size using one word for each memory chunk. The price to pay
7970 * is that one needs to pass the size to the functions that free a block. In any case, the methods in SCIP can save
7971 * memory. Moreover, buffer memory is stored in similar places and not spread out, which also might help cache.
7972 * - <em>Debugging:</em> All of the possibilities provide methods to detect memory leaks. Together with tools like
7978 * SCIP offers its own block memory handling, which allows efficient handling of smaller blocks of memory in cases in
7979 * which many blocks of the same (small) size appear. This is adequate for branch-and-cut codes in which small blocks
7980 * of the same size are allocated and freed very often (for data structures used to store rows or branch-and-bound
7981 * nodes). Actually, most blocks allocated within SCIP have small sizes like 8, 16, 30, 32, 64. The idea is simple:
7982 * There is a separate list of memory blocks for each interesting small size. When allocating memory, the list is
7983 * checked for a free spot in the list; if no such spot exists, the list is enlarged. Freeing just sets the block to be
7984 * available. Very large blocks are handled separately. See the dissertation of Tobias Achterberg for more details.
7986 * One important comment is that freeing block memory requires the size of the block in order to find the right list.
8000 * In addition to block memory, SCIP offers buffer memory. This should be used if memory is locally used within a
8001 * function and freed within the same function. For this purpose, SCIP has a list of memory buffers that are reused for
8004 * Note that the buffers are organized in a stack, i.e., freeing buffers in reverse order of allocation is faster.
8012 * SCIP 3.2 introduced a new type of buffer memory, the <em>clean buffer</em>. It provides memory which is initialized to zero
8013 * and requires the user to reset the memory to zero before freeing it. This can be used at performance-critical
8014 * places where only few nonzeros are added to a dense array and removing these nonzeros individually is much faster
8015 * than clearing the whole array. Similar to the normal buffer array, the clean buffer should be used for temporary memory
8025 * SCIP provides an access to the standard C functions @c malloc and @c free with the additional feature of tracking
8026 * memory in debug mode. In this way, memory leaks can be easily detected. This feature is automatically activated in
8035 * - `SCIPensureBlockMemoryArray()`: Extends a dynamically allocated block memory array to be able to store at least the given
8036 * number of elements. This function ensures that the array is resized efficiently by calculating an appropriate new size. This can be
8039 * - `SCIPreallocBlockMemoryArray()`, `SCIPreallocBufferArray()`, `SCIPreallocMemoryArray()`: Reallocate memory arrays to a specific
8040 * new size. These are useful when you already know the exact new size needed, for instance when managing multiple arrays of the
8041 * same size or when you want to compute the new size once and apply it to multiple arrays. Unlike the ensure* functions, these
8047 * Since allocating and freeing memory is very crucial for the speed and memory consumption of a program, it is
8053 * - In debug mode, the arguments are checked for overly large allocations (usually arising from a bug). Note that all
8054 * arguments are converted to unsigned values of type @c size_t, such that negative sizes are converted into very
8056 * - The functions always allocate at least one byte and return non-NULL pointers if memory is available. In particular,
8059 * - Debugging can be supported by using the compiler flags @p NOBLKMEM=true, @p NOBUFMEM=true, @p NOBLKBUFMEM=true
8060 * that turn off the usage of block memory, buffer memory, as well as block and buffer memory, respectively. Since,
8061 * the internal block and buffer memory is freed at the end (leaving no memory leaks), turning them off allows tools
8068 * - Use buffer memory if your memory chunk can be allocated and freed within the same function.
8070 * - Free memory in the reverse order in which it was allocated! For block and buffer memory this @b significantly
8072 * - Use as few memory allocations/freeing operations as possible, since these functions take a significant amount of time.
8080 * - Be careful with buffer memory reallocation: For single buffers, the memory is reallocated (using malloc); since
8081 * the actual space might be larger than what was needed at allocation time, reallocation sometimes comes without
8085/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
8091 * - Use <b>asserts</b> in your code to show preconditions for the parameters, invariants and postconditions.
8092 * Assertions are boolean expressions which inevitably have to evaluate to <code>TRUE</code>. Consider the
8097 * As you can see, both pointers and integers are checked for valid values at the beginning of the
8098 * function <code>consCatchEvent()</code>. This is particularly important for, e.g., array indices like
8099 * the variable <code>pos</code> in this example, where using the <code>consdata->vars[pos]</code>
8101 * if the asserted precondition on <code>pos</code> were not matched and <code>pos</code> were an arbitrary index
8111 * \endcode and run the code. See \ref CMAKE and \ref MAKE for further information about compiler options for SCIP.
8119 * at the top of SCIP files you want to analyze. This will output messages included in the code using
8120 * <code>SCIPdebugMsg(scip, ...)</code> (or <code>SCIPdebugMessage()</code>), see \ref EXAMPLE_1.
8121 * We recommend to also use <code>SCIPdebugMsg(scip, ...)</code> in your own code for being able to activate
8126 * - If available on your system, you can use software like <a href="http://valgrind.org">valgrind</a> to check for uninitialized
8131 * - If there are memory leaks for which you cannot detect the origin, you can recompile your code with the option <code>cmake -DNOBLKBUFMEM=on</code>
8133 * Also for the Makefile system, do not forget to clean your code before with <code>make OPT=... LPS=... clean</code>)
8136 * - If your code cuts off a feasible solution, but you do not know which component is responsible,
8137 * you can use the debugging mechanism (see \ref EXAMPLE_2). Therefore, a given solution is read and it
8141 * For example, if we include a <code>\#define SCIP_DEBUG</code> at the top of \ref heur_oneopt.c, recompile SCIP
8143 * <a href="http://miplib2010.zib.de/miplib3/miplib.html">MIPLIB 3.0</a> , we get some output like:
8153 * If we afterwards recompile SCIP with the additional compiler flag <code>cmake -DDEBUGSOL=on</code> (<code>make DEBUGSOL=true</code> in the Makefile system),
8154 * set the parameter <code>misc/debugsol = check/p0033.sol</code>, and run SCIP again it will output:
8159/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
8163 * The SCIP object goes through different stages during the solving process, the transitions from one to the next are presented in the following diagram.
8182 * Most functions can be called in a subset of the stages, this is then documented, a runtime check is often added and will throw a \ref SCIP_INVALIDCALL if the stage is not allowed.
8185/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
8189 * The SCIP source code has different types of files, distinguished by their naming style. The following list gives an overview of the most important file types and their purpose.
8194 * - The internal implementation should be in a file `<component>.c,h` and should not be included in the public API.
8195 * - Internal API functions usually do not take a `SCIP*` parameter, but a pointer to the component as first argument and pointers to internal structures like `SCIP_SET*` or `SCIP_STAT*`, where necessary.
8196 * - The name of internal API functions follows the style `SCIP<component><operation>...`, e.g., <code>SCIPvarCreateOriginal()</code> or <code>SCIPvarAddLocks()</code>.
8197 * - `pub_<component>.h` declares the functions of the public API that do not need a SCIP pointer.
8200 * - Functions in `pub_<component>.h` follow the same naming style as those in `<component>.h` and are used by the implementation of the internal API as well.
8201 * - `scip_<component>.h` declares the functions of the public API that need a SCIP instance (`SCIP*`), e.g., \ref scip_var.h for public variable manipulation functions.
8202 * Functions declared in `scip_<component>.h` are often thin wrappers that call the internal API functions from `<component>.h`.
8203 * These functions should follow the naming style `SCIP<operation><component>...`, e.g., <code>SCIPcreateVarOriginal()</code> or <code>SCIPaddVarLocks()</code>.
8204 * - To ensure functions of the public API being reachable in shared libraries, their declaration needs to contain the <code>SCIP_EXPORT</code> attribute.
8206 * Type names follow the style `SCIP_<COMPONENT>...`. For every struct, we have a typedef that shortens the name
8208 * The convention is to have the mixed-casing for the struct name, and then all-capital for the typedef's type. Similar for enums.
8209 * - Structs that need to be accessed by several source files are defined in `struct_<component>.h`.
8210 * `struct_<component>.h` is usually included only by `<component>.c` and maybe `scip_<component>.c`.
8211 * Exceptions are due to manual inlining of functions via macros when compiling for optimized mode.
8213 * The documentation of the implementation of a function must repeat the documentation of the function declaration exactly (for doxygen to treat them as identical).
8220 * - API functions of plugins are named as `SCIP<operation>...<Name>`, e.g., <code>SCIPincludeConshdlrAnd()</code>, <code>SCIPcreateConsAnd()</code>, or <code>SCIPgetNVarsAnd()</code>.
8222 * - Plugins that need to be included by default should be registered in <code>src/scip/scipdefplugins.c</code>.
8225/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
8236 * At first you should create a file listing all problem instances that should be part of the test.
8242 * e.g., <code>../../problems/instance1.lp</code> or absolute path, e.g., <code>/home/problems/instance2.mps</code>
8243 * in this file. Only one problem should be listed on every line (since the command <code>cat</code> is used to parse this file).
8247 * Optionally, you can provide a solution file in the <code>scip/check/testset/</code> directory containing
8248 * known information about the feasibility and the best known objective values for the test instances.
8249 * SCIP can use these values to verify the results. The file has to have the same basename as the
8250 * <code>.test</code>-file, i.e., in our case <code>testrun.solu</code>. One line can only contain
8257 * With these information types you can encode for an instance named <code>instance1.lp</code> the following
8284 * See the files <code>scip/check/testset/short.test</code> and <code>scip/check/testset/short.solu</code>
8297 * <code>test</code>-file (<code>testrun.test</code>). This will cause SCIP to solve our test instances
8303 * During computation, SCIP automatically creates the directory <code>scip/check/results/</code>
8312 * \arg <code>*.pav</code> - <a href="http://www.gamsworld.org/performance/paver/">PAVER</a> output
8314 * The last three files in the above list, i.e., the files containing a summary of the computational results,
8315 * can also be generated manually. Therefore the user has to call the <code>evalcheck.sh</code> script in the
8316 * @c check directory with the corresponding @c out file as argument. For example, this may be useful if the user stopped the
8317 * test before it was finished, in which case the last three files will not be automatically generated by SCIP.
8319 * The last column of the ASCII summary table contains the solver status. We distinguish the following statuses: (in order of priority)
8322 * \arg fail: solver cut off a known feasible solution (value of the <code>solu</code>-file is beyond the dual bound;
8326 * \arg solved: solver solved problem which has no (optimal) value in solu-file (since we here cannot detect the direction
8327 * of optimization, it is possible that a solver claims an optimal solution which contradicts a known feasible solution)
8328 * \arg better: solver found solution better than known best solution (or no solution was noted in the <code>solu</code>-file so far)
8329 * \arg gaplimit, sollimit: solver reached gaplimit or limit of number of solutions (at present: only in SCIP)
8333 * Additionally the <code>evalcheck.sh</code> script can generate a <code>solu</code>-file by calling
8337 * where <code><solu-file></code> denotes the filename of the new file where the solutions shall be
8344 * The output has two additional columns containing the solving time until the first and the best solution was found.
8354 * \arg <<code>test name</code>> indicates the name of the the test file, e.g., <code>testrun</code>
8355 * \arg <<code>binary</code>> defines the used binary, e.g., <code>scip-3.2.0.linux.x86_64.gnu.opt.spx</code>
8356 * \arg <<code>machine name</code>> tells the name of the machine, e.g., <code>mycomputer</code>
8357 * \arg <<code>setting name</code>> denotes the name of the used settings, e.g., <code>default</code>
8369 * It is possible to use customized settings files for the test run instead of testing SCIP with default settings.
8372 * @b Note: Several common user parameters such as, e.g., the time limit and node limit parameters,
8375 * for a list of available advanced testing options that have to be specified from the command line.
8377 * @b Note: Accessing settings files in subfolders of the @c settings directory is currently not supported.
8385 * in the SCIP root directory. It is possible to enter a list of settings files as a double-quoted,
8386 * comma-separated list of settings names as <code>fast</code> above, i.e. <code>SETTINGS="fast,medium,slow"</code>
8387 * will invoke the solution process for every instance with the three settings <code>fast.set, medium.set, slow.set</code>
8388 * before continuing with the next instance from the <code>.test</code>-file. This may come in handy if the
8394 * We can further customize the test run by specifying the following options in the <code>make</code> call:
8396 * \arg <code>CONTINUE</code> - continue the test run if it was previously aborted [default: "false"]
8399 * \arg <code>LOCK</code> - should the test run be locked to prevent other machines from performing the same test run [default: "false"]
8400 * \arg <code>MAXJOBS=n</code> - run tests on 'n' cores in parallel. Note that several instances are solved in parallel, but
8405 * \arg <code>SETCUTOFF</code> - if set to '1', an optimal solution value (from the <code>.solu</code>-file) is used as objective limit [default: 0]
8406 * \arg <code>THREADS</code> - the number of threads used for solving LPs, if the linked LP solver supports multithreading [default: 1]
8407 * \arg <code>VALGRIND</code> - run valgrind on the SCIP binary; errors and memory leaks found by valgrind are reported as fails [default: "false"]
8412 * Often test runs are performed on the basis of different settings. In this case, it is useful to
8413 * have a performance comparison. For this purpose, we can use the <code>allcmpres.sh</code> script in
8416 * Suppose, we performed our test run with two different settings, say <code>fast.set</code> and
8417 * <code>slow.set</code>. Assuming that all other parameters (including the SCIP binary), were the same,
8418 * we may have the following <code>res</code>-files in the directory <code>scip/check/results/</code>
8432 * in the @c check directory. This produces an ASCII table on the console that provide a detailed
8433 * performance comparison of both test runs. Note that the first <code>res</code>-file serves as reference
8435 * (The term "solver" can be considered as the combination of SCIP with a specific setting file.)
8440 * \arg <code>NodQ</code> - Equals Nodes(i) / Nodes(0), where 'i' denotes the current solver and '0' stands for the reference solver.
8445 * \arg <code>eval</code> - Number of instances evaluated (bounds check = "ok", i.e., solved to optimality
8446 * within the time and memory limit and result is correct). Only these instances are used in the calculation
8464 * \arg <code>gnodes</code> - Geometric mean of the processed nodes over all evaluated instances.
8465 * \arg <code>shnodes</code> - Shifted geometric mean of the processed nodes over all evaluated instances.
8469 * \arg <code>gtime</code> - Geometric mean of the computation time over all evaluated instances.
8470 * \arg <code>shtime</code> - Shifted geometric mean of the computation time over all evaluated instances.
8476 * \arg <code>optimal auto settings</code> - Theoretical result for a solver that performed 'best of all' for every instance.
8477 * \arg <code>diff</code> - Solvers with instances that differ from the reference solver in the number of
8479 * \arg <code>equal</code> - Solvers with instances whose number of processed nodes and total number of
8480 * simplex iterations is equal to the reference solver (including a 10% tolerance) and where no timeout
8485 * Since this large amount of information is not always needed, one can generate a narrower table by calling:
8496 * As in the evaluation, the output contains the two additional columns of the solving time until the first and the best solution was found.
8500 * The \c allcmpres script also performs two statistical tests for comparing different settings: For deciding whether
8501 * more feasible solutions have been found or more instances have been solved to optimality or not, we use a McNemar
8502 * test. For comparing the running time and number of nodes, we use a variant of the Wilcoxon signed rank test. A
8503 * detailed explanation can be found in the PhD thesis of Timo Berthold (Heuristic algorithms in global MINLP solvers).
8507 * Assume that we compare two settings \c S1 and \c S2 with respect to the number of instances solved to optimality
8508 * within the timelimit. The null hypothesis would be "Both settings lead to an equal number of instances being solved
8509 * to optimality", which we would like to disprove. Let \f$n_1\f$ be the number of instances solved by setting \c S1
8510 * but not by \c S2, and let \f$n_2\f$ be the number of instances solved by setting \c S2 but not by \c S1. The
8515 * Under the null hypothesis, \f$\chi^2\f$ is chi-squared distributed with one degree of freedom. This allows to compute
8516 * a \f$p\f$-value as the probability for obtaining a similar or even more extreme result under the null hypothesis.
8530 * In this case, the test with respect to the number of found feasible solutions is irrelevant, since their number is
8531 * equal. In particular, the null hypothesis gets accepted (i.e., there is no difference in the settings - this is
8534 * With respect to the number of instances solved to optimality within the timelimit, we have that \f$0.005 < p <=
8535 * 0.05\f$ (marked by <tt>p ~ (0.005, 0.05)</tt>). Thus, there is some evidence that the null hypothesis is false, i.e., the
8536 * settings perform differently; this is marked by "!". In the concrete case, we have 230 instances, all of which are
8541 * Assume that we compare two settings \c S1 and \c S2 with respect to their solution times (within the time limit). We
8542 * generate a sorted list of the ratios of the run times, where ratios that are (absolutely or relatively) within 1\%
8543 * of 1.0 are discarded, and ratios between 0.0 and 0.99 are replaced with their negative inverse in order to
8547 * and \c G2 depending on whether the ratios are smaller than -1.0 or larger than 1.0 (\c G1 contains the instances for which
8548 * setting \c S1 is faster). Then the sums of the ranks in groups \c G1 and \c G2 are computed, yielding values \c R1
8555 * which we assume to be (approximately) normally distributed (with zero mean) and allows to compute the probability
8556 * \f$p\f$ that one setting is faster than the other. (Note that for \f$N \leq 60\f$, we apply a correction by
8564 * While the \f$z\f$-value is close to zero for the run time, it is extremely negative regarding the solving nodes. This latter
8565 * tendency for the number of nodes is significant on a 0.05 % level, i.e., the probability \f$p\f$ that setting \c S1 uses more
8568 * However, the null hypothesis is not rejected with respect to the run time. In the concrete case, setting \c S1 has a
8569 * shifted geometric mean of its run times (over 230 instances) of 248.5, for \c S2 it is 217.6. This makes a ratio of
8574 * Analogously to the target <code>test</code> there is another target to run automated tests with <a href="http://www.gams.com/">gams</a>
8578 * For this target, the option GAMSSOLVER has to be given to specify the name of a GAMS solver to run, e.g. GAMSSOLVER=SCIP.
8583 * CONVERTSCIP to specify a SCIP which can be used to convert non-gams files into gams format (default: bin/scip, if existing; set to "no" to disable conversion).
8585 * A memory limit (MEM option) is only passed as workspace option to GAMS, but not enforced via ulimit (it's up to the solver to regard and obey the limit).
8591 * After the testrun there should be an <code>.out</code>, an <code>.err</code> and a <code>.res</code> file
8598 * To run a python script that uses PySCIPOpt with <code>make test</code> or <code>make testcluster</code>, one has to
8599 * specify the python code to execute with the option <code>EXECUTABLE=/full/path/to/python-script.py</code>.
8601 * In addition, one <b>must</b> specify which python it should run with the option <code>PYTHON=my-python</code>.
8602 * The reason for this is that one usually installs PySCIPOpt in a virtual environment, thus only the python of the
8605 * The scripts work in such a way that they pass information to SCIP like the setting files, the instance name, and some other options.
8606 * It is the responsability of the python script <code>python-script.py</code> to parse this information.
8607 * Thus, you need to modify your python script to read the setting files and the other options provided by the testing scripts.
8609 * One should either modify <code>scip/check/scip-runner.py</code> or include the <code>build_model()</code> function
8618/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
8622 * SCIP is capable of computing (count or enumerate) the number of feasible solutions of a given constraint integer
8623 * program. In case continuous variables are present, the number of feasible solutions for the projection to the
8624 * integral variables is counted/enumerated. This means, an assignment to the integer variables is counted if the
8625 * remaining problem (this is the one after fixing the integer variables w.r.t. to this assignment) is feasible.
8627 * As a first step you have to load or create your problem in the usual way. In case of using the
8632 * Afterwards you can count the number of feasible solution with the command <code>count</code>.
8636 * @note After completing the counting process, SCIP will terminate with status <tt>infeasible</tt>. This is intended
8637 * behavior, because SCIP counts solutions by the following internal mechanism. Each feasible solution that is found is
8638 * reported as infeasible to the SCIP core. This avoids that SCIP performs reductions based on the primal bound that
8639 * could cut off suboptimal feasible solutions, which would then be missing in the count. However, as a result, the
8640 * SCIP core has not found any feasible solutions during the search and reports status <tt>infeasible</tt>.
8642 * By default, SCIP only counts the number of solutions but does not store (enumerate) them. If you are interested in
8645 * @note Since SCIP version 2.0.0 you do not have to worry about the impact of dual reductions anymore. These are
8646 * automatically turned off. The only thing you should switch off are restarts. These restarts can lead to a wrong
8647 * counting process. We recommend using the counting settings which can be set in the interactive shell as follows:
8651 * The SCIP callable library provides an interface function SCIPcount() which allows users to count the number of feasible
8652 * solutions to their problem. The function SCIPsetParamsCountsols(), which is also located in cons_countsols.h, loads the
8653 * predefined counting settings to ensure a safe count. The complete list of all functions that can be used for counting
8659 * It is possible to give a (soft) upper bound on the number solutions that should be counted. If this upper bound is
8660 * exceeded, SCIP will be stopped. The name of this parameter is <code>constraints/countsols/sollimit</code>. In
8665 * In case you are using the callable library, this upper bound can be assigned by calling SCIPsetLongintParam() as follows:
8672 * The reason why this upper bound is soft comes from the fact that, by default, SCIP uses a technique called unrestricted
8673 * subtree detection. Using this technique it is possible to detect several solutions at once. Therefore, it can happen
8678 * Per default SCIP only counts all feasible solutions. This means, these solutions are not stored. If you switch the
8679 * parameter <code>constraints/countsols/collect</code> to TRUE (the default value is FALSE) the detected solutions are
8690 * @note The solution which are collected are stored w.r.t. the active variables. These are the variables which got not
8693 * In case you are using the interactive shell you can write all collected solutions to a file as follows
8697 * In that case the sparse solutions are unrolled and lifted back into the original variable space.
8699 * The callable library provides a function which gives access to all collected sparse solutions. That is,
8700 * SCIPgetCountedSparseSolutions(). The sparse solutions you get are defined w.r.t. active variables. To get solutions
8704 * -# lift each solution into original variable space by extending the solution by those variable which got removed
8707 * The get the variables which got removed during presolving, you can use the functions SCIPgetFixedVars() and
8708 * SCIPgetNFixedVars(). The function SCIPgetProbvarLinearSum() transforms given variables, scalars and constant to the
8709 * corresponding active variables, scalars and constant. Using this function for a single variable gives a representation
8710 * for that variable w.r.t. the active variables which can be used to compute the value for the considered solution (which
8714 * \ref SCIP_DECL_DIALOGEXEC(SCIPdialogExecWriteAllsolutions) "SCIPdialogExecWriteAllsolutions()" cons_countsols.c which
8720 * If you are interested in counting the number of optimal solutions, this can be done with SCIP using the
8724 * -# Added the objective function as constraint with left and right hand side equal to \f$c^*\f$
8733/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
8737 * Symmetry handling is an important feature of SCIP that allows to discard symmetric subproblems from the
8738 * branch-and-bound tree, and thus, can substantially reduce the running time. To handle symmetries, SCIP
8739 * automatically detects symmetries and then applies (combinations of) symmetry handling methods.
8743 * SCIP can detect two types of symmetries: permutation symmetries and signed permutation symmetries.
8748 * a permutation symmetry is a permutation \f$\gamma\f$ of \f$\{1,\dots,n\}\f$ that acts on vector \f$x\f$ by
8749 * permuting its coordinates via \f$\gamma(x) = (x_{\gamma^{-1}(1)}, \dots, x_{\gamma^{-1}(n)})\f$
8752 * -# \f$\gamma\f$ leaves the objective invariant, i.e., \f$c^{\top}x = c^{\top}\gamma(x)\f$, and
8753 * -# \f$\gamma\f$ maps feasible solutions onto feasible solutions, i.e., \f$Ax \leq b\f$ if and only
8756 * Signed permutation symmetries are defined similarly and allow to also handle symmetries arising from
8757 * reflections of the feasible region along standard hyperplanes, e.g., mapping \f$x_i\f$ to \f$-x_i\f$
8758 * and keeping the remaining entries of a solution vector \f$x\f$ invariant. Formally, a signed permutation \f$\gamma\f$
8759 * is a permutation of the set \f$\{\pm 1, \dots, \pm n\}\f$ such that \f$\gamma(-i) = - \gamma(i)\f$
8763 * where \f$\mathrm{sgn}(\cdot)\f$ is the sign function. The remaining properties of a symmetry are the same.
8767 * bounded domain to be centered at the origin. This way, also variables with, e.g., domains \f$[1,2]\f$
8768 * and \f$[0,1]\f$ can be symmetric. In SCIP, we implement this shift only within symmetry detection
8769 * to find generalized signed permutations; the variable bounds of the problem itself remain unchanged.
8771 * Since both definitions depend on the feasible region of the integer program, which is unknown
8772 * in general, SCIP only computes symmetries that leave the formulation of the optimization problem
8773 * invariant. To detect such formulation symmetries, SCIP builds an auxiliary colored graph whose
8774 * color-preserving automorphisms correspond to symmetries of the integer program. The symmetries of
8775 * the graph, and thus of the integer program, are then computed by an external graph automorphism
8776 * library that needs to be linked to SCIP. Currently, SCIP can use three such libraries: The graph
8777 * automorphism libraries bliss, nauty/traces, and dejavu. They are the basic workhorses to detect symmetries. Moreover, one can use
8778 * sassy, a graph symmetry preprocessor which passes the preprocessed graphs to bliss or nauty/traces; sassy is automatically included in dejavu.
8780 * To use other symmetry packages, options <code>SYM</code> and <code>-DSYM</code> in the Makefile and CMake
8784 * constraint mixed-integer programs containing most of the constraint types that can be handled
8794 * After symmetries have been computed, SCIP has access to a list \f$\gamma_1,\dots,\gamma_m\f$ of
8795 * (signed) permutations that generate a group \f$\Gamma\f$ of symmetries of the optimization problem. That
8796 * is, SCIP has not access to all permutations in \f$\Gamma\f$, but only a set of generators. Based
8797 * on these generators, SCIP analyzes the group \f$\Gamma\f$ and checks whether it can be split into
8799 * \f$\Gamma\f$ that act on pairwise independent sets of variables such that \f$\bigcup_{i=1}^k \Gamma_i = \Gamma\f$.
8800 * In this case, SCIP can handle the symmetries of the different subgroups independently. In particular,
8805 * Most symmetry handling methods available in SCIP have only been implemented for ordinary permutation symmetries,
8806 * and not for signed permutation symmetries. In the following, we silently assume that the described methods
8812 * SCIP contains three constraint handlers for handling symmetries of binary variables: the symresack,
8814 * the symresack constraint handler enforces that a solution vector \f$x\f$ is not lexicographically
8815 * smaller than its image \f$\gamma(x)\f$. This constraint is enforced by a propagation algorithm
8816 * and separating inequalities. Moreover, given the disjoint cycle decomposition of \f$\gamma\f$,
8817 * SCIP checks, for each cycle of \f$\gamma\f$, whether all variables in the cycle are contained
8818 * in set packing or partitioning constraints. If this is the case, specialized inequalities can
8823 * orbisack constraint handler. For orbisack constraints, also facet-defining inequalities of the
8824 * convex hull of all binary points \f$x\f$ being not lexicographically smaller than \f$\gamma(x)\f$
8825 * can be separated. Since the coefficients in these inequalities grow exponentially large which might
8826 * cause numerical instabilities, the separation of these inequalities is disabled by default, but can be
8827 * enabled via the parameter <code>constraints/orbisack/orbiSeparation</code>. Furthermore, to avoid
8828 * numerical instabilities, the parameter <code>constraints/orbisack/coeffbound</code> controls the
8831 * Finally, the orbitope constraint handler is able to handle symmetries of special symmetric groups \f$\Gamma\f$.
8832 * For orbitopes to be applicable, the affected variables need to be arranged in a matrix \f$X\f$ such that
8833 * the symmetries in \f$\Gamma\f$ permute the columns of \f$X\f$. Symmetries are then handled by orbitope
8834 * constraints by enforcing to only compute solution matrices \f$X\f$ whose columns are sorted lexicographically
8835 * non-increasingly. To this end, a propagation algorithm is used and inequalities are separated. In case
8836 * the variables of each row of the matrix \f$X\f$ are contained in a set packing or partitioning constraint,
8842 * The pro of that approach, is that throughout the solving process, the same lexicographic ordering constraint
8844 * The con of this approach is that an ordering of the variables for lexicographic comparisons have to be made
8845 * before solving. Consequently, if reductions of certain variable domains are found, but these variables are compared
8848 * Dynamic symmetry handling addresses this issue by propagating symmetry handling constraints, where the variable
8849 * comparison ordering are determined while solving, attempting to make strong symmetry handling reductions early on.
8850 * Dynamic symmetry handling removes feasible solutions of the problem, while it is guaranteed that at least one
8853 * Whether dynamic or static symmetry handling methods are used, is determined by the boolean parameter
8859 * -# Orbitopal reduction is the dynamic counterpart of orbitopal fixing. This method can be used if the variables
8860 * can be arranged without duplicates in a matrix, and symmetries permute the columns of this matrix. This method
8861 * propagates the variable domains such that solutions in matrix-form have lexicographically decreasing columns,
8863 * Orbitopal reduction respects the parameter <code>propagating/symmetry/detectorbitopes</code>.
8865 * Lexicographic reduction respects the parameter <code>propagating/symmetry/addsymresacks</code>.
8866 * At the moment, the implementation of this method is the only one that allows to also handle signed permutation
8868 * -# Orbital reduction is a generalization of orbital fixing that also works for non-binary variable domains.
8870 * See \ref SYMMETHODSELECT "method selection". Since there is no static counterpart, this method ignores
8874 * In particular, at different branch-and-bound tree nodes, a different variable ordering can be active.
8875 * Since the symmetries are handled for independent factors of the symmetry group, a different variable ordering method
8876 * can be used for handling symmetries in different factors. In SCIP, the same method is used for orbital reduction and
8877 * for lexicographic reduction, which means that these two methods are compatible and can be used simultaneously in the
8880 * As SCIP might restart the branch-and-bound process, which removes information regarding the branching decisions,
8882 * If a restart occurs, static symmetry handling methods are preserved. Since dynamic symmetry handling methods
8883 * depend on the branch-and-bound tree structure, and because the prior branch-and-bound tree is removed,
8888 * The Schreier-Sims table (SST) is a table that contains certain information about symmetry groups
8889 * and can be used, among others, to derive symmetry handling inequalities. The corresponding SST cuts
8890 * are symmetry handling inequalities that are defined iteratively in rounds \f$r = 1,\dots,R\f$.
8892 * \f$\Gamma_r = \{ \gamma \in \Gamma : \gamma(\ell_i) = \ell_i \text{ for all } i = 1,\dots,r-1\}\f$
8897 * SST cuts admit many degrees of freedom. In particular, they are not limited to binary variables
8898 * but can be used for arbitrary variable types. A user can gain control over the selection process of
8901 * - <code>sstleadervartype</code> is a bitset encoding the variable types of leaders: the 1-bit models binary,
8902 * the 2-bit integer, the 4-bit implied integral of any type, and the 8-bit continuous variables. That is, a value
8904 * - <code>sstleaderrule</code> ranges from 0 to 2 and models whether a leader is the first variable in
8905 * its orbit, the last variable in its orbit, or a variable with most conflicts with other variables in
8907 * - <code>ssttiebreakrule</code> ranges from 0 to 2 and models whether an orbit of minimum size, maximum
8909 * - <code>sstmixedcomponents</code> whether SST cuts are also applied if a symmetries do not only affect
8911 * - <code>sstaddcuts</code> whether SST cuts are added to the problem. If no cuts are added, only
8917 * <code>misc/usesymmetry</code>, which encodes the enabled methods via a bitset that ranges between 0
8918 * and 7: the 1-bit encodes symmetry handling constraints, the 2-bit encodes orbital reduction, and the
8919 * 4-bit encodes SST cuts. For example, <code>misc/usesymmetry = 3</code> enables symmetry handling
8920 * constraints and orbital reduction, whereas <code>misc/usesymmetry = 0</code> disables symmetry handling.
8921 * In the following, we explain how the combination of different symmetry handling methods works.
8923 * The default strategy of SCIP is to handle symmetries via the bitset value 7, i.e., symmetry handling
8924 * constraints, orbital reduction, and SST cuts are enabled. To make sure that the different methods are
8927 * -# SCIP determines independent subgroups \f$\Gamma_1,\dots,\Gamma_k\f$ as described in \ref SYMPROCESS.
8929 * -# For each subgroup \f$\Gamma_i\f$, a heuristic is called that checks whether orbitopes are applicable
8932 * -# Otherwise, if parameter <code>propagating/symmetry/detectsubgroups</code> is <code>TRUE</code>
8934 * heuristic is called to detect whether "hidden" orbitopes are present. That is, whether some but not
8935 * all symmetries of \f$\Gamma_i\f$ can be handled by orbitopes. If sufficiently many symmetries can
8936 * be handled by orbitopes, orbitopes are applied and, if parameter <code>propagating/symmetry/addweaksbcs</code>
8937 * is TRUE, some compatible SST cuts are added, too. Besides this, no further symmetry handling methods
8939 * -# Otherwise, orbital reduction is used. If <code>propagating/symmetry/usedynamicprop</code> and
8940 * <code>propagating/symmetry/addsymresacks</code> are <code>TRUE</code>, then also the dynamic lexicographic
8942 * -# Otherwise, if the majority of variables affected by \f$\Gamma_i\f$ are non-binary, SST cuts are applied
8943 * to handle \f$\Gamma_i\f$. No further symmetry handling methods are applied for \f$\Gamma_i\f$.
8945 * @note If orbital reduction is enabled, a factor \f$\Gamma_i\f$ can always be handled by this method.
8948 * @note Depending on the setting of <code>misc/usesymmetry</code>, it might be possible that a symmetry component is
8951 * and if a symmetry component is no orbitope, no symmetry is handled for that component at all.
8956 * Since presolving might both remove and introduce formulation symmetries, the timing of computing symmetries
8958 * The parameter takes value 0, 1, or 2, corresponding to computing symmetries before presolving,
8960 * Based on the computed symmetries, SCIP enables some symmetry handling methods as explained above.
8964 * To detect (signed) permutation symmetries, SCIP requests from each constraint present in the problem to be solved
8965 * a node and edge colored graph whose symmetries correspond to the symmetries of the corresponding constraint.
8966 * This information is provided by two callbacks, the SCIP_DECL_CONSGETPERMSYMGRAPH callback for permutation
8967 * symmetries and the SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH callback for signed permutation symmetries. If a
8968 * constraint handler does not implement one of these callbacks, SCIP will not detect symmetries of the corresponding
8971 * In the following, we briefly describe how such a symmetry detection graph looks like for linear constraints.
8972 * Afterwards, we mention the basic setup of the symmetry detection graphs and how the callbacks could be implemented
8977 * Simple permutation symmetries of a linear constraint \f$\sum_{i = 1}^n a_ix_i \leq \beta\f$ are given
8978 * by permutations that exchange equivalent variables with the same coefficients. These symmetries can be encoded
8979 * by a graph with the following structure. For every variable \f$x_i\f$, the graph contains a node \f$v_i\f$
8980 * that receives a color that uniquely determines the type of the variable (lower/upper bound, objective coefficient,
8981 * integrality). Moreover, the graph contains a node \f$w\f$ that receives a color corresponding to the right-hand side
8982 * \f$\beta\f$. Node \f$w\f$ is then connected with all nodes corresponding to variables. Edge \f$\{w,v_i\}\f$ then
8983 * receives a color corresponding to the coefficient \f$a_i\f$. Then, every automorphism of this graph corresponds to a
8986 * For signed permutation symmetries, almost the same construction can be used. The only difference is that also
8987 * nodes \f$v_{-i}\f$ need to be introduced that correspond to the negation of variable \f$x_i\f$. These negated
8988 * variable nodes are then also connected with node \f$\beta\f$ and the corresponding edge receives color \f$-a_i\f$.
8989 * Finally, to make sure that the corresponding symmetry corresponds to a signed permutation \f$\gamma\f$, i.e.,
8990 * \f$\gamma(-i) = - \gamma(i)\f$, one also needs to add the edges \f$\{v_i,v_{-i}\}\f$ that remain uncolored.
8991 * Note that the color of node \f$v_{-i}\f$ also needs to uniquely determine the negated variable bounds and
8996 * A symmetry detection graph of a constraint needs to have the property that each of its automorphisms corresponds
8997 * to a (signed) permutation of the constraint. Moreover, the corresponding constraint handler of the constraints
8998 * needs to be encoded in the graph to make sure that only symmetries between equivalent constraints can be computed.
8999 * Among others, this can be achieved by assigning the nodes and edges appropriate colors. To make sure that the
9000 * colors are compatible between the different symmetry detection graphs, SCIP automatically determines the colors of
9001 * nodes and edges based on information that is provided by the user (or the creator of the graph).
9003 * A pointer to a globally maintained symmetry detection graph is provided to the callbacks. The nodes and edges of the
9005 * The nodes of the graph need to be added via the functions <code>SCIPaddSymgraphValnode()</code>
9006 * and <code>SCIPaddSymgraphConsnode()</code>. The first function can be used to create nodes corresponding to
9007 * a numerical value like \f$\beta\f$ in the above example, the latter function creates a node corresponding to
9008 * a provided constraint. This ensures that only symmetry detection graphs from the same constraint handler
9009 * can be isomorphic. The colors of the nodes are then computed automatically by SCIP based on the information
9010 * that is provided the functions creating these nodes. This ensures that node colors are compatible.
9012 * Edges are created via the function <code>SCIPaddSymgraphEdge()</code> which receives, among others, the
9013 * indices of created nodes. Note that there is no function for creating variable nodes as SCIP automatically
9014 * creates nodes for variables. Their indices can be accessed via <code>SCIPgetSymgraphVarnodeidx()</code> for
9015 * original variables and <code>SCIPgetSymgraphNegatedVarnodeidx()</code> for negated variables used for
9016 * signed permutations. The edges between variables \f$x_i\f$ and \f$-x_i\f$ are also automatically present
9017 * in the symmetry detection graph for signed permutation symmetries. The function <code>SCIPaddSymgraphEdge()</code>
9018 * also takes a numerical value as argument, which allows to assign an edge a weight (e.g., \f$a_i\f$
9021 * Moreover, special nodes, so-called operator nodes, can be added via <code>SCIPaddSymgraphOpnode()</code>.
9022 * Such nodes allow to model special structures of a constraint, which allow to have more degrees of freedom in
9023 * creating symmetry detection graphs. Different operators are distinguished by an integral value.
9024 * Their encoding is thus similar to the one of nodes created by <code>SCIPaddSymgraphValnode()</code>.
9025 * In computing colors, operator nodes are treated differently though, which allows to distinguish
9030 * Let \f$G = (V,E)\f$ be an undirected graph with node weights \f$c_v\f$, \f$v \in C\f$. The maximum weight
9032 * \f\[ \max\Big\{ \sum_{v \in V} c_vx_v : x_u + x_v \leq 1 \text{ for all } \{u,v\} \in E,\; x \in \{0,1\}^V\Big\}.\f\]
9033 * Suppose a user wants to implement a constraint handler <code>cons_stableset</code> that enforces a solution to define
9034 * a stable set in \f$G\f$, e.g., by propagation methods and separating edge and clique inequalities.
9035 * Then, the symmetries of the constraint are the weight-preserving automorphisms of the underlying graph \f$G\f$.
9038 * In our construction, we introduce for each node \f$v\f$ of the graph an operator node \f$v'\f$.
9039 * Moreover, for each edge \f$\{u,v\}\in E\f$, we add the edges \f$\{u',v'\}\f$ to the symmetry detection graph.
9040 * To identify the symmetry detection graph as derived from <code>cons_stableset</code>, we add a constraint node
9041 * that is connected with all operator nodes, which preserves the automorphisms of \f$G\f$. Finally, each
9044 * In the following, we present a code snippet showing how to implement the above mentioned symmetry detection graph.
9052 * - <code>vars</code> array containing a binary variable for each node modeling whether node is present in stable set.
9082 * SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, idx[consdata->first[v]], idx[consdata->second[v]], FALSE, 0.0) );
9131 * There are several ways of accessing the \SCIP Optimization Suite from other software packages or programming
9137 * The easiest way to load a problem into SCIP is via an input file, given in a format that SCIP can parse directly,
9139 * \SCIP is capable of reading more than ten different file formats, including formats for nonlinear
9140 * problems and constraint programs. This gives researchers from different communities an easy access to the
9141 * \SCIP Optimization Suite. See also the \ref AVAILABLEFORMATS "list of readable file formats".
9145 * The main access point for \SCIP is its API to C. Please refer to the \ref PUBLICAPI documentation
9150 * Since \SCIP is written in C, its callable library can be directly accessed from C++. If a user wants to program own
9151 * plugins in C++, there are wrapper classes for all different types of plugins available in the <code>src/objscip</code>
9152 * directory of the \SCIP standard distribution. SCIP provides several examples that were written in C++, see
9157 * Interfaces for other programming languages are developed and maintained independently from the SCIP Optimization Suite
9158 * on <a href="https://github.com/scipopt">GitHub</a> in order to provide extensions and patches faster
9161 * - <a href="https://github.com/scipopt/PySCIPOpt">PySCIPOpt</a> provides an extensive open-source interface for Python.
9162 * PySCIPOpt can be installed via <a href="https://anaconda.org/conda-forge/pyscipopt">conda-forge</a>,
9166 * Since Python is one of the most commonly used programming languages, especially in the field of
9167 * machine learning, the API gives easy access to the solvers functionality to incorporate \SCIP
9168 * into any python project pipeline, extract data for further analysis and computation as well as allow
9183 * There are also many third-party python interfaces to the \SCIP Optimization Suite, for example:
9184 * - <a href="https://github.com/eomahony/Numberjack">NUMBERJACK</a> is a constraint programming platform implemented in python.
9187 * by Ryan J. O'Neil and is a python extension of the \SCIP Optimization Suite (not maintained anymore).
9201 * - <a href="https://jump.dev/JuMP.jl/stable/">JuMP</a> accesses SCIP through the Julia interface.
9202 * - <a href="http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Main.HomePage">YALMIP</a> by Johan Löfberg provides a
9211 * It is activated when the executable is called with the name of the AMPL `.nl` file as first argument and `-AMPL` as second argument.
9212 * In this case, \SCIP will employ the \ref reader_nl.h "NL reader" to read the `.nl` file (and `.col` and `.row` files with variable and constraint names, if available),
9213 * read parameter settings from a `scip.set` file (if present), attempt to solve the problem, write an AMPL solution file with the solve output, and exit.
9214 * However, if `-i` is given as third argument, then solving the problem is replaced by opening the \ref SHELL "interactive shell".
9216 * Next to a `scip.set` file, parameter settings can also be given via an `option` command in AMPL, e.g.,
9220 * Parameter `display/statistics` is specific to using \SCIP via the AMPL interface and triggers a call to \ref SCIPprintStatistics after the problem has been solved (or the interactive shell has been exited).
9221 * In addition, a parameter `display/logfile` is available to specify a file to which to print \SCIP output in addition to stdout.
9224 * A dual solution is written to an AMPL solution file only if an LP has been solved with presolve disabled.
9226 * \SCIP is also able to write AMPL `.nl` files (and `.col` and `.row` files with variable and constraint names). See \ref reader_nl.h for currently supported constraint types.
9230 * @brief functions and headers of the public C-API of \SCIP. Please refer to \ref DOC "" for information how to use the reference manual.
9239 * @brief functions and headers of the plugin-independent C-API provided by the \SCIP header file scip.h.
9241 * This module comprises functions provided by the header file scip.h. Including this header into a user-written extension
9252 * In order facilitate the navigation through the core API of \SCIP, it is structured into different modules.
9269 * This module summarizes the main functions needed to create a problem for \SCIP, and access its most important members:
9274 * @note These core functions are not sufficient to create constraints of a certain type that is provided by the default plugins of \SCIP.
9275 * An example would be the creation of a linear constraint for which the functions provided by the
9276 * \ref cons_linear.h "linear constraint handler" must be used. Such functions are provided by the default plugins of \SCIP
9315 * This large group of functions and modules comprises the solving process related API of \SCIP. This includes
9336 * @brief functions to create, catch, process, and drop events during the solving process of \SCIP
9340 * If you want to catch an event for an original variable, you have to get the corresponding transformed variable
9347 * @see functions to interact with \ref PublicColumnMethods "LP columns" and \ref PublicRowMethods "LP rows"
9362 * @brief common functions used to manipulate, generate, and strengthen cuts and to organize the cutpool
9409 * @see \ref PublicVariableMethods "Public Variable functions" contains some typical variable branching score functions
9414 * @brief functions to query information about or strengthen the problem at the current local search node
9449 * Weighted Disjoint Set is a data structure to quickly update and query connectedness information
9674 * @brief core API extensions provided by the default plugins of \SCIP, includable via scipdefplugins.h.
9676 * All default plugins of \SCIP, especially the default \ref CONSHDLRS "constraint handlers", provide
9677 * valuable extensions to the \ref PUBLICCOREAPI "core API" of \SCIP. These functions are made available
9680 * For a better overview, this page lists all default plugin headers structured into modules based on their individual
9683 * All of the modules listed below provide functions that are allowed to be used by user-written extensions of \SCIP.
9688 * This page lists the header files of internal API functions. In contrast to the public API, these internal functions
9690 * \ref PUBLICCOREAPI "the Core API" and \ref PUBLICPLUGINAPI "Plugin API" for the complete API available to user plugins.
9696 * @brief functions and files provided by the default Benders' decomposition implementations of \SCIP
9698 * A detailed description what a Benders' decomposition implementation does and how to add a Benders' decomposition
9707 * This module contains functions to include specific Benders' decomposition implementations into \SCIP.
9709 * @note All default plugins can be included at once (including all Benders' decomposition implementations) using
9716 * @brief functions and files provided by the default Benders' decomposition cut method of \SCIP
9718 * A detailed description what a Benders' decomposition cut method does and how to add a Benders' decomposition
9727 * This module contains functions to include specific Benders' decomposition cut methods into \SCIP.
9729 * @note The Benders' decomposition cut methods are linked to each Benders' decomposition implementation. Thus, the
9730 * default Benders' decomposition implementations automatically include the necessary Benders' decomposition cut
9731 * methods. For custom Benders' decomposition implementations, you can call SCIPincludeDefaultBendersCuts() in the
9740 * A detailed description what a branching rule does and how to add a branching rule to SCIP can be found
9750 * @note All default plugins can be included at once (including all branching rules) using SCIPincludeDefaultPlugins()
9758 * A detailed description what a constraint handler does and how to add a constraint handler to SCIP can be found
9768 * @note All default plugins can be included at once (including all default constraint handlers) using SCIPincludeDefaultPlugins()
9776 * A detailed description what a cut selector does and how to add a cut selector to SCIP can be found
9786 * @note All default plugins can be included at once (including all default cut selectors) using SCIPincludeDefaultPlugins()
9804 * @note All default plugins can be included at once (including all default dialogs) using SCIPincludeDefaultPlugins()
9823 * @note All default plugins can be included at once (including all default displays) using SCIPincludeDefaultPlugins()
9838 * @note All default plugins can be included at once (including all default expression handlers) using SCIPincludeDefaultPlugins()
9846 * A detailed description what a expression interpreter does and how to add a expression interpreter to SCIP can be found
9856 * The \ref SHELL "interactive shell" and the callable library are capable of reading/parsing several different file
9861 * <tr><td>\ref reader_cip.h "CIP format"</td> <td>for SCIP's constraint integer programming format</td></tr>
9862 * <tr><td>\ref reader_cnf.h "CNF format"</td> <td>DIMACS CNF (conjunctive normal form) file format used for example for SAT problems</td></tr>
9863 * <tr><td>\ref reader_diff.h "DIFF format"</td> <td>for reading a new objective function for mixed-integer programs</td></tr>
9864 * <tr><td>\ref reader_fzn.h "FZN format"</td> <td>FlatZinc is a low-level solver input language that is the target language for MiniZinc</td></tr>
9865 * <tr><td>\ref reader_lp.h "LP format"</td> <td>for mixed-integer (quadratically constrained quadratic) programs (CPLEX)</td></tr>
9866 * <tr><td>\ref reader_mps.h "MPS format"</td> <td>for mixed-integer (quadratically constrained quadratic) programs</td></tr>
9867 * <tr><td>\ref reader_nl.h "NL format"</td> <td>for <a href="http://www.ampl.com">AMPL</a> .nl files, e.g., mixed-integer linear and nonlinear
9868 * <tr><td>\ref reader_opb.h "OPB format"</td> <td>for pseudo-Boolean optimization instances</td></tr>
9869 * <tr><td>\ref reader_osil.h "OSiL format"</td> <td>for mixed-integer nonlinear programs</td></tr>
9870 * <tr><td>\ref reader_pip.h "PIP format"</td> <td>for <a href="http://polip.zib.de/pipformat.php">mixed-integer polynomial programming problems</a></td></tr>
9871 * <tr><td>\ref reader_sol.h "SOL format"</td> <td>for solutions; XML-format (read-only) or raw SCIP format</td></tr>
9872 * <tr><td>\ref reader_wbo.h "WBO format"</td> <td>for weighted pseudo-Boolean optimization instances</td></tr>
9873 * <tr><td>\ref reader_zpl.h "ZPL format"</td> <td>for <a href="http://zimpl.zib.de">ZIMPL</a> models, i.e., mixed-integer linear and nonlinear
9879 * A detailed description what a file reader does and how to add a file reader to SCIP can be found
9890 * @note All default plugins can be included at once (including all default file readers) using SCIPincludeDefaultPlugins()
9897 * A detailed description what an IIS finder does and how to add a IIS finder to SCIP can be found \ref IISFINDER "here".
9906 * @note All default plugins can be included at once (including all default file readers) using SCIPincludeDefaultPlugins()
9931 * @note All default plugins can be included at once (including all default file readers) using SCIPincludeDefaultPlugins()
9967 * A detailed description what a node selector does and how to add a node selector to SCIP can be found
9977 * @note All default plugins can be included at once (including all default node selectors) using SCIPincludeDefaultPlugins()
9992 * @note All default plugins can be included at once (including all default nonlinear handlers) using SCIPincludeDefaultPlugins()
10000 * A detailed description what a NLP solver interface does and how to add a NLP solver interface to SCIP can be found
10010 * @note All default plugins can be included at once (including all default NLP solver interfaces) using SCIPincludeDefaultPlugins()
10018 * A detailed description what a presolver does and how to add a presolver to SCIP can be found
10028 * @note All default plugins can be included at once (including all default presolvers) using SCIPincludeDefaultPlugins()
10036 * Per default there exist no variable pricer. A detailed description what a variable pricer does and how to add a
10046* @note All default plugins can be included at once using SCIPincludeDefaultPlugins(). There exists no pricer per default.
10047* In order to see examples of variable pricers, please consult the \ref EXAMPLES "Coding Examples" of \SCIP.
10055 * A detailed description what a primal heuristic does and how to add a primal heuristic to SCIP can be found
10065 * @note All default plugins can be included at once (including all default primal heuristics) using SCIPincludeDefaultPlugins()
10073 * A detailed description what a propagator does and how to add a propagator to SCIP can be found
10083 * @note All default plugins can be included at once (including all default propagators) using SCIPincludeDefaultPlugins()
10091 * A detailed description what a relaxation handler does and how to add a relaxation handler to SCIP can be found
10092 * \ref RELAX "here". Note that the linear programming relaxation is not implemented via the relaxation handler plugin.
10093 * Per default no relaxation handler exists in SCIP. However, there are two relaxation handlers in the
10101 * A detailed description what a separator does and how to add a separator to SCIP can be found
10111 * @note All default plugins can be included at once (including all default separators) using SCIPincludeDefaultPlugins()
10130 * @note All default plugins can be included at once (including all default statisticstables) using SCIPincludeDefaultPlugins()
10136 * @brief functions used by the majority of operations involving floating-point computations in \SCIP
10146 * The core provides the functionality for creating problems, variables, and general constraints.
10147 * The default plugins of SCIP provide a mix of public API function and private, static function and callback declarations.