[Scip] Adding constraints to a LP on the fly

[Stefan Vigerske]

Hi,

> "grbenv = NULL in lpi_grb.c:1095" I'll give that a try, but even if it
> works, it would mean that Gurobi is restarting its search from a "cold"
> state, and ignoring the current work its done!

Gurobi is only used to solve the LP relaxation in SCIP, anyway.

> You mentioned "You can only add constraints before SCIP transformed the
> problem, or during presolve and solve."
> Would SCIP allow me to write a plugin to intercept a solution during solve,
> add my constraints, then continue until the model is infeasible?  If so,
> could you suggest how?  It would be a lot slower to have to restart, just
> because a solution is found.  The constraints would build on the already
> done work.

You could add a simple constraint handler (see 
http://scip.zib.de/doc/html/CONS.html) with a very low priority that 
declares every solution it has to check or enforce as infeasible, and 
possibly also adds constraints to rule out symmetric solutions.
The low priority is important to get only to those solutions that have 
already been checked by the other constraint handlers (esp. linear and 
integral), so your constraint handler would only see actually feasible 
solutions.

> I saw something about the "solution counting feature of SCIP" somewhere in
> the documentation, but whenever a solution has been found, it knocks out
> many more.  That's why I want to be able to add multiple constraints.

It may still be a good starting point, since it already does what is 
written above.
Also it does some additional checks to ensure a valid counting process 
(see the method checkParameters), i.e., to ensure that all solutions are 
enumerated.

Stefan

>
> Thanks
>
> Daniel
>
> On Sun, Oct 16, 2011 at 8:36 PM, Stefan Vigerske
> <stefan at math.hu-berlin.de>wrote:
>
>> Hi,
>>
>>
>>   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
>>>
>>
>> Can you try if it works if you add a grbenv = NULL in lpi_grb.c:1095, i.e.,
>> immediately after the GRBfreeenv(grbenv); ?
>>
>>   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<http://dl.dropbox.com/u/12269404/2-1.lp>(over a week), and a moderate
>>> problem http://dl.dropbox.com/u/**12269404/model.lp<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)?
>>>
>>
>> The third one was correct. You can only add constraints before SCIP
>> transformed the problem, or during presolve and solve.
>>
>>
>>   2) What parameters should I use to speed up this sort of problem?
>>>
>>
>> Have you looked whether the solution counting feature of SCIP may be
>> helpful?
>>
>> Stefan
>>
>>
>>> 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
>>> ############################
>>>
>>>
>>>
>>>
>>> ______________________________**_________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/**mailman/listinfo/scip<http://listserv.zib.de/mailman/listinfo/scip>
>>>
>>
>>
>


-- 
Stefan Vigerske
Humboldt University Berlin, Numerical Mathematics
http://www.math.hu-berlin.de/~stefan