[SCIP] column and row generation

[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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.cpp
Type: text/x-c++src
Size: 4404 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20180508/15dd2bd9/attachment.bin>