[SCIP] column and row generation

Wed May 9 09:49:09 CEST 2018

Dear Tilo,

I would recommend to use constraints instead of rows in this case. Rows 
are not checked for feasibility, only constraints. One effect is that 
the locks are not increased and you can work around this as Ambros 
suggested. But if some heuristic constructs a solution candidate, it may 
be accepted although it violates the row. Essentially, if you add a row, 
this has only the aim to tighten your LP relaxation, but it should not 
alter the set of feasible solutions w.r.t. your constraint set. But 
since your additional constraints are essential for the feasibility of a 
solution, you should add them as constraints.

Best,
Gerald

On 09.05.2018 09:16, Ambros Gleixner wrote:
> 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
>>
>>
>>
>