SCIP Frequently Asked Questions

General Questions about SCIP

Using SCIP as a standalone MIP-Solver

  • The output is too wide for my terminal window. What can I do?
  • Type "set display width" followed by a appropriate number into the interactive shell. Please also regard the next question.
  • What do the cryptic abbreviations for the columns mean which are displayed during the solving process of SCIP?
  • Type "display display" in the interactive shell to get an explanation of them. By the way: If a letter appears in front of a display row, it indicates, which heuristic found the new primal bound, a star standing for an integral LP-relaxation.
    Typing "display statistics" after finishing or interrupting the solving process gives you plenty of extra information about the solving process.
  • How do I change the behavior of my solver?
  • You can find a variety of different general settings for SCIP in the directory "settings". They can be loaded via "set load settings/*/*.set". You can combine the general settings for cuts, presolving, and heuristics arbitrarily.
    "display parameters" shows you which settings currently differ from their default, "set default" resets them all. Furthermore, there are complete settings in settings/emphasis/, analogously to ILOG CPLEX.
  • I recognized that one special plugin works very bad / very well for my problem and I want to disable it / weaken its influence / intensify its influence. How do I do this?
  • For using a non-default branching rule or node selection strategy as standard, you just have to give it the highest priority, using, e.g., "set branching mostinf priority 9999999"
    If you want to completely disable a heuristic or a separator you have to set its frequency to -1 and the sepafreq to -1 for separation by constraint handlers, respectively.
    For disabling a presolver, you have to set its maxrounds parameter to 0.
    If you want to intensify the usage of a heuristic, you can reduce its frequency to some smaller, positive value, and/or raise the quotient and offset values (maxlpiter for diving heuristics, nodes for LNS heuristics).
    For intensifying the usage of a separator, you can raise its maxroundsroot and maxsepacutsroot values. If you also want to use this separator locally, you have to set its frequency to a positive value and possibly raise maxrounds and maxsepacuts. Compare the parameters of the heuristic/separator in the appropriate aggressive setting (see previous question).
    For weakening, you should just do the opposite operation, i.e. reducing the values you would raise for intensification and vice versa.

Using SCIP included in another source code

  • How Do I construct a problem instance in SCIP?
  • First you have to create your SCIP object via SCIPcreate(), then you start to build up the problem via SCIPcreateProb().
    Now, it is time to fill in the variables by first creating them via SCIPcreateVar() and then adding them to the problem via SCIPaddVar().
    The same has to be done for the constraints. For example, if you want to fill in the rows of a general MIP, you have to call SCIPcreateConsLinear(), SCIPaddConsLinear() and additionally SCIPreleaseCons() after finishing. In principle, you could now call SCIPsolve().
    Make sure to also call SCIPreleaseVar() if you do not need the variable pointer anymore. For an explanation of creating and releasing objects, please see the doxygen documentation..
  • I already know a solution in advance, which I want to pass to SCIP. How do I do this?
  • At first you have to build up your problem, then you have to transform your problem (SCIP only accepts solutions, if it is at least in the transformed stage, seehere) via calling SCIPtransformProb(). Next, you create a new SCIP primal solution by calling SCIPcreateSol() and set all nonzero values by calling SCIPsetSolVal().
    After finishing that, you add this solution by calling SCIPtrySol() (success should be true afterwards, if your solution was correct) and then release it by calling SCIPsolFree().
  • 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 SCIPtrySol() (see previous question).
  • 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 variable and constraint gets a "t_" as suffix: Apart from that, their meaning is identical.
    General integers with bounds that differ just by one will be aggregated to binary variables which get the same name with th suffix "_bin" . E.g. an integer variable t_x with lower bound 4 and upper bound 5 will be aggregated to a binary variable t_x_bin = t_x - 4.
    Variable can have negated counterparts, e.g. for a binary t_x its (also binary) negated would be t_x_neg = 1 - t_x.
    The knapsack constraint handler is able to disaggregate its constraints to cliques, which are theirselves are set packing constraints and get names that consist of the knapsack's name and a suffix "_clq_<int>".
    E.g., a knapsack constraint knap: x_1 + x2 +2·x_3 ≤ 2 could be disaggregated to the set packing constraints knap_clq_1: x_1 + x_3 ≤ 1 and knap_clq_2: x_2 + x_3 ≤ 1 .
  • 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.
  • 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 "make LPS=none".

