[Scip] Capturing multiple optimal solutions to a ILP

[Stefan Heinz]

Hi Rich

sorry for the late respond.


> Hi -
>
> I've been experimenting with SCIP+SoPlex over the last couple of days
> and I would really value some help getting started. My previous
> experience has been with the GLPK, so the open complexity of SCIP is a
> little daunting!
>
> I have an problem expressed as a ILP. The problem is mid-sized -
> approximately 17000 binary variables and 5000 constraints, and has a
> large number of optimal solutions. I wish to examine a sample of the
> optimal solutions because I'm interested in the redundancy of
> individual variables.
>
> As an ideal, I would like to collect a random sample of, say,
> 1000-10000 solutions from the set of optimal solutions to the ILP. Is
> this a feasible (meaningful?) goal, and where might I start looking
> for ways to implement it?
>
> Simply presolving and optimising my program generates (extremely
> quickly!) 8 optimal solutions, and describes one of them. Should I
> start looking at ways to 'design' a search strategy to sample a wider
> range of decisions? Or is there a simple solution I've missed?

Probably the eight solutions are not all optimal. These are solutions SCIP
founds during the solving process. Besides that, it is possible to access
all these solutions (but not via the interactive shell) by using the
following callback methods:

- int SCIPgetNSols(SCIP* scip)
  gives you the number of solutions (in your case 8).
- SCIP_SOL** SCIPgetSols(SCIP* scip)
  gives you a pointer to the array of these solutions

This does not solve your problem of finding a set of optimal solutions.
However, with SCIP it is possible to count/enumerate the number of feasible
solutions of a given constraint integer problem. The count/enumerating
functionality of SCIP in realized in the constraint handler "cons_countsols.
{c,h}" and is available since SCIP version 1.1.

Since you are interested only in optimal solutions I suggested a two stage
approach.

First solve the problem to optimality. Let c^* be the optimal value and
"c^T x" the objective function. Then, add the constrain c^T x = c^* to your
problem. The feasible solutions for this (new) problem are all optimal for
the original one. Using now the SCIP callback method SCIPcount(SCIP* scip)
will force SCIP to count all feasible (in your case optimal) solutions. If
you are interest to access these solutions you have the set the parameter
"constraints/countsols/collect" to TRUE using the call

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

before starting the counting process. Then SCIP will enumerate all feasible
solutions and it is possible to access them. This is done via the callback
method:

- void SCIPgetCountedSparseSolutions (SCIP *scip, SCIP_VAR *** vars, int
*nvars, SPARSESOLUTION ***sols, int *nsols)
  (located in "cons_countsols.h")

Doing this approach you should NOT use the default SCIP settings for the
count/enumeration loop. I recommend to load the setting file "counter.set",
which is locate in the "settings/emphasis/" directory of SCIP, for any
counting process to ensure a save count.

The open problem is how to stop SCIP if a certain amount of feasible
solutions are collected. The SCIP version 1.1 does not support this feature
yet. Therefore, I attached the current developer version of
"cons_countsols.c" which includes this feature (just exchange the files).
To
use it, you have to set the parameter "constraints/countsols/sollimit" to
your desired number. This is done as follows:

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

After that SCIP stops if this number is exceeded. Then you can reset this
number and continue counting by calling SCIPcount() again.

Note that the solutions SCIP will collect are usually collected in the way
that the search tree is processed in a depth first manner.

I hope this helps. If you need more help, please let as know.


Best Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cons_countsols.c
Type: text/x-csrc
Size: 62306 bytes
Desc: not available
Url : http://listserv.zib.de/mailman/private/scip/attachments/20090504/586f88d0/cons_countsols.bin