[SCIP] column and row generation

[Ambros Gleixner]

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