SCIP Frequently Asked QuestionsSections
General Questions about SCIP
SCIP is a constraint integer program solver and contain all necessary plugin to be a standalone MIP-Solver
as well as a branch-cut-and-price-framework.
If you are either looking for a fast non-commercial MIP-Solver or for a branch-cut-and-price-framework in which you can directly implement your own methods — which can even be for more general purposes than MIP (see here). I heard something about licenses. Do I have to pay for using SCIP? As long as you use it for academic, non-commercial purposes: No. This will not change. For the other cases, check the explanation of the ZIB academic license and always feel free to ask us. Except if you want to use SCIP as a pure CP-Solver (see here), you need an underlying LP-Solver which has first to be installed and linked to the libraries (see the INSTALL file in the SCIP root directory). LP-solvers currently supported by SCIP are: We also provide some precompiled binaries. Besides that, you might need a modeling language like ZIMPL to generate *.mps or *.lp files. ZIMPL files can also directly be read by SCIP. An easy way is to use the SCIP-binaries and call SCIP from a shell. For that, you just have to download one of the precompiled binaries from the download section, or the zipped source code and compile it with your favorite settings. This is described in detail in the INSTALL file in the SCIP main directory. Another way is to use SCIP as a solver integrated into your own program source code. See the directory "examples/MIPsolver/" for a simple example and this point. A third way is to implement your own plugins into SCIP. This is explained in the HowTos for all plugin types, which you can find in the doxygen documentation. See also How to start a new project.
For an explanation of the naming see the
coding style guidelines.
In fact, there is a slight difference: I have installation problems. What can I do? Read the INSTALL file in the SCIP root directory. It contains hints of how to get around problems. You can also try the binaries available on the SCIP page. If you want to use SoPlex as the underlying LP-solver, you can try the following: First, download the ZIB Optimization Suite. Then, extract the file, change into the ziboptsuite directory, and enter 'make'. As long as you have all the necessary libraries installed in your system, it should generate a SCIP binary linked to ZIMPL and Soplex. The necessary system libraries are:
If you do not have all of these libraries, read the INSTALL file in the ZIB Optimization
Suite directory. If you have any problems while using an LP-solver different from SoPlex, please read the SCIP INSTALL file first. Maybe the parameters of a function in SCIP changed. Relevant changes between version are listed below.
Can I use SCIP as a pure CP-Solver?
Yes. There is a setting-file "settings/emphasis/cpsolver.set".
Furthermore, you can compile SCIP without any LP-Solver by How can I use the SCIP makefiles? See Makefiles. What is this business with .a and .so libraries in the directory lib/?
When SCIP builds the binary it needs to link with the corresponding libraries of the LP-solver. There are usually
two ways to distribute a library. In the first (.a) the library is linked statically to SCIP; this means
that all of its information is packed into the binary. In the second way (.so) the library is a shared
library. In this case, the code of the library is not inserted into the binary itself, but is loaded at
runtime. This has the advantage that the binaries are smaller, but it comes at the cost that you have to make
sure that the library is found at runtime (for most systems it suffices to put the path of the library into the
LD_LIBRARY_PATH variable). Can I compile SCIP as a shared library?
If you are using Linux and a GNU compiler you can use the Using SCIP as a standalone MIP-SolverThe output is too wide for my terminal window. What can I do? In the interactive shell you can set the width of the output with the following command "set display width" followed by an appropriate number. See also the next question.
Type "display display" in the interactive shell to get an explanation of them. How do I change the behavior of SCIP?
You can find a variety of different general settings for SCIP in the directory "settings".
They can be loaded via "set load settings/*/*.set" in the interactive shell.
You can combine the general settings for cuts, presolving, and heuristics arbitrarily.
Using SCIP included in another source codeHow do I construct a problem instance in SCIP?
First you have to create a SCIP object via I already know a solution in advance, which I want to pass to SCIP. How do I do this?
First you have to build your problem, then you have to transform your problem (SCIP only accepts solutions if it
is at least in the transformed stage, see here) via calling
What operational stages of SCIP are there and are they important for me?
There are ten different stages during a run of SCIP.
There are some methods which cannot be called in all stages, consider for example What is this thing with the original and the transformed problem about?
Before the solving process starts, the original problem is copied to a different memory area.
This copy is called "transformed problem", and all modifications during the presolving
and solving process are only applied to the transformed problem. Why do the names, e.g. in debug messages often differ from the ones I defined?
This can have several reasons. Especially names of binary variables can get different prefixes and suffixes. Each
transformed variable and constraint (see here) gets a "t_" as prefix. Apart from
that, the meaning of original and transformed variables and constraints is identical. What is SCIP_CALL()? Do I need this? Yes, you do. SCIP_CALL() is a global define, which handles the return codes of all methods which return a SCIP_RETCODE and should therefore parenthesize each such method. SCIP_OKAY is the code which is returned if everything worked well; there are 18 different error codes, see type_retcode.h. Each method that calls methods which return a SCIP_RETCODE should itself return a SCIP_RETCODE. If this is not possible, use SCIP_CALL_ABORT() to catch the return codes of the methods. If you do not want to use this either, you have to do the exception handling (i.e. the case that the return code is not SCIP_OKAY) on your own. Using SCIP as a Branch-Cut-And-Price-FrameworkSee How to start a new project. What types of plugins can I add and how do I do this? See the doxygen documentation for a list of plugin types. There is a HowTo for each of them. When should I implement a constraint handler, when should I implement a separator?
This depends on whether you want to add constraints or only cutting planes. The main
difference is that constraints can be "model constraints", while cutting planes are only
additional LP rows that strengthen the LP relaxation.
A model constraint is a constraint that is important for the feasibility of the integral
solutions. If you delete a model constraint, some infeasible integral vectors would
suddenly become feasible in the reduced model.
A cutting plane is redundant w.r.t. integral solutions. The set of feasible integral
vectors does not change if the cutting plane is removed. You can, however, relax this
condition slightly and add cutting planes that do cut off feasible solutions, as long as
at least one of the optimal solutions remains feasible.
You want to use a cutting plane separator in the following cases:
Note that a constraint handler is defined by the type of constraints that it manages. For constraint handlers, always think in terms of constraint programming. For example, the "nosubtour" constraint handler in the TSP (see "ConshdlrSubtour.cpp" in the directory "scip/examples/TSP/src/") manages "nosubtour" constraints, which demand that in a given graph no feasible solution can contain a tour that does not contain all cities. In the usual TSP problem, there is only one "nosubtour" constraint, because there is only one graph for which subtours have to be ruled out. The "nosubtour" constraint handler has various ways of enforcing the "nosubtour" property of the solutions. A simple way is to just check each integral solution candidate (in the CONSCHECK, CONSENFOLP, and CONSENFOPS callback methods) for subtours. If there is a subtour, the solution is rejected. A more elaborate way includes the generation of "subtour elimination cuts" in the CONSSEPALP callback method of the constraint handler. Additionally, the constraint handler may want to separate other types of cutting planes like comb inequalities in its CONSSEPALP callback.
Setting the status of a display column to 0 turns it off. E.g., type "set display memused status 0" in the
interactive shell to disable the memory information column, or include the line How do LP-rows look like in SCIP?
Each row is of the form lhs ≤ Σ(val[j]·col[j]) + const
≤ rhs. For now, val[j]·col[j] can be interpreted as
aij·xj (for the difference between columns and variables
see here). The constant is essentially needed for collecting the influence of presolving
reductions like variable fixings and aggregations. How do I get the data of the current LP-relaxation?
You can get all rows in the current LP-relaxation by calling What is the difference between columns and variables, rows and constraints?
The terms columns and rows always refer to the representation in the current LP-relaxation, variables and
constraints to your global Constraint Integer Program. Are the variables and rows sorted in any particular order? The variable array which you get by When should I use which of the numerical comparison functions?
There are various numerical comparison functions available, each of them using a different
epsilon in its comparisons. Let's take the equality comparison as an example. There are
the following methods available:
Specific questions about Column Generation and Branch-And-Price with SCIPWhy are not all variables in the LP?
With I only implemented one pricer, why is there a second one, called variable pricer? As described in the previous question, it may happen, that some variables are not in the current LP relaxation. Nevertheless, these variables still exist, and SCIP can calculate their reduced costs and add them to the LP again, if necessary. This is the job of the variable pricer. It is called before all other pricers.
Currently, it is not possible to delete variables during solving. A variable can be removed from the problem by
We are working on this problem and expect to provide functionalities for the deletion of variables in the next release. How can I store branching decisions? This is a very common problem in Branch-And-Price, which you can deal nicely with using SCIP. There are basically three different options. The first one is to add binary variables to the problem that encode branching decisions. Then constraints should be added that enforce the corresponding branching decisions in the subtrees. If you have complex pricer data like a graph and need to update it after each branching decision, you should introduce "marker constraints" that are added to the branching nodes and store all the information needed (see the next question). The third way is the usage of an event handler like described in How can an event handler help me with my branching?. This can be done by creating a new constraint handler with constraint data that can store the information and do/undo changes in the pricer's data structures. In general, all methods of the constraint handler (check, enforcing, separation, ...) should be empty (which means to always return the status SCIP_FEASIBLE for the fundamental callbacks), just as if all constraints of this type are always feasible. The important callbacks are the CONSACTIVE and CONSDEACTIVE methods. The CONSACTIVE method is always called when a node is entered on which the constraint has been added. Here, you need to apply the changes to your pricing data structures. The CONSDEACTIVE method will be called if the node is left again. Since the CONSACTIVE and CONSDEACTIVE methods of different constraints are always called in a stack-like fashion, this should be exactly what you need.
If you have such a constraint handler, just create constraints of this type and add them to the child nodes of
your branching by
If you need to fix variables for enforcing your branching decision, this can be done in the propagation callback
of the constraint handler. Since in general each node is only propagated once, in this case you will have to check
in your CONSACTIVE method whether new variables were added after your last propagation of this node. If this is
the case, you will have to mark this node for repropagation by You can look into the constraint handler of the coloring problem (examples/Coloring/src/cons_storeGraph.c) to get an example of a constraint handler that does all these things. How can an event handler help me with my branching? An event handler can watch for events like local bound changes on variables. So, if your pricer wants to be informed whenever a local bound of a certain variable changes, add an event handler, catch the corresponding events of the variable, and in the event handler's execution method adjust the data structures of your pricer accordingly. My pricer generates the same column twice. How can I solve this problem? First check whether your pricing is correct. Are there upper bounds on variables that you have forgotten to take into account? If your pricer cannot cope with other variable bounds than 0 and infinity, you have to mark all constraints containing priced variables as modifiable, and you may have to disable reduced cost strengthening by setting propagating/rootredcost/freq to -1. If your pricer works correctly and makes sure that the same column is added at most once in one pricing round, this behavior is probably caused by the PRICER_DELAY property of your pricer. If it is set to FALSE, the following may have happened: The variable pricer (see this question) found a variable with negative dual feasibility that was not part of the current LP relaxation and added it to the LP. In the same pricing round, your own pricer found the same column and created a new variable for it. This might happen, since your pricer uses the same dual values as the variable pricer. To avoid this behavior, set PRICER_DELAY to TRUE, so that the LP is reoptimized after the variable pricer added variables to the LP. You can find some more information about the PRICER_DELAY property at How to add variable pricers . Which default plugins should be deactivated in order to get a working branch-and price code?
In most cases, you should deactivate separators, since cutting planes that are added to your master problem may
destroy your pricing problem. Additionally, it may be necessary to deactivate some presolvers, mainly the dual
fixing presolver. This can be done by not including these plugins into SCIP, namely by not calling
|
|||
|
|