Using SCIP as a Branch-Cut-And-Price-Framework

  • 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 deleted 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 constraint handler in the following cases:
    1. Some of your feasibility conditions can not be expressed by existing constraint types (e.g., linear constraints), or you would need too many of them. For example, the "nosubtour" constraint in the TSP is equivalent to exponentially many linear constraints. Therefore, it is better to implement a "nosubtour" constraint handler that can inspect solutions for subtours and generate subtour elimination cuts and others (e.g., comb inequalities) to strengthen the LP relaxation.
    2. Although you can express your feasibility condition by a reasonable number of existing constraint types, you can represent and process the condition in a more efficient way. For example, it may be that you can, due to your structural knowledge, implement a stronger or faster domain propagation or find tighter cutting planes than what one could do with the sum of the individual "simple" constraints that model the feasibility condition.

    You want to use a cutting plane separator in the following cases:
    1. You have a general purpose cutting plane procedure that can be applied to any MIP. It does not use problem specific knowledge. It only looks at the LP, the integrality conditions, and other deduced information like the implication graph.
    2. You can describe your feasibility condition by a set C of constraints of existing type (e.g., linear constraints). The cuts you want to separate are model specific, but apart from these cuts, there is nothing you can gain by substituting the set C of constraints with a special purpose constraint. For example, the preprocessing and the domain propagation methods for the special purpose constraint would do basically the same as what the existing constraint handler does with the set C of constraints. In this case, you don't need to implement the more complex constraint handler. You add constraints of existing type to your problem instance in order to produce a valid model, and you enrich the model by your problem specific cutting plane separator to make the solving process faster. You can easily evaluate the performance impact of your cutting planes by enabling and disabling the separator.

    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 manages "nosubtour" constraints, which demand that in a given graph no feasible solution must 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 CHECK, ENFOLP, and ENFOPS 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 SEPALP callback method of the constraint handler. Additionally, the constraint handler may want to separate other types of cutting planes like comb inequalities in its SEPALP callback.

  • Can I remove unnecessary display columns or - even better - add my own ones? Can I change the statistics displayed at the end of solving?
  • 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 from console, or include the line SCIPsetIntParam(scip, "display/memused/status", 0) into your source code. Adding an own display column can be realized via the SCIPinclDisp(), see the doxygen documentation.
    The statistic display, which is shown by "print statistics" and SCIPprintStatistics(), respectively, cannot be changed.
  • What 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 SCIPgetRowsData(). The methods SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwGetNNonz(),SCIProwGetCols() then give you information about each row, see previous question.
    You get a columnwise representation by calling SCIPgetColsData(). The methods SCIPcolGetLb() and SCIPcolGetUb() give you the locally valid bounds of the LP relaxation in the current branch-and-bound-node.
    If you are interested in global information, you have to call SCIPcolGetVar() to get the variable associated to a column (see next question), which you can ask for global bounds via SCIPvarGetLbGlobal() and SCIPvarGetUbGlobal() as well as the type of the variable (binary, general integer, implicit integer, or continuous) by calling SCIPvarGetType(). For more information, also see this question).
  • 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.
    Each column has an associated variable, which it represents, but not every variable must be part of the current LP-relaxation. E.g., it could be already fixed, aggregated to another variable, or be priced out if a column generation approach was implemented.
    Each row has either been added to the LP by a constraint handler or by a cutting plane seperator. A constraint handler is able to, but does not need to, add one or more rows to the LP as a linear relaxation of each of its constraints. E.g., in the usual case (i.e. without using dynamic rows) the linear constraint handler adds one row to the LP for each linear constraint.
  • Are the variables and rows sorted in some sense?
  • The variable array which you get by SCIPgetVars() is internally sorted by variable types. The binary variables are stored at position [0...nbinvars-1], the general integers at [nbinvars...nbinvars+nintvars-1], ... . It holds that nvars = nbinvars + ninitvars + nimplvars + ncontvars. There is no further sorting within these sections, as well as there is no sorting for the rows. But each column and each row has a unique index, which can be obtained by SCIPcolGetIndex() and SCIProwGetIndex(), respectively.
  • 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: SCIPisEQ(), SCIPisSumEQ(), SCIPisFeasEQ(), SCIPisRelEQ(), SCIPisSumRelEQ().

    SCIPisEQ() should be used to compare two single values that are either results of a simple calculation or are input data. The comparison is done w.r.t. the "numerics/epsilon" parameter, which is 1e-9 in the default settings.
    SCIPisSumEQ() should be used to compare the results of two scalar products or other "long" sums of values. In these sums, numerical inaccuracy can occur due to cancellation of digits in the addition of values with opposite sign. Therefore, SCIPisSumEQ() uses a relaxed equality tolerance of "numerics/sumepsilon", which is 1e-6 in the default settings.
    SCIPisFeasEQ() should be used to check the feasibility of some result, for example after you have calculated the activity of a constraint and compare it with the left and right hand sides. The feasibility is checked w.r.t. the "numerics/feastol" parameter, and the equation is defined in a relative fashion in contrast to absolute differences. That means, two values are considered to be equal if their difference divided by the larger of theri absolute values is smaller than "numerics/feastol". This parameter is 1e-6 in the default settings.
    SCIPisRelEQ() can be used to check the relative difference between two values, just like what SCIPisFeasEQ() is doing. In contrast to SCIPisFeasEQ() it uses "numerics/epsilon" as tolerance.
    SCIPisSumRelEQ() is the same as SCIPisRelEQ() but uses "numerics/sumepsilon" as tolerance. It should be used to compare two results of scalar products or other "long" sums.

...to be continued...
Valid HTML!
© 2003-2007 by Zuse Institute Berlin (ZIB), Imprint Last Update $Date: 2007/05/15 11:54:13 $