[SCIP] column and row generation

Tilo Wiedera twiedera at uos.de
Wed May 9 08:28:29 CEST 2018


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.

> 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)?
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



-- 
---------------------------------------------
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



More information about the Scip mailing list