[SCIP] column and row generation

[Ambros Gleixner]

Hi Tilo,


Am 09.05.2018 um 08:28 schrieb Tilo Wiedera:
> Dear Ambros,
> 
> thank you for the swift reply.
> Using constraints instead of rows does indeed fix the problem observed in
> my minimal example.
> I'll use the correct result when adding rows instead of constraints and
> switch to using the lower case types—thank you for these remarks.

upper cases are the right versions.


>> I am guessing that option 1 is more efficient, but for that to work you
>> need to add locks to variable y right after you create it.
> 
> Could you elaborate on locking variables (manually)?

Have you looked at the CONSLOCK section in

http://scip.zib.de/doc-5.0.1/html/CONS.php

?

Best,
Ambros


> Do I simply increase the lock counters of variable y by one using
> SCIPaddVarLocks()?
> Am I right in assuming that a variable cannot be rounded up (down) as long
> as the number of up (resp. down) locks is not zero?
> 
> Cheers
> Tilo
> 
> On Tue, May 8, 2018 at 7:22 PM Ambros Gleixner <gleixner at zib.de> wrote:
> 
>> Dear Tilo,
> 
>> Thank you for your question.  Good that you sent such a reduced example
>> code.
> 
>> The reason is probably that the newly added variable has no locks, and
>> is only restricted by a row in the separation storage of SCIP, no check
>> constraint.  As such, SCIP is allowed to fix it to zero in propagation.
> 
>> Similarly, note that you add a row but set the result pointer to
>> SCIP_CONSADDED.  This is inconsistent.  Either 1. you add a row and set
>> the result pointer to SCIP_SEPARATED, or 2. you add a linear constraint
>> and set the result pointer to SCIP_CONSADDED.  Maybe see
> 
>> http://scip.zib.de/doc-5.0.1/html/FAQ.php#columnsvsvariables
> 
>> for the difference between rows and constraints.
> 
>> I am guessing that option 1 is more efficient, but for that to work you
>> need to add locks to variable y right after you create it.
> 
>> Best,
>> Ambros
> 
> 
>> PS: You should use the capitalized versions SCIP_ROW, SCIP_VAR,
>> SCIP_CONS, ... instead of SCIP_Row, ...
> 
> 
> 
>> Am 08.05.2018 um 11:25 schrieb Tilo Wiedera:
>>> Dear SCIP developers and users,
>>>
>>> I am working on a minimization problem that I would like to solve using
>>> SCIP's c++ interface. All my variables are binary and I need to use
> custom
>>> constraint generation. However, some of the constraints (that I
> generate in
>>> a constraint handler) require the introduction of new variables. In my
> case,
>>> such newly introduced variables neither decrease the dual bound
>>> nor do they occur in the objective. Particularly, all constraints
> existing
>>> so far remain valid without modification. Instead, these new variables
>>> are used only in new constraints generated in separation steps
> thereafter.
>>>
>>> Question: how should one implement this type of variable generation?
>>> Can new variables be added in the constraint handler during constraint
>>> generation? Do I have to implement a variable pricer instead?
>>>
>>> I've tested several implementation approaches (including the use of
>>> SCIP's pricer interface) and none seem to work.
>>> Adding the variables results in non-optimal solutions. I suspect that
> SCIP
>>> assumes the new variables to be fixed to zero as newly added constraints
>>> using these new variables seem to cut off valid solutions.
>>>
>>> I am using SCIP 5.0.1, CPLEX 12.7.1, and GCC 7.2.0 on a x64 Linux
> machine.
>>>
>>> I've reduced the problem to a minimal LP that consists of only *two*
>>> continuous variables:
>>>             min x
>>>             s.t. x >= 1 and y >= x
>>> The initial SCIP instance contains only the variable x and bounds it by
> 0
>>> <= x.
>>> The constraint handler first checks whether x < 1.
>>> If true, the constraint x >= 1 is added and the constraint handler
> returns.
>>> Otherwise, x >= 1, and the constraint handler checks whether y exists
> and y
>>>> = x. If not, the variable y and the constraint y >= x are added.
>>> Clearly, x = y = 1 is a feasible solution but there must be an error in
> my
>>> implementation as SCIP claims the problem is infeasible.
>>> I've attached the source code of this minimal failing example.
>>>
>>> Printing the transformed problem after solving reveals that SCIP assumes
>>> the bounds 0 <= y <= 0.
>>>
>>> Any hints are highly appreciated.
>>>
>>> Kind regards
>>> Tilo
>>>
>>>
>>> --
>>> ---------------------------------------------
>>> Tilo Wiedera, M.Sc.
>>> Research Assistant
>>> Theoretical Computer Science
>>> ---------------------------------------------
>>> Institute of Computer Science
>>> Osnabrueck University
>>> Wachsbleiche 27, D-49090 Osnabrueck, GERMANY
>>> ---------------------------------------------
>>> Webpage: http://tcs.uos.de/staff/wiedera
>>> Mail: twiedera at uni-osnabrueck.de
>>>
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> https://listserv.zib.de/mailman/listinfo/scip
>>>
> 
>> --
>> Ambros Gleixner, Research Group Mathematical Optimization Methods at
>> Zuse Institute Berlin, http://www.zib.de/gleixner
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
> 
> 
> 

-- 
Ambros Gleixner, Research Group Mathematical Optimization Methods at 
Zuse Institute Berlin, http://www.zib.de/gleixner