How to use SCIP to count/enumerate feasible solutions

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

Note

After completing the counting process, SCIP will terminate with status 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.

Note

Since SCIP version 2.0.0 you do not have to worry about the impact of dual reductions anymore. These are automatically turned off. The only thing you should switch off are restarts. These restarts can lead to a wrong counting process. We recommend using the counting settings which can be set in the interactive shell as follows:

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.

Limit the number of solutions which should be counted

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:

SCIP_CALL( SCIPsetLongintParam( scip, "constraints/countsols/sollimit", 1000) );

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.

Collect all feasible solutions

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

SCIP_CALL( SCIPsetBoolParam( scip, "constraints/countsols/collect", TRUE) );

Note

The solution which are collected are stored w.r.t. the active variables. These are the variables which got not removed during presolving.

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:

1. unroll each sparse solution
2. lift each solution into original variable space by extending the solution by those variable which got removed during presolving

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.

Count number of optimal solutions

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:

1. Solve the original problem to optimality and let \(c^*\) be the optimal value
2. Added the objective function as constraint with left and right hand side equal to \(c^*\)
3. load the adjusted problem into SCIP
4. use the predefined counting settings
5. start counting the number of feasible solutions

If you do this, SCIP will collect all optimal solutions of the original problem.