SCIP is capable of computing (count or enumerate) the number of feasible solutions of a given constraint integer program. In case continuous variables are present, the number of feasible solutions for the projection to the integral variables is counted/enumerated. This means, an assignment to the integer variables is counted if the remaining problem (this is the one after fixing the integer variables w.r.t. to this assignment) is feasible.
As a first step you have to load or create your problem in the usual way. In case of using the interactive shell, you use the read
command:
SCIP> read <file name>
Afterwards you can count the number of feasible solution with the command count
.
SCIP> count
infeasible
. This is intended behavior, because SCIP counts solutions by the following internal mechanism. Each feasible solution that is found is reported as infeasible to the SCIP core. This avoids that SCIP performs reductions based on the primal bound that could cut off suboptimal feasible solutions, which would then be missing in the count. However, as a result, the SCIP core has not found any feasible solutions during the search and reports status infeasible
.By default, SCIP only counts the number of solutions but does not store (enumerate) them. If you are interested in that see Collect all feasible solutions.
SCIP> set emphasis counter
The SCIP callable library provides an interface method SCIPcount() which allows users to count the number of feasible solutions to their problem. The method SCIPsetParamsCountsols(), which is also located in cons_countsols.h, loads the predefined counting settings to ensure a safe count. The complete list of all methods that can be used for counting via the callable library can be found in cons_countsols.h.
It is possible to give a (soft) upper bound on the number solutions that should be counted. If this upper bound is exceeded, SCIP will be stopped. The name of this parameter is constraints/countsols/sollimit
. In the interactive shell this parameter can be set as follows:
SCIP> set constraints countsols sollimit 1000
In case you are using the callable library, this upper bound can be assigned by calling SCIPsetLongintParam() as follows:
The reason why this upper bound is soft comes from the fact that, by default, SCIP uses a technique called unrestricted subtree detection. Using this technique it is possible to detect several solutions at once. Therefore, it can happen that the solution limit is exceeded before SCIP is stopped.
Per default SCIP only counts all feasible solutions. This means, these solutions are not stored. If you switch the parameter constraints/countsols/collect
to TRUE (the default value is FALSE) the detected solutions are stored. Changing this parameter can be done in the interactive shell
SCIP> set constraints countsols collect TRUE
as well as via the callable library
In case you are using the interactive shell you can write all collected solutions to a file as follows
SCIP> write allsolutions <file name>
In that case the sparse solutions are unrolled and lifted back into the original variable space.
The callable library provides a method which gives access to all collected sparse solutions. That is, SCIPgetCountedSparseSolutions(). The sparse solutions you get are defined w.r.t. active variables. To get solutions w.r.t. to the original variables. You have to do two things:
The get the variables which got removed during presolving, you can use the methods SCIPgetFixedVars() and SCIPgetNFixedVars(). The method SCIPgetProbvarLinearSum() transforms given variables, scalars and constant to the corresponding active variables, scalars and constant. Using this method for a single variable gives a representation for that variable w.r.t. the active variables which can be used to compute the value for the considered solution (which is defined w.r.t. active variables).
For that complete procedure you can also check the source code of SCIPdialogExecWriteAllsolutions() cons_countsols.c which does exactly that.
If you are interested in counting the number of optimal solutions, this can be done with SCIP using the count
command by applying the following steps:
If you do this, SCIP will collect all optimal solutions of the original problem.