[Scip] Adding constraints to a LP on the fly

[Daniel Skates]

Hello,

I have been using Gurobi to solve some problems that can be expressed as
binary linear problems (with objective=0) for my honours thesis.  I had
~10,000 cases to run, and I am into the last 400 or so, however, each case
increases the difficulty.  Unfortunately, I have ran into issues with the
time it took to solve - some cases are taking weeks to prove infeasible (as
in all solutions found, see below) - and my deadline is fast approaching.

In Gurobi, I would load the initial LP, and begin optimizing.  If the model
was infeasible, I'd quit, but if I found a solution, I'd add a constraint
excluding that solution (for a given solution, the sum over the variables
equal to 1 in this solution is < the number of variables equal to 1 in this
solution), then allow Gurobi to optimize again, and repeat.

I have been experimenting with SCIP, in hopes that SCIP's constraint
satisfaction code would help speed up my search.  My code is written in C,
similar to the Queens example (with no custom plugins).  While I can easily
find a first solution using SCIP, my problem is with adding new constraints
to remove that solution.

My code is at http://dl.dropbox.com/u/12269404/main.c
I have marked a point in my code with //###### where I have trouble

After finding a solution, I create an array of variables and coefficients,
then try calling
SCIPcreateConsLinear
But this gives an error:
[src/scip/scip.c:11725] ERROR: invalid SCIP stage <8>
[src/scip/cons_linear.c:10356] ERROR: Error <0> in function call
[src/main.c:188] ERROR: Error <0> in function call

So I tried:
SCIPfreeSolve(scip, FALSE)
SCIPcreateConsLinear
And this gave an error:
[src/scip/scip.c:11725] ERROR: invalid SCIP stage <3>
[src/scip/cons_linear.c:10356] ERROR: Error <0> in function call
[src/main.c:188] ERROR: Error <0> in function call

Finally, I tried:
 SCIPfreeSolve(scip, FALSE)
SCIPfreeTransform
SCIPcreateConsLinear
And this gave an error:
[src/scip/lpi_grb.c:1038] ERROR: Gurobi error 10003:
[src/scip/lp.c:6925] ERROR: Error <-6> in function call
[src/scip/scip.c:5655] ERROR: Error <-6> in function call
[src/scip/scip.c:6631] ERROR: Error <-6> in function call
[src/scip/scip.c:6806] ERROR: Error <-6> in function call
[src/main.c:143] ERROR: Error <-6> in function call

Note that I'm linking with Gurobi as my LP solver.  With Gurobi, after a
solution is found, a constraint can be added, and the next GRBoptimize call
starts from a "warm" state (partially solved) instead of the "cold" state
when you load the model.  I'm trying to emulate this, as the new constraint
only prevents the current solution from being found again, and doesn't
change the model.

Well almost.  I should also point out that when I have found one solution, I
use the symmetry of my problem to find additional solutions (not shown in my
code for simplicity).  Thus when I have found one solution, I need to add
several similar constraints, not just the one preventing my current
solution.

Below is a simple concrete example (14 variables, 8 constraints).  Actual
lack of time problems occur with ~2000 variables & ~1000 constraints.  I was
also wondering if there are any SCIP parameters I should be aware of to
speed up my search?

I have an example of a much more difficult problem
http://dl.dropbox.com/u/12269404/2-1.lp (over a week), and a moderate
problem http://dl.dropbox.com/u/12269404/model.lp (< 30 mins).  Note that
these both have constraints of the form:
pi - pj = 0
And so I am hoping that SCIP will be better at solving them then Gurobi on
its own!

To summarize:
1) How do I add a constraint after finding a solution (preferably without
undoing all of SCIP/Gurobi's previous work)?
2) What parameters should I use to speed up this sort of problem?

Thanks for your time,

Daniel


############################
Maximize
 Obj:
Subject to
 c0: +1 p1 +1 p2 +1 p3 +2 l0 = +2
 c1: +1 p0 +1 p2 +1 p4 +2 l1 = +2
 c2: +1 p0 +1 p1 +1 p5 +2 l2 = +2
 c3: +1 p0 +1 p3 +1 p6 +2 l3 = +2
 c4: +1 p1 +1 p4 +1 p6 +2 l4 = +2
 c5: +1 p2 +1 p5 +1 p6 +2 l5 = +2
 c6: +1 p3 +1 p4 +1 p5 +2 l6 = +2
 sum: +1 p0 +1 p1 +1 p2 +1 p3 +1 p4 +1 p5 +1 p6 = +4
Binaries
 p0 l0 p1 l1 p2 l2 p3 l3 p4 l4 p5 l5 p6 l6
End
############################
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20111015/2d48f68d/attachment.html