SCIP

    Solving Constraint Integer Programs

    sepa_cgmip.c
    Go to the documentation of this file.
    1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    2/* */
    3/* This file is part of the program and library */
    4/* SCIP --- Solving Constraint Integer Programs */
    5/* */
    6/* Copyright (c) 2002-2026 Zuse Institute Berlin (ZIB) */
    7/* */
    8/* Licensed under the Apache License, Version 2.0 (the "License"); */
    9/* you may not use this file except in compliance with the License. */
    10/* You may obtain a copy of the License at */
    11/* */
    12/* http://www.apache.org/licenses/LICENSE-2.0 */
    13/* */
    14/* Unless required by applicable law or agreed to in writing, software */
    15/* distributed under the License is distributed on an "AS IS" BASIS, */
    16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
    17/* See the License for the specific language governing permissions and */
    18/* limitations under the License. */
    19/* */
    20/* You should have received a copy of the Apache-2.0 license */
    21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
    22/* */
    23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    24/* #define SCIP_WRITEPROB */
    25/* #define SCIP_OUTPUT */
    26/**@file sepa_cgmip.c
    27 * @ingroup DEFPLUGINS_SEPA
    28 * @brief Chvatal-Gomory cuts computed via a sub-MIP
    29 * @author Marc Pfetsch
    30 *
    31 * Separate Chvátal-Gomory cuts using a sub-MIP. The approach is based on the following papers.
    32 *
    33 * M. Fischetti and A. Lodi@n
    34 * Optimizing over the first Chvátal closure,@n
    35 * in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization IPCO 2005,@n
    36 * LNCS 3509, pp. 12-22. Springer, Berlin Heidelberg New York (2005)
    37 *
    38 * M. Fischetti and A. Lodi@n
    39 * Optimizing over the first Chvátal closure,@n
    40 * Mathematical Programming 110, 3-20 (2007)
    41 *
    42 * P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, and A. Lodi@n
    43 * Projected Chvátal-Gomory cuts for mixed integer linear programs,@n
    44 * Mathematical Programming 113, No. 2 (2008)
    45 *
    46 *
    47 * There are several possibilities to generate the final cut:
    48 *
    49 * - The CMIR-routines of SCIP can be used (if @p usecmir is true). One can determine which bound is
    50 * used in the rounding operation (if @p cmirownbounds is true) or let SCIP choose the best. This
    51 * version is generally numerically the most stable.
    52 * - If @p usestrongcg is true, we try to generate Strong-CG cuts (as done in sepa_strongcg.c).
    53 * - One can directly generate the CG-cut as computed (if @p usecmir and @p usestrongcg are
    54 * false). The cut is not taken from the solution of the MIP, but is recomputed, and some care (but
    55 * not as much as in the first version) has been taken to create a valid cut.
    56 *
    57 * The computation time of the separation MIP is limited as follows:
    58 * - There is a node limit (parameters @a minnodelimit and @a maxnodelimit).
    59 * - There is a time limit (parameter @a timelimit).
    60 * - If paramter @a earlyterm is true, the separation is run until the first cut that is violated is
    61 * found. (Note that these cuts are not necessarily added to the LP, because here also the norm of
    62 * the cuts are taken into account - which cannot easily be included into the separation subscip.)
    63 * Then the solution process is continued for a certain number of nodes.
    64 *
    65 * @todo Check whether one can weaken the conditions on the continuous variables.
    66 * @todo Use pointers to originating separators to sort out cuts that should not be used.
    67 *
    68 * @warning This separator should be used carefully - it may require a long separation time.
    69 */
    70
    71/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    72
    73#include "blockmemshell/memory.h"
    74#include "scip/cons_linear.h"
    75#include "scip/cuts.h"
    76#include "scip/pub_cons.h"
    77#include "scip/pub_lp.h"
    78#include "scip/pub_message.h"
    79#include "scip/pub_misc.h"
    80#include "scip/pub_sepa.h"
    81#include "scip/pub_var.h"
    82#include "scip/scip_branch.h"
    83#include "scip/scip_cons.h"
    84#include "scip/scip_copy.h"
    85#include "scip/scip_cut.h"
    86#include "scip/scip_general.h"
    87#include "scip/scip_lp.h"
    88#include "scip/scip_mem.h"
    89#include "scip/scip_message.h"
    90#include "scip/scip_numerics.h"
    91#include "scip/scip_param.h"
    92#include "scip/scip_prob.h"
    93#include "scip/scip_randnumgen.h"
    94#include "scip/scip_sepa.h"
    95#include "scip/scip_sol.h"
    96#include "scip/scip_solve.h"
    97#include "scip/scip_solvingstats.h"
    98#include "scip/scip_timing.h"
    99#include "scip/scip_tree.h"
    100#include "scip/scip_var.h"
    101#include "scip/scipdefplugins.h"
    102#include "scip/sepa_cgmip.h"
    103
    104
    105#define SEPA_NAME "cgmip"
    106#define SEPA_DESC "Chvatal-Gomory cuts via MIPs separator"
    107#define SEPA_PRIORITY -1000
    108#define SEPA_FREQ -1
    109#define SEPA_MAXBOUNDDIST 0.0
    110#define SEPA_USESSUBSCIP TRUE /**< does the separator use a secondary SCIP instance? */
    111#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
    112
    113#define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */
    114#define DEFAULT_MAXROUNDSROOT 50 /**< maximal number of separation rounds in the root node (-1: unlimited) */
    115#define DEFAULT_MAXDEPTH -1 /**< maximal depth at which the separator is applied */
    116#define DEFAULT_DECISIONTREE FALSE /**< Use decision tree to turn separation on/off? */
    117#define DEFAULT_TIMELIMIT 1e20 /**< time limit for sub-MIP (set to infinity in order to be deterministic) */
    118#define DEFAULT_MEMORYLIMIT 1e20 /**< memory limit for sub-MIP */
    119#define DEFAULT_CUTCOEFBND 1000.0 /**< bounds on the values of the coefficients in the CG-cut */
    120#define DEFAULT_MINNODELIMIT 500LL /**< minimum number of nodes considered for sub-MIP (-1: unlimited) */
    121#define DEFAULT_MAXNODELIMIT 5000LL /**< maximum number of nodes considered for sub-MIP (-1: unlimited) */
    122#define DEFAULT_ONLYACTIVEROWS FALSE /**< Use only active rows to generate cuts? */
    123#define DEFAULT_MAXROWAGE -1 /**< maximal age of rows to consider if onlyactiverows is false */
    124#define DEFAULT_ONLYRANKONE FALSE /**< Separate rank 1 inequalities w.r.t. CG-MIP separator? */
    125#define DEFAULT_ONLYINTVARS FALSE /**< Generate cuts for problems with only integer variables? */
    126#define DEFAULT_CONTCONVERT FALSE /**< Convert some integral variables to be continuous to reduce the size of the sub-MIP? */
    127#define DEFAULT_CONTCONVFRAC 0.1 /**< fraction of integral variables converted to be continuous (if contconvert) */
    128#define DEFAULT_CONTCONVMIN 100 /**< minimum number of integral variables before some are converted to be continuous */
    129#define DEFAULT_INTCONVERT FALSE /**< Convert some integral variables attaining fractional values to have integral value? */
    130#define DEFAULT_INTCONVFRAC 0.1 /**< fraction of fractional integral variables converted to have integral value (if intconvert) */
    131#define DEFAULT_INTCONVMIN 100 /**< minimum number of integral variables before some are converted to have integral value */
    132#define DEFAULT_SKIPMULTBOUNDS TRUE /**< Skip the upper bounds on the multipliers in the sub-MIP? */
    133#define DEFAULT_OBJLONE FALSE /**< Should the objective of the sub-MIP only minimize the l1-norm of the multipliers? */
    134#define DEFAULT_OBJWEIGHT 1e-03 /**< objective weight for artificial variables */
    135#define DEFAULT_OBJWEIGHTSIZE TRUE /**< Weight each row by its size? */
    136#define DEFAULT_DYNAMICCUTS TRUE /**< Should generated cuts be removed from the LP if they are no longer tight? */
    137#define DEFAULT_USECMIR TRUE /**< Use CMIR-generator (otherwise add cut directly)? */
    138#define DEFAULT_USESTRONGCG FALSE /**< Use strong CG-function to strengthen cut? */
    139#define DEFAULT_CMIROWNBOUNDS FALSE /**< Tell CMIR-generator which bounds to used in rounding? */
    140#define DEFAULT_USECUTPOOL TRUE /**< Use cutpool to store CG-cuts even if the are not efficient? */
    141#define DEFAULT_PRIMALSEPARATION TRUE /**< Only separate cuts that are tight for the best feasible solution? */
    142#define DEFAULT_EARLYTERM TRUE /**< Terminate separation if a violated (but possibly sub-optimal) cut has been found? */
    143#define DEFAULT_ADDVIOLATIONCONS FALSE /**< Add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?*/
    144#define DEFAULT_ADDVIOLCONSHDLR FALSE /**< Add constraint handler to filter out violated cuts? */
    145#define DEFAULT_CONSHDLRUSENORM TRUE /**< Should the violation constraint handler use the norm of a cut to check for feasibility? */
    146#define DEFAULT_USEOBJUB FALSE /**< Use upper bound on objective function (via primal solution)? */
    147#define DEFAULT_USEOBJLB FALSE /**< Use lower bound on objective function (via lower bound)? */
    148#define DEFAULT_SUBSCIPFAST TRUE /**< Should the settings for the sub-MIP be optimized for speed? */
    149#define DEFAULT_OUTPUT FALSE /**< Should information about the sub-MIP and cuts be displayed? */
    150#define DEFAULT_RANDSEED 101 /**< start random seed for random number generation */
    151#define DEFAULT_GENPRIMALSOLS FALSE /**< Try to generate primal solutions from Gomory cuts? */
    152
    153
    154#define NROWSTOOSMALL 5 /**< only separate if the number of rows is larger than this number */
    155#define NCOLSTOOSMALL 5 /**< only separate if the number of columns is larger than this number */
    156
    157#define EPSILONVALUE 1e-03 /**< epsilon value needed to model strict-inequalities */
    158#define BETAEPSILONVALUE 1e-02 /**< epsilon value for fracbeta - is larger than EPSILONVALUE for numerical stability */
    159#define STALLNODELIMIT 1000LL /**< number of stalling nodes if earlyterm is true */
    160#define CONSHDLRFULLNORM FALSE /**< compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true) */
    161#define MINEFFICACY 0.05 /**< minimum efficacy of a cut - compare set.c */
    162#define MAXNSOLS 1000 /**< maximal number of solutions stored in sub-SCIP */
    163#define OBJWEIGHTRANGE 0.01 /**< maximal range of scaling of objective w.r.t. size of rows */
    164
    165/* parameters used for CMIR-generation (taken from sepa_gomory) */
    166#define BOUNDSWITCH 0.9999
    167#define VARTYPEUSEVBDS 2 /**< We allow variable bound substitution for variables with continuous vartype only.
    168 * See SCIPcalcMIR() for more information. */
    169#define POSTPROCESS TRUE
    170#define MINFRAC 0.0009 /**< to allow a deviation of the same size as EPSILONVALUE */
    171#define MAXFRAC 0.9991 /**< to allow a deviation of the same size as EPSILONVALUE */
    172#define FIXINTEGRALRHS FALSE
    173#define MAKECONTINTEGRAL FALSE
    174#define MAXWEIGHTRANGE 1e+05 /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
    175#define AWAY 0.005 /**< minimal fractionality of a basic variable in order to try GMI cut */
    176#define SEPARATEROWS TRUE /**< Separate rows with integral slack? */
    177
    178#define MAXAGGRLEN(nvars) nvars /**< currently very large to allow any generation; an alternative would be (0.1*(nvars)+1000) */
    179
    180/** separator data */
    181struct SCIP_SepaData
    182{
    183 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
    184 int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
    185 int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
    186 int maxdepth; /**< maximal depth at which the separator is applied */
    187 SCIP_Bool decisiontree; /**< Use decision tree to turn separation on/off? */
    188 SCIP_Real timelimit; /**< time limit for subscip */
    189 SCIP_Real memorylimit; /**< memory limit for subscip */
    190 SCIP_Longint minnodelimit; /**< minimum number of nodes considered for sub-MIP (-1: unlimited) */
    191 SCIP_Longint maxnodelimit; /**< maximum number of nodes considered for sub-MIP (-1: unlimited) */
    192 SCIP_Real cutcoefbnd; /**< bounds on the values of the coefficients in the CG-cut */
    193 SCIP_Bool onlyactiverows; /**< Use only active rows to generate cuts? */
    194 int maxrowage; /**< maximal age of rows to consider if onlyactiverows is false */
    195 SCIP_Bool onlyrankone; /**< Separate only rank 1 inequalities w.r.t. CG-MIP separator? */
    196 SCIP_Bool onlyintvars; /**< Generate cuts for problems with only integer variables? */
    197 SCIP_Bool allowlocal; /**< Allow local cuts? */
    198 SCIP_Bool contconvert; /**< Convert some integral variables to be continuous to reduce the size of the sub-MIP? */
    199 SCIP_Real contconvfrac; /**< fraction of integral variables converted to be continuous (if contconvert) */
    200 int contconvmin; /**< minimum number of integral variables before some are converted to be continuous */
    201 SCIP_Bool intconvert; /**< Convert some integral variables attaining fractional values to have integral value? */
    202 SCIP_Real intconvfrac; /**< fraction of frac. integral variables converted to have integral value (if intconvert) */
    203 int intconvmin; /**< minimum number of integral variables before some are converted to have integral value */
    204 SCIP_Bool skipmultbounds; /**< Skip the upper bounds on the multipliers in the sub-MIP? */
    205 SCIP_Bool objlone; /**< Should the objective of the sub-MIP only minimize the l1-norm of the multipliers? */
    206 SCIP_Real objweight; /**< objective weight for artificial variables */
    207 SCIP_Bool objweightsize; /**< Weight each row by its size? */
    208 SCIP_Bool dynamiccuts; /**< Should generated cuts be removed from the LP if they are no longer tight? */
    209 SCIP_Bool usecmir; /**< Use CMIR-generator (otherwise add cut directly)? */
    210 SCIP_Bool usestrongcg; /**< Use strong CG-function to strengthen cut? */
    211 SCIP_Bool cmirownbounds; /**< Tell CMIR-generator which bounds to used in rounding? */
    212 SCIP_Bool usecutpool; /**< Use cutpool to store CG-cuts even if the are not efficient? */
    213 SCIP_Bool primalseparation; /**< Only separate cuts that are tight for the best feasible solution? */
    214 SCIP_Bool earlyterm; /**< Terminate separation if a violated (but possibly sub-optimal) cut has been found? */
    215 SCIP_Bool addviolationcons; /**< Add constraint to subscip that only allows violated cuts? */
    216 SCIP_Bool addviolconshdlr; /**< Add constraint handler to filter out violated cuts? */
    217 SCIP_Bool conshdlrusenorm; /**< Should the violation constraint handler use the cut-norm to check for feasibility? */
    218 SCIP_Bool useobjub; /**< Use upper bound on objective function (via primal solution)? */
    219 SCIP_Bool useobjlb; /**< Use lower bound on objective function (via lower bound)? */
    220 SCIP_Bool subscipfast; /**< Should the settings for the sub-MIP be optimized for speed? */
    221 SCIP_Bool output; /**< Should information about the sub-MIP and cuts be displayed? */
    222 SCIP_Bool genprimalsols; /**< Try to generate primal solutions from Gomory cuts? */
    223};
    224
    225
    226/** what happens for columns in the LP */
    227enum CGMIP_ColType
    228{
    229 colPresent = 0, /**< column is present in the separating MIP */
    230 colContinuous = 1, /**< column corresponds to a continuous variable */
    231 colConverted = 2, /**< column is converted to be continuous */
    232 colAtUb = 3, /**< variable corresponding to column was at it's upper bound and was complemented */
    233 colAtLb = 4 /**< variable corresponding to column was at it's lower bound (possibly complemented) */
    234};
    235typedef enum CGMIP_ColType CGMIP_COLTYPE;
    236
    237
    238/** data for the sub-MIP */
    239struct CGMIP_MIPData
    240{
    241 SCIP* subscip; /**< pointer to (sub)SCIP data structure containing the auxiliary IP */
    242 unsigned int m; /**< number of constraints of subscip */
    243 unsigned int n; /**< number of variables of subscip */
    244 unsigned int nrows; /**< number of rows of original LP */
    245 unsigned int ncols; /**< number of columns of original LP */
    246 unsigned int ntotalrows; /**< number of total rows used (possibly including objective rows) */
    247
    248 SCIP_VAR** alpha; /**< cut coefficient variable (NULL if not in separating MIP) */
    249 SCIP_VAR* beta; /**< rhs of cut */
    250 SCIP_VAR** fracalpha; /**< fractional part of lhs of cut (NULL if not present) */
    251 SCIP_VAR* fracbeta; /**< fractional part of rhs of cut */
    252 CGMIP_COLTYPE* coltype; /**< type for the columns */
    253 SCIP_Bool* iscomplemented; /**< whether the variable was complemented */
    254 SCIP_Bool* isshifted; /**< whether the variable was shifted to have 0 lower bound */
    255
    256 SCIP_VAR** ylhs; /**< auxiliary row variables for lhs (NULL if not present) */
    257 SCIP_VAR** yrhs; /**< auxiliary row variables for rhs (NULL if not present) */
    258
    259 SCIP_VAR** z; /**< auxiliary variables for upper bounds (NULL if not present) */
    260
    261 SCIP_Real* lhs; /**< transformed left hand sides */
    262 SCIP_Real* rhs; /**< transformed left hand sides */
    263
    264 char normtype; /**< type of norm to use for efficacy norm calculation */
    265
    266 /* additional redundant data */
    267 SCIP_Bool conshdlrusenorm; /**< copy from sepadata */
    268 SCIP_Bool conshdlrfullnorm; /**< compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true) */
    269 SCIP* scip; /**< original SCIP */
    270 SCIP_SEPA* sepa; /**< CG-cut separator */
    271 SCIP_SEPADATA* sepadata; /**< CG-cut separator data */
    272};
    273typedef struct CGMIP_MIPData CGMIP_MIPDATA;
    274
    275
    276/*
    277 * constraint handler to filter out violated cuts
    278 */
    279
    280/* constraint handler properties */
    281#define CONSHDLR_NAME "violatedCuts"
    282#define CONSHDLR_DESC "only allow solutions corresponding to violated cuts"
    283
    284/** constraint handler data */
    285struct SCIP_ConshdlrData
    286{
    287 CGMIP_MIPDATA* mipdata; /**< data of separating sub-MIP */
    288};
    289
    290/* temporary forward declaration */
    291static
    292SCIP_RETCODE computeCut(
    293 SCIP* scip, /**< original scip */
    294 SCIP_SEPA* sepa, /**< separator */
    295 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
    296 SCIP_SEPADATA* sepadata, /**< separator data */
    297 SCIP_SOL* sol, /**< current solution for sub-MIP */
    298 SCIP_Bool usefrac, /**< use fractional value of multipliers */
    299 SCIP_Real* cutcoefs, /**< coefficients of the cut */
    300 SCIP_Real* cutrhs, /**< rhs of the cut */
    301 SCIP_Bool* localrowsused, /**< pointer to store whether local rows were used in summation */
    302 SCIP_Bool* localboundsused, /**< pointer to store whether local bounds were used in summation */
    303 int * cutrank, /**< pointer to store the cut rank */
    304 SCIP_Bool* success /**< whether we produced a valid cut */
    305 );
    306
    307/** check whether cut corresponding to solution is violated */
    308static
    309SCIP_RETCODE solCutIsViolated(
    310 SCIP* scip, /**< SCIP data structure */
    311 CGMIP_MIPDATA* mipdata, /**< data of separating sub-MIP */
    312 SCIP_SOL* sol, /**< solution to be checked */
    313 SCIP_Bool* violated /**< pointer to store if the cut is violated */
    314 )
    315{
    316 SCIP_Real cutsqrnorm = 0.0;
    317 SCIP* subscip;
    318 SCIP_Real act;
    319 SCIP_Real norm;
    320 SCIP_Real val;
    321 SCIP_VAR* var;
    322 SCIP_Real rhs;
    323 unsigned int j;
    324 int len = 0;
    325
    326 assert( mipdata != NULL );
    327 subscip = mipdata->subscip;
    328 assert( subscip != NULL );
    329 assert( violated != NULL );
    330
    331 /* initialize activity and norm */
    332 act = 0.0;
    333 norm = 1.0;
    334 *violated = FALSE;
    335
    336 /* compute activity and norm */
    337 if ( mipdata->conshdlrusenorm )
    338 {
    339 /* check whether we should compute the full cut and then compute the norm */
    340 if ( mipdata->conshdlrfullnorm )
    341 {
    342 SCIP_Real* cutcoefs;
    343 SCIP_Bool localrowsused;
    344 SCIP_Bool localboundsused;
    345 SCIP_Bool success;
    346 SCIP_VAR** vars;
    347 int cutrank = 0;
    348 int nvars;
    349
    350 /* get data */
    351 SCIP_CALL( SCIPgetVarsData(mipdata->scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
    352 assert(nvars >= 0);
    353 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
    354
    355 /* compute coefficients */
    356 SCIP_CALL( computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, TRUE, cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) );
    357
    358 /* try again if cut was not valid */
    359 if ( ! success )
    360 {
    361 SCIP_CALL( computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, FALSE,
    362 cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) );
    363
    364 if ( ! success )
    365 return SCIP_OKAY;
    366 }
    367
    368#ifdef SCIP_MORE_DEBUG
    369 for (j = 0; j < (unsigned int) nvars; ++j)
    370 {
    371 if ( ! SCIPisZero(scip, cutcoefs[j]) )
    372 SCIPinfoMessage(scip, NULL, "+ %f x%d", cutcoefs[j], j);
    373 }
    374 SCIPinfoMessage(scip, NULL, "\n");
    375#endif
    376
    377 /* compute activity and Euclidean norm (todo: use arbitrary norm) */
    378 cutsqrnorm = 0.0;
    379 for (j = 0; j < (unsigned int) nvars; ++j)
    380 {
    381 if ( ! SCIPisZero(scip, cutcoefs[j]) )
    382 {
    383 act += cutcoefs[j] * SCIPvarGetLPSol(vars[j]);
    384 cutsqrnorm += SQR(cutcoefs[j]);
    385 }
    386 }
    387 norm = sqrt(cutsqrnorm);
    388
    389 SCIPfreeBufferArray(scip, &cutcoefs);
    390 } /*lint !e438*/
    391 else
    392 {
    393 switch ( mipdata->normtype )
    394 {
    395 case 'e':
    396 cutsqrnorm = 0.0;
    397 for (j = 0; j < mipdata->ncols; ++j)
    398 {
    399 var = mipdata->alpha[j];
    400 if ( var == NULL )
    401 continue;
    402
    403 val = SCIPgetSolVal(subscip, sol, var);
    404 if ( !SCIPisZero(scip, val) )
    405 {
    406 act += val * SCIPvarGetObj(var);
    407 cutsqrnorm += SQR(val);
    408 }
    409 }
    410 norm = sqrt(cutsqrnorm);
    411 break;
    412 case 'm':
    413 for (j = 0; j < mipdata->ncols; ++j)
    414 {
    415 var = mipdata->alpha[j];
    416 if ( var == NULL )
    417 continue;
    418
    419 val = SCIPgetSolVal(subscip, sol, var);
    420 if ( !SCIPisZero(scip, val) )
    421 {
    422 act += val * SCIPvarGetObj(var);
    423 if ( REALABS(val) > norm )
    424 norm = REALABS(val);
    425 }
    426 }
    427 break;
    428 case 's':
    429 for (j = 0; j < mipdata->ncols; ++j)
    430 {
    431 var = mipdata->alpha[j];
    432 if ( var == NULL )
    433 continue;
    434
    435 val = SCIPgetSolVal(subscip, sol, var);
    436 if ( !SCIPisZero(scip, val) )
    437 {
    438 act += val * SCIPvarGetObj(var);
    439 norm += REALABS(val);
    440 }
    441 }
    442 break;
    443 case 'd':
    444 for (j = 0; j < mipdata->ncols; ++j)
    445 {
    446 var = mipdata->alpha[j];
    447 if ( var == NULL )
    448 continue;
    449
    450 val = SCIPgetSolVal(subscip, sol, var);
    451 if ( !SCIPisZero(scip, val) )
    452 {
    453 act += val * SCIPvarGetObj(var);
    454 ++len;
    455 }
    456 }
    457 if ( len > 0 )
    458 norm = 1.0;
    459 break;
    460 default:
    461 SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", mipdata->normtype);
    462 return SCIP_INVALIDDATA;
    463 }
    464 /* get rhs */
    465 rhs = SCIPgetSolVal(subscip, sol, mipdata->beta);
    466 }
    467
    468 /* if norm is 0, the cut is trivial */
    469 if ( SCIPisZero(subscip, norm) )
    470 return SCIP_OKAY;
    471 }
    472 else
    473 {
    474 for (j = 0; j < mipdata->ncols; ++j)
    475 {
    476 var = mipdata->alpha[j];
    477 if ( var == NULL )
    478 continue;
    479
    480 val = SCIPgetSolVal(subscip, sol, var);
    481 if ( !SCIPisZero(subscip, val) )
    482 act += SCIPvarGetObj(var) * val;
    483 }
    484
    485 /* get rhs */
    486 rhs = SCIPgetSolVal(subscip, sol, mipdata->beta);
    487 }
    488
    489#ifdef SCIP_DEBUG
    490 if ( SCIPisEfficacious(subscip, (act - rhs)/norm) )
    491 {
    492 SCIPdebugMsg(scip, "Violated cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm);
    493 }
    494 else
    495 {
    496 SCIPdebugMsg(scip, "Rejected cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm);
    497 }
    498#endif
    499
    500 *violated = SCIPisEfficacious(subscip, (act - rhs)/norm);
    501
    502 return SCIP_OKAY;
    503}
    504
    505
    506/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
    507static
    508SCIP_DECL_CONSFREE(consFreeViolatedCuts)
    509{ /*lint --e{715}*/
    510 SCIP_CONSHDLRDATA* conshdlrdata;
    511
    512 assert( scip != NULL );
    513 assert( conshdlr != NULL );
    514 conshdlrdata = SCIPconshdlrGetData(conshdlr);
    515 assert( conshdlrdata != NULL );
    516
    517 SCIPfreeBlockMemory(scip, &conshdlrdata);
    518
    519 return SCIP_OKAY;
    520}
    521
    522
    523/** constraint enforcing method of constraint handler for LP solutions */
    524static
    525SCIP_DECL_CONSENFOLP(consEnfolpViolatedCuts)
    526{ /*lint --e{715}*/
    527 SCIP_CONSHDLRDATA* conshdlrdata;
    528 SCIP_Bool violated;
    529
    530 assert( scip != NULL );
    531 assert( conshdlr != NULL );
    532 assert( result != NULL );
    533
    534 assert( SCIPgetNLPBranchCands(scip) == 0 );
    535
    536 conshdlrdata = SCIPconshdlrGetData(conshdlr);
    537 assert( conshdlrdata != NULL );
    538
    539 SCIP_CALL( solCutIsViolated(scip, conshdlrdata->mipdata, NULL, &violated) );
    540
    541 if ( violated )
    542 *result = SCIP_FEASIBLE;
    543 else
    544 *result = SCIP_CUTOFF; /* cutoff, since all integer variables are integer, but the solution is not feasible */
    545
    546 return SCIP_OKAY;
    547}
    548
    549
    550/** constraint enforcing method of constraint handler for pseudo solutions */
    551static
    552SCIP_DECL_CONSENFOPS(consEnfopsViolatedCuts)
    553{ /*lint --e{715}*/
    554 assert( result != NULL );
    555
    556 /* this function should better not be called, since we need an LP solution for the sub-MIP to
    557 * make sense, because of the multiplier variables. We therefore return SCIP_FEASIBLE. */
    558 *result = SCIP_FEASIBLE;
    559
    560 return SCIP_OKAY;
    561}
    562
    563
    564/** feasibility check method of constraint handler for integral solutions */
    565static
    566SCIP_DECL_CONSCHECK(consCheckViolatedCuts)
    567{ /*lint --e{715}*/
    568 SCIP_CONSHDLRDATA* conshdlrdata;
    569 SCIP_Bool violated;
    570
    571 assert( scip != NULL );
    572 assert( conshdlr != NULL );
    573 assert( sol != NULL );
    574 assert( result != NULL );
    575
    576 conshdlrdata = SCIPconshdlrGetData(conshdlr);
    577 assert( conshdlrdata != NULL );
    578
    579 SCIP_CALL( solCutIsViolated(scip, conshdlrdata->mipdata, sol, &violated) );
    580
    581 if ( violated )
    582 *result = SCIP_FEASIBLE;
    583 else
    584 *result = SCIP_INFEASIBLE;
    585
    586 return SCIP_OKAY;
    587}
    588
    589
    590/** variable rounding lock method of constraint handler */
    591static
    592SCIP_DECL_CONSLOCK(consLockViolatedCuts)
    593{ /*lint --e{715}*/
    594 /* do not lock variables */
    595 return SCIP_OKAY;
    596}
    597
    598
    599/** creates the violated CG-cut constraint handler and includes it in SCIP */
    600static
    601SCIP_RETCODE SCIPincludeConshdlrViolatedCut(
    602 SCIP* scip, /**< SCIP data structure */
    603 CGMIP_MIPDATA* mipdata /**< data of separating sub-MIP */
    604 )
    605{
    606 SCIP_CONSHDLRDATA* conshdlrdata;
    607 SCIP_CONSHDLR* conshdlr;
    608
    609 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
    610 conshdlrdata->mipdata = mipdata;
    611
    612 /* include constraint handler */
    613 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
    614 -1000000, -1000000, 100, FALSE,
    615 consEnfolpViolatedCuts, consEnfopsViolatedCuts, consCheckViolatedCuts, consLockViolatedCuts,
    616 conshdlrdata) );
    617
    618 assert(conshdlr != NULL);
    619
    620 /* set non-fundamental callbacks via specific setter functions */
    621 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeViolatedCuts) );
    622
    623 return SCIP_OKAY;
    624}
    625
    626
    627/*
    628 * local methods
    629 */
    630
    631
    632/** stores nonzero elements of dense coefficient vector as sparse vector and calculates activity and norm
    633 *
    634 * copied from sepa_gomory.c
    635 */
    636static
    637SCIP_RETCODE storeCutInArrays(
    638 SCIP* scip, /**< SCIP data structure */
    639 int nvars, /**< number of problem variables */
    640 SCIP_Real* cutcoefs, /**< dense coefficient vector */
    641 SCIP_Real* varsolvals, /**< dense variable LP solution vector */
    642 char normtype, /**< type of norm to use for efficacy norm calculation */
    643 int* cutinds, /**< array to store variables of sparse cut vector */
    644 SCIP_Real* cutvals, /**< array to store coefficients of sparse cut vector */
    645 int* cutlen, /**< pointer to store number of nonzero entries in cut */
    646 SCIP_Real* cutact, /**< pointer to store activity of cut */
    647 SCIP_Real* cutnorm /**< pointer to store norm of cut vector */
    648 )
    649{
    650 SCIP_Real val;
    651 SCIP_Real cutsqrnorm;
    652 SCIP_Real act;
    653 SCIP_Real norm;
    654 int len;
    655 int v;
    656
    657 assert( nvars == 0 || cutcoefs != NULL );
    658 assert( nvars == 0 || varsolvals != NULL );
    659 assert( cutinds != NULL );
    660 assert( cutvals != NULL );
    661 assert( cutlen != NULL );
    662 assert( cutact != NULL );
    663 assert( cutnorm != NULL );
    664
    665 len = 0;
    666 act = 0.0;
    667 norm = 0.0;
    668 switch ( normtype )
    669 {
    670 case 'e':
    671 cutsqrnorm = 0.0;
    672 for (v = 0; v < nvars; ++v)
    673 {
    674 val = cutcoefs[v];
    675 if ( !SCIPisZero(scip, val) )
    676 {
    677 act += val * varsolvals[v];
    678 cutsqrnorm += SQR(val);
    679 cutinds[len] = v;
    680 cutvals[len++] = val;
    681 }
    682 }
    683 norm = sqrt(cutsqrnorm);
    684 break;
    685 case 'm':
    686 for (v = 0; v < nvars; ++v)
    687 {
    688 val = cutcoefs[v];
    689 if ( !SCIPisZero(scip, val) )
    690 {
    691 act += val * varsolvals[v];
    692 if ( REALABS(val) > norm )
    693 norm = REALABS(val);
    694 cutinds[len] = v;
    695 cutvals[len++] = val;
    696 }
    697 }
    698 break;
    699 case 's':
    700 for (v = 0; v < nvars; ++v)
    701 {
    702 val = cutcoefs[v];
    703 if ( !SCIPisZero(scip, val) )
    704 {
    705 act += val * varsolvals[v];
    706 norm += REALABS(val);
    707 cutinds[len] = v;
    708 cutvals[len++] = val;
    709 }
    710 }
    711 break;
    712 case 'd':
    713 for (v = 0; v < nvars; ++v)
    714 {
    715 val = cutcoefs[v];
    716 if ( !SCIPisZero(scip, val) )
    717 {
    718 act += val * varsolvals[v];
    719 cutinds[len] = v;
    720 cutvals[len++] = val;
    721 }
    722 }
    723 if ( len > 0 )
    724 norm = 1.0;
    725 break;
    726 default:
    727 SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", normtype);
    728 return SCIP_INVALIDDATA;
    729 }
    730
    731 *cutlen = len;
    732 *cutact = act;
    733 *cutnorm = norm;
    734
    735 return SCIP_OKAY;
    736}
    737
    738
    739/** Compute lhs/rhs for transformed column
    740 *
    741 * Consider a variable \f$x_j\f$ and some row of the original system:
    742 * \f[
    743 * \gamma \leq a^T x \leq \delta, \quad \ell_j \leq x_j \leq u_j.
    744 * \f]
    745 * We perform the transformation
    746 * \f[
    747 * x_i' = \left\{
    748 * \begin{array}{ll}
    749 * s + \frac{1}{\sigma}\, x_j & \mbox{if }i = j\\
    750 * x_i & \mbox{otherwise},
    751 * \end{array}
    752 * \right.
    753 * \f]
    754 * where \f$s\f$ is the offset value and \f$\sigma\f$ is a scaling factor. The new system is
    755 * \f[
    756 * \gamma + \sigma\, a_j\,s \leq \sum_{i \neq j} a_i\, x_i' + \sigma a_j\, x_j' \leq \delta + \sigma\, a_j\, s
    757 * \f]
    758 * with bounds
    759 * \f[
    760 * \frac{1}{\sigma} \ell_j + s \leq x_j' \leq \frac{1}{\sigma} u_j + s, \qquad \mbox{ if }\sigma > 0
    761 * \f]
    762 * and
    763 * \f[
    764 * \frac{1}{\sigma} u_j + s \leq x_j' \leq \frac{1}{\sigma} \ell_j + s, \qquad \mbox{ if }\sigma < 0.
    765 * \f]
    766 *
    767 * This can be used as follows:
    768 *
    769 * - If \f$x_j \geq \ell_j\f$ has a (nonzero) lower bound, one can use \f$s = -\ell_j\f$, \f$\sigma = 1\f$,
    770 * and obtain \f$\gamma - a_j\,\ell_j \leq a^T x' \leq \delta - a_j\,\ell_j\f$, \f$0 \leq x_j' \leq u_j - \ell_j\f$.
    771 *
    772 * - If \f$x_j \leq u_j\f$ has a (nonzero) upper bound, one can use \f$s = u_j\f$, \f$\sigma = -1\f$,
    773 * and obtain \f$\gamma - a_j\,u_j \leq \sum_{i \neq j} a_i\, x_i' - a_j\, x_j' \leq \delta - a_j\, u_j\f$,
    774 * \f$0 \leq x_j' \leq u_j - \ell_j\f$.
    775 */
    776static
    777SCIP_RETCODE transformColumn(
    778 SCIP* scip, /**< SCIP data structure */
    779 SCIP_SEPADATA* sepadata, /**< separator data */
    780 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
    781 SCIP_COL* col, /**< column that should be complemented */
    782 SCIP_Real offset, /**< offset by which column should be shifted */
    783 SCIP_Real sigma, /**< scaling factor */
    784 SCIP_Real* lhs, /**< array of lhs of rows */
    785 SCIP_Real* rhs, /**< array rhs of rows */
    786 SCIP_Real* lb, /**< pointer to lb of column */
    787 SCIP_Real* ub, /**< pointer to ub of column */
    788 SCIP_Real* primsol /**< pointer to solution value */
    789 )
    790{
    791 SCIP_ROW** colrows;
    792 SCIP_Real* colvals;
    793 int pos, i;
    794
    795 assert( scip != NULL );
    796 assert( lhs != NULL );
    797 assert( rhs != NULL );
    798 assert( col != NULL );
    799
    800 colrows = SCIPcolGetRows(col);
    801 colvals = SCIPcolGetVals(col);
    802 assert( SCIPcolGetNLPNonz(col) == 0 || colrows != NULL );
    803 assert( SCIPcolGetNLPNonz(col) == 0 || colvals != NULL );
    804 assert( ! SCIPisZero(scip, sigma) );
    805
    806 /* loop through rows that contain column */
    807 for (i = 0; i < SCIPcolGetNLPNonz(col); ++i)
    808 {
    809 SCIP_ROW* row;
    810
    811 row = colrows[i];
    812 assert( row != NULL );
    813
    814 /* skip modifiable rows and local rows, unless allowed */
    815 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
    816 continue;
    817
    818 pos = SCIProwGetLPPos(row);
    819 assert( 0 <= pos && pos < (int) mipdata->nrows );
    820
    821 assert( ! SCIPisInfinity(scip, lhs[pos]) );
    822 if ( ! SCIPisInfinity(scip, -lhs[pos]) )
    823 lhs[pos] += sigma * colvals[i] * offset;
    824
    825 assert( ! SCIPisInfinity(scip, -rhs[pos]) );
    826 if ( ! SCIPisInfinity(scip, rhs[pos]) )
    827 rhs[pos] += sigma * colvals[i] * offset;
    828 }
    829
    830 /* check objective function */
    831 if ( sepadata->useobjub || sepadata->useobjlb )
    832 {
    833 assert( SCIPisEQ(scip, SCIPcolGetObj(col), SCIPvarGetObj(SCIPcolGetVar(col))) );
    834 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
    835
    836 if ( ! SCIPisInfinity(scip, -lhs[mipdata->nrows]) )
    837 lhs[mipdata->nrows] += sigma * SCIPcolGetObj(col) * offset;
    838
    839 if ( ! SCIPisInfinity(scip, rhs[mipdata->nrows]) )
    840 rhs[mipdata->nrows] += sigma * SCIPcolGetObj(col) * offset;
    841 }
    842
    843 /* correct lower and upper bounds and solution */
    844 if ( SCIPisNegative(scip, sigma) )
    845 {
    846 SCIP_Real l;
    847
    848 assert( ! SCIPisInfinity(scip, -*ub) );
    849 if ( ! SCIPisInfinity(scip, *ub) )
    850 l = *ub/sigma + offset;
    851 else
    852 l = -SCIPinfinity(scip);
    853
    854 assert( ! SCIPisInfinity(scip, *lb) );
    855 if ( ! SCIPisInfinity(scip, -*lb) )
    856 *ub = *lb/sigma + offset;
    857 else
    858 *ub = SCIPinfinity(scip);
    859 *lb = l;
    860 }
    861 else
    862 {
    863 assert( ! SCIPisInfinity(scip, *lb) );
    864 if ( ! SCIPisInfinity(scip, -*lb) )
    865 *lb = *lb/sigma + offset;
    866 assert( ! SCIPisInfinity(scip, -*ub) );
    867 if ( ! SCIPisInfinity(scip, *ub) )
    868 *ub = *ub/sigma + offset;
    869 }
    870 *primsol = *primsol/sigma + offset;
    871
    872 return SCIP_OKAY;
    873}
    874
    875
    876/** compute objective coefficient for rows that are weighted by size
    877 *
    878 * The objective is computed by multiplying a default value by
    879 * \f[
    880 * 1 - (r_{\mbox{max}} - r) \frac{1 - a}{r_{\mbox{max}} - r_{\mbox{min}}},
    881 * \f]
    882 * where \f$r\f$ is the size of the current row, \f$a \in [0,1]\f$ is a parameter, and \f$r_{\mbox{max}}\f$ and
    883 * \f$r_{\mbox{min}}\f$ are the maximal and minimal size of a row, respectively.
    884 *
    885 * Thus, if \f$r = r_{\mbox{max}}\f$, we get 1 and if \f$r = r_{\mbox{min}}\f$, we get \f$a\f$.
    886 */
    887static
    888SCIP_Real computeObjWeightSize(
    889 int rowsize, /**< size of current row */
    890 int minrowsize, /**< maximal size of rows */
    891 int maxrowsize /**< minimal size of rows */
    892 )
    893{
    894 SCIP_Real a;
    895
    896 assert( maxrowsize > 0 );
    897 assert( minrowsize < INT_MAX );
    898 assert( minrowsize <= maxrowsize );
    899 assert( minrowsize <= rowsize && rowsize <= maxrowsize );
    900
    901 if ( minrowsize == maxrowsize )
    902 return 1.0;
    903
    904 a = (1.0 - OBJWEIGHTRANGE)/((SCIP_Real) (maxrowsize - minrowsize));
    905
    906 return 1.0 - a * ((SCIP_Real) (maxrowsize - rowsize));
    907}
    908
    909
    910/** Creates a subscip representing the separating MIP.
    911 *
    912 * Let the constraints of the original MIP be of the following form:
    913 * \f[
    914 * \begin{array}{l@{\;}ll}
    915 * a \leq A x + & C r & \leq b\\
    916 * \ell \leq x & & \leq u\\
    917 * c \leq & r & \leq d\\
    918 * x \in Z^n.
    919 * \end{array}
    920 * \f]
    921 * Here, some of the bounds may have value \f$\infty\f$ or \f$-\infty\f$. Written in
    922 * \f$\leq\f$-form this becomes:
    923 * \f[
    924 * \begin{array}{r@{\;}l}
    925 * \tilde{A} x + \tilde{C} r & \leq \tilde{b}\\
    926 * -x & \leq -\ell\\
    927 * x & \leq u\\
    928 * -r & \leq -c\\
    929 * r & \leq d\\
    930 * x \in Z^n,
    931 * \end{array}
    932 * \f]
    933 * where we use
    934 * \f[
    935 * \tilde{A} =
    936 * \left[
    937 * \begin{array}{r}
    938 * -A \\
    939 * A
    940 * \end{array}
    941 * \right],
    942 * \quad
    943 * \tilde{C} =
    944 * \left[
    945 * \begin{array}{r}
    946 * - C\\
    947 * C
    948 * \end{array}
    949 * \right]
    950 * \qquad\mbox{ and }\qquad
    951 * \tilde{b} =
    952 * \left[
    953 * \begin{array}{r}
    954 * -a\\
    955 * b
    956 * \end{array}
    957 * \right].
    958 * \f]
    959 * For the moment we assume that \f$c = 0\f$, i.e., the lower bounds on the continuous variables
    960 * are 0. To obtain a Chv&aacute;tal-Gomory cut we have to find nonnegative multipliers \f$y\f$,
    961 * \f$\underline{z}\f$, and \f$\overline{z}\f$ such that
    962 * \f[
    963 * y^T \tilde{A} - \underline{z}^T + \overline{z}^T \in Z \qquad\mbox{ and }\qquad
    964 * y^T \tilde{C} \geq 0.
    965 * \f]
    966 * Note that we use zero multipliers for the bounds on the continuous variables \f$r\f$. Moreover,
    967 * if some bounds are infinity, the corresponding multipliers are assumed to be 0. From these
    968 * conditions, we obtain
    969 * \f[
    970 * (y^T \tilde{A} - \underline{z}^T + \overline{z}^T)\, x +
    971 * y^T \tilde{C} \, r \leq
    972 * y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u.
    973 * \f]
    974 * Because \f$r \geq 0\f$, we can ignore the term \f$y^T \tilde{C} \, r \geq 0\f$ and obtain the
    975 * following cut:
    976 * \f[
    977 * (y^T \tilde{A} - \underline{z}^T + \overline{z}^T )\, x \leq
    978 * \lfloor y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u \rfloor.
    979 * \f]
    980 * Assume that \f$\ell = 0\f$ for the meantime. Then the cut can be written as:
    981 * \f[
    982 * \lfloor y^T \tilde{A} + \overline{z}^T \rfloor \, x \leq
    983 * \lfloor y^T \tilde{b} + \overline{z}^T u \rfloor.
    984 * \f]
    985 *
    986 * Following Fischetti and Lodi [2005], let \f$(x^*,r^*)\f$ be a fractional solution of the above
    987 * original system. The separating MIP created below is
    988 * \f[
    989 * \begin{array}{rlr@{\;}l}
    990 * \max & (x^*)^T \alpha - \beta - w^T y \\
    991 * & f = \tilde{A}^T y + \overline{z} - \alpha \\
    992 * & \tilde{f} = \tilde{b}^T y + u^T \overline{z} - \beta\\
    993 * & \tilde{C}^T y \geq 0\\
    994 * & 0 \leq f \leq 1 - \epsilon \\
    995 * & 0 \leq \tilde{f} \leq 1 - \epsilon\\
    996 * & 0 \leq y, \overline{z} \leq 1 - \epsilon.\\
    997 * & \alpha \in Z^m, \beta \in Z.
    998 * \end{array}
    999 * \f]
    1000 * Here, \f$w\f$ is a weight vector; it's idea is to make the sum over all components of \f$y\f$ as
    1001 * small as possible, in order to generate sparse cuts.
    1002 *
    1003 * We perform the following additional computations:
    1004 *
    1005 * - If the lower bounds on \f$x_i\f$ or \f$r_j\f$ are finite, we shift the variable to have a zero
    1006 * lower bound, i.e., we replace it by \f$x_i - \ell_i\f$ (or \f$r_j - u_j\f$). This is helpful in
    1007 * several ways: As seen above, the resulting inequalities/formulations simplify. Moreover, it
    1008 * allows to drop a variable if \f$x^*_i = 0\f$, see the next comment. If the lower bounds are not
    1009 * finite, but the upper bounds are finite, we can complement the variable. If the variables are
    1010 * free, the above formulation changes as follows: For free continuous variables, we require
    1011 * \f$\tilde{C}^T y = 0\f$. For a free integer variable \f$x_j\f$ (which rarely occurs in
    1012 * practice), we require \f$f_j = 0\f$, i.e., we force that \f$(\tilde{A}^T y + \overline{z})_j =
    1013 * \alpha_j\f$.
    1014 *
    1015 * - If \f$x^*_j = 0 = \ell_j\f$ (after the above preprocessing), we drop variable \f$\alpha_j\f$
    1016 * from the formulation. Let \f$(\alpha^*, \beta^*, y^*, \overline{z}^*)\f$ be an
    1017 * optimal solution to the separating MIP. Then we can compute \f$\alpha_j =
    1018 * \lfloor(\tilde{A}_j^T y^* + \overline{z}^*)\rfloor\f$.
    1019 *
    1020 * - If \f$x^*_i = u_i\f$, we complement the variable and drop it from the formulation, since the
    1021 * lower bound is 0 afterwards.
    1022 *
    1023 * - If a variable has been shifted or complemented, we have to recompute \f$\beta\f$ with the
    1024 * original lhs/rhs.
    1025 *
    1026 * - If a continuous variable \f$r_j\f$ is free, we have to force equality for the corresponding components in
    1027 * \f$y^T \tilde{C} \, r \geq 0\f$.
    1028 *
    1029 * - If an integer variable \f$x_i\f$ is free, we are not allowed to round the cut down. In this
    1030 * case, the combintation of rows and bounds has to be integral. We force this by requiring that
    1031 * \f$f_i = 0\f$.
    1032 *
    1033 * - If @p contconvert is true, some integral variables are randomly treated as if they were
    1034 * continuous. This has the effect that in the resulting cut the corresponding coefficient has
    1035 * value 0. This makes the cuts more sparse. Moreover, the separation problems should become
    1036 * easier.
    1037 *
    1038 * - If required, i.e., parameter @p primalseparation is true, we force a primal separation step. For
    1039 * this we require that the cut is tight at the currently best solution. To get reliable solutions
    1040 * we relax equality by EPSILONVALUE.
    1041 *
    1042 * - If required (via parameters @p useobjub or @p useobjlb), we add a row corresponding to the objective function with
    1043 * respect to the current lower and upper bounds.
    1044 */
    1045static
    1046SCIP_RETCODE createSubscip(
    1047 SCIP* origscip, /**< SCIP data structure */
    1048 SCIP_SEPA* sepa, /**< separator */
    1049 SCIP_SEPADATA* sepadata, /**< separator data */
    1050 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
    1051 )
    1052{
    1053 SCIP* subscip;
    1054 SCIP_COL** cols;
    1055 SCIP_ROW** rows;
    1056 SCIP_Real* lhs;
    1057 SCIP_Real* rhs;
    1058 SCIP_Real* lb;
    1059 SCIP_Real* ub;
    1060 SCIP_Real* primsol;
    1061 SCIP_Real multvarub;
    1062
    1063 unsigned int cnt;
    1064 unsigned int ucnt;
    1065 unsigned int nshifted;
    1066 unsigned int ncomplemented;
    1067#ifndef NDEBUG
    1068 unsigned int ncontconverted = 0;
    1069 unsigned int nintconverted = 0;
    1070#endif
    1071 unsigned int nlbounds;
    1072 unsigned int nubounds;
    1073
    1074 SCIP_VAR** consvars;
    1075 SCIP_Real* consvals;
    1076 SCIP_CONS* cons;
    1077 int nconsvars;
    1078 char name[SCIP_MAXSTRLEN];
    1079
    1080 int ncols;
    1081 int nrows;
    1082 int ntotalrows;
    1083 int maxrowsize = 0;
    1084 int minrowsize = INT_MAX;
    1085 int i, j;
    1086
    1087 assert( origscip != NULL );
    1088 assert( sepadata != NULL );
    1089
    1090 assert( mipdata->subscip == NULL );
    1091
    1092 SCIP_CALL( SCIPgetLPColsData(origscip, &cols, &ncols) );
    1093 SCIP_CALL( SCIPgetLPRowsData(origscip, &rows, &nrows) );
    1094 assert( ncols > 0 && nrows > 0 );
    1095
    1096 mipdata->m = 0;
    1097 mipdata->n = 0;
    1098 mipdata->nrows = (unsigned int) nrows;
    1099 mipdata->ncols = (unsigned int) ncols;
    1100 mipdata->ntotalrows = mipdata->nrows;
    1101
    1102 if ( sepadata->useobjub || sepadata->useobjlb )
    1103 mipdata->ntotalrows = mipdata->nrows + 1;
    1104
    1105 assert(mipdata->ntotalrows <= INT_MAX);
    1106 ntotalrows = (int) mipdata->ntotalrows;
    1107
    1108 /* copy value */
    1109 mipdata->conshdlrusenorm = sepadata->conshdlrusenorm;
    1110
    1111 /* create subscip */
    1112 SCIP_CALL( SCIPcreate( &(mipdata->subscip) ) );
    1113 subscip = mipdata->subscip;
    1114 SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
    1115
    1116 /* add violation constraint handler if requested */
    1117 if ( sepadata->addviolconshdlr )
    1118 {
    1119 SCIP_CALL( SCIPincludeConshdlrViolatedCut(subscip, mipdata) );
    1120 }
    1121
    1122 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sepa_cgmip separating MIP (%s)", SCIPgetProbName(origscip));
    1123 SCIP_CALL( SCIPcreateProb(subscip, name, NULL, NULL , NULL , NULL , NULL , NULL , NULL) );
    1124 SCIPsetSubscipDepth(subscip, SCIPgetSubscipDepth(origscip) + 1);
    1125 SCIP_CALL( SCIPsetObjsense(subscip, SCIP_OBJSENSE_MAXIMIZE) );
    1126
    1127 /* alloc memory for subscipdata elements */
    1128 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->alpha), ncols) );
    1129 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->fracalpha), ncols) );
    1130 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->coltype), ncols) );
    1131 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->iscomplemented), ncols) );
    1132 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->isshifted), ncols) );
    1133 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->ylhs), ntotalrows) );
    1134 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->yrhs), ntotalrows) );
    1135 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->z), 2*ncols) );
    1136 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->lhs), ntotalrows) );
    1137 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->rhs), ntotalrows) );
    1138 lhs = mipdata->lhs;
    1139 rhs = mipdata->rhs;
    1140
    1141 /* get temporary storage */
    1142 SCIP_CALL( SCIPallocBufferArray(origscip, &lb, ncols) );
    1143 SCIP_CALL( SCIPallocBufferArray(origscip, &ub, ncols) );
    1144 SCIP_CALL( SCIPallocBufferArray(origscip, &primsol, ncols) );
    1145
    1146 /* store lhs/rhs for complementing (see below) and compute maximal nonzeros of candidate rows */
    1147 for (i = 0; i < nrows; ++i)
    1148 {
    1149 SCIP_Real val;
    1150 SCIP_ROW* row;
    1151
    1152 row = rows[i];
    1153 assert( row != NULL );
    1154
    1155 val = SCIProwGetLhs(row) - SCIProwGetConstant(row);
    1156 if ( SCIProwIsIntegral(row) )
    1157 val = SCIPfeasCeil(origscip, val); /* row is integral: round left hand side up */
    1158 lhs[i] = val;
    1159
    1160 val = SCIProwGetRhs(row) - SCIProwGetConstant(row);
    1161 if ( SCIProwIsIntegral(row) )
    1162 val = SCIPfeasFloor(origscip, val); /* row is integral: round right hand side down */
    1163 rhs[i] = val;
    1164
    1165 /* skip modifiable rows and local rows, unless allowed */
    1166 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
    1167 continue;
    1168
    1169 /* skip rows that not have been active for a longer time */
    1170 if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage )
    1171 continue;
    1172
    1173 /* check whether we want to skip cuts produced by the CGMIP separator */
    1174 if ( sepadata->onlyrankone )
    1175 {
    1176 if ( SCIProwGetOriginSepa(row) == sepa )
    1177 continue;
    1178 }
    1179
    1180 /* determine maximal row size: */
    1181 val = SCIPgetRowLPActivity(origscip, row);
    1182 if ( ! SCIPisInfinity(origscip, REALABS(lhs[i])) )
    1183 {
    1184 if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetLhs(row)) )
    1185 {
    1186 if ( SCIProwGetNLPNonz(row) > maxrowsize )
    1187 maxrowsize = SCIProwGetNLPNonz(row);
    1188 if ( SCIProwGetNLPNonz(row) < minrowsize )
    1189 minrowsize = SCIProwGetNLPNonz(row);
    1190 }
    1191 }
    1192 else
    1193 {
    1194 if ( ! SCIPisInfinity(origscip, rhs[i]) )
    1195 {
    1196 if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetRhs(row)) )
    1197 {
    1198 if ( SCIProwGetNLPNonz(row) > maxrowsize )
    1199 maxrowsize = SCIProwGetNLPNonz(row);
    1200 if ( SCIProwGetNLPNonz(row) < minrowsize )
    1201 minrowsize = SCIProwGetNLPNonz(row);
    1202 }
    1203 }
    1204 }
    1205 }
    1206 assert( maxrowsize > 0 );
    1207 assert( minrowsize < INT_MAX );
    1208
    1209 /* add cuts for objective function if required */
    1210 if ( sepadata->useobjub )
    1211 {
    1212 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
    1213 rhs[mipdata->nrows] = SCIPgetUpperbound(origscip);
    1214 assert( ! SCIPisObjIntegral(origscip) || SCIPisFeasIntegral(origscip, SCIPgetUpperbound(origscip)) );
    1215
    1216 if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize )
    1217 maxrowsize = SCIPgetNObjVars(origscip);
    1218 if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize )
    1219 minrowsize = SCIPgetNObjVars(origscip);
    1220 }
    1221 if ( sepadata->useobjlb )
    1222 {
    1223 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
    1224
    1225 if ( SCIPisObjIntegral(origscip) )
    1226 lhs[mipdata->nrows] = SCIPfeasCeil(origscip, SCIPgetLowerbound(origscip));
    1227 else
    1228 lhs[mipdata->nrows] = SCIPgetLowerbound(origscip);
    1229
    1230 if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize )
    1231 maxrowsize = SCIPgetNObjVars(origscip);
    1232 if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize )
    1233 minrowsize = SCIPgetNObjVars(origscip);
    1234 }
    1235
    1236 /* store lb/ub for complementing and perform preprocessing */
    1237 nshifted = 0;
    1238 ncomplemented = 0;
    1239 nlbounds = 0;
    1240 nubounds = 0;
    1241 for (j = 0; j < ncols; ++j)
    1242 {
    1243 SCIP_COL* col;
    1244 SCIP_VAR* var;
    1245
    1246 col = cols[j];
    1247 assert( col != NULL );
    1248 var = SCIPcolGetVar(col);
    1249 assert( var != NULL );
    1250
    1251 primsol[j] = SCIPcolGetPrimsol(col);
    1252 assert( SCIPisEQ(origscip, SCIPgetVarSol(origscip, var), primsol[j]) );
    1253
    1254 lb[j] = SCIPvarGetLbGlobal(var);
    1255 assert( SCIPisEQ(origscip, SCIPvarGetLbLocal(var), SCIPcolGetLb(col)) );
    1256
    1257 /* if allowed, try to use stronger local bound */
    1258 if ( sepadata->allowlocal && SCIPisGT(origscip, SCIPvarGetLbLocal(var), lb[j]) )
    1259 lb[j] = SCIPvarGetLbLocal(var);
    1260
    1261 ub[j] = SCIPvarGetUbGlobal(var);
    1262 assert( SCIPisEQ(origscip, SCIPvarGetUbLocal(var), SCIPcolGetUb(col)) );
    1263
    1264 /* if allowed, try to use stronger local bound */
    1265 if ( sepadata->allowlocal && SCIPisLT(origscip, SCIPvarGetUbLocal(var), ub[j]) )
    1266 ub[j] = SCIPvarGetUbLocal(var);
    1267
    1268 mipdata->coltype[j] = colPresent;
    1269 mipdata->iscomplemented[j] = FALSE;
    1270 mipdata->isshifted[j] = FALSE;
    1271
    1272 /* check status of column/variable */
    1273 if ( SCIPcolIsIntegral(col) )
    1274 {
    1275 /* integral variables taking integral values are not interesting - will be substituted out below */
    1276 if ( ! SCIPisFeasIntegral(origscip, primsol[j]) )
    1277 {
    1278 /* possibly convert fractional integral variables to take integral values */
    1279 if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
    1280 {
    1281 /* randomly convert variables */
    1282 if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->intconvfrac )
    1283 {
    1284 assert( ! SCIPisInfinity(origscip, ub[j]) || ! SCIPisInfinity(origscip, -lb[j]) );
    1285
    1286 /* if both bounds are finite, take the closer one */
    1287 if ( ! SCIPisInfinity(origscip, ub[j]) && ! SCIPisInfinity(origscip, -lb[j]) )
    1288 {
    1289 assert( SCIPisFeasIntegral(origscip, ub[j]) );
    1290 assert( SCIPisFeasIntegral(origscip, lb[j]) );
    1291 assert( SCIPisFeasLT(origscip, primsol[j], ub[j]) );
    1292 assert( SCIPisFeasGT(origscip, primsol[j], lb[j]) );
    1293 if ( ub[j] - primsol[j] < primsol[j] - lb[j] )
    1294 primsol[j] = ub[j];
    1295 else
    1296 primsol[j] = lb[j];
    1297#ifndef NDEBUG
    1298 ++nintconverted;
    1299#endif
    1300 }
    1301 else
    1302 {
    1303 /* if only lower bound is finite */
    1304 if ( ! SCIPisInfinity(origscip, -lb[j]) )
    1305 {
    1306 assert( SCIPisFeasIntegral(origscip, lb[j]) );
    1307 primsol[j] = lb[j];
    1308#ifndef NDEBUG
    1309 ++nintconverted;
    1310#endif
    1311 }
    1312 else
    1313 {
    1314 assert( ! SCIPisInfinity(origscip, ub[j]) );
    1315 assert( SCIPisFeasIntegral(origscip, ub[j]) );
    1316 primsol[j] = ub[j];
    1317#ifndef NDEBUG
    1318 ++nintconverted;
    1319#endif
    1320 }
    1321 }
    1322 }
    1323 }
    1324 }
    1325
    1326 /* integral variables taking integral values are not interesting - will be substituted out below */
    1327 if ( ! SCIPisFeasIntegral(origscip, primsol[j]) )
    1328 {
    1329 /* possibly convert integral variables to be continuous */
    1330 if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
    1331 {
    1332 /* randomly convert variables */
    1333 if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->contconvfrac )
    1334 {
    1335 /* preprocessing is also performed for converted columns */
    1336 mipdata->coltype[j] = colConverted;
    1337#ifndef NDEBUG
    1338 ++ncontconverted;
    1339#endif
    1340 }
    1341 }
    1342 }
    1343 }
    1344 else
    1345 {
    1346 /* detect continuous variables, but perform preprocessing for them */
    1347 mipdata->coltype[j] = colContinuous;
    1348 }
    1349
    1350 /* if integer variable is at its upper bound -> complementing (this also generates a 0 lower bound) */
    1351 if ( mipdata->coltype[j] == colPresent && SCIPisFeasEQ(origscip, primsol[j], ub[j]) )
    1352 {
    1353 assert( ! SCIPisInfinity(origscip, ub[j]) );
    1354 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
    1355 mipdata->iscomplemented[j] = TRUE;
    1356 mipdata->coltype[j] = colAtUb;
    1357 ++nubounds;
    1358 }
    1359 else
    1360 {
    1361 /* if a variable has a finite nonzero lower bound -> shift */
    1362 if ( ! SCIPisInfinity(origscip, -lb[j]) )
    1363 {
    1364 if ( ! SCIPisZero(origscip, lb[j]) )
    1365 {
    1366 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, -lb[j], 1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
    1367 assert( SCIPisZero(origscip, lb[j]) );
    1368 mipdata->isshifted[j] = TRUE;
    1369 ++nshifted;
    1370 }
    1371
    1372 /* if integer variable is at its lower bound */
    1373 if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) )
    1374 {
    1375 mipdata->coltype[j] = colAtLb;
    1376 ++nlbounds;
    1377 }
    1378 }
    1379 else
    1380 {
    1381 /* lower bound is minus-infinity -> check whether upper bound is finite */
    1382 if ( ! SCIPisInfinity(origscip, ub[j]) )
    1383 {
    1384 /* complement variable */
    1385 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
    1386 assert( SCIPisZero(origscip, lb[j]) );
    1387 mipdata->iscomplemented[j] = TRUE;
    1388 ++ncomplemented;
    1389
    1390 /* if integer variable is at its lower bound */
    1391 if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) )
    1392 {
    1393 mipdata->coltype[j] = colAtLb;
    1394 ++nlbounds;
    1395 }
    1396 }
    1397 }
    1398 }
    1399
    1400 assert( SCIPisFeasLE(origscip, lb[j], primsol[j]) );
    1401 assert( SCIPisFeasLE(origscip, primsol[j], ub[j]) );
    1402 }
    1403
    1404#ifndef NDEBUG
    1405 if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
    1406 {
    1407 SCIPdebugMsg(origscip, "Converted %u fractional integral variables to have integral value.\n", nintconverted);
    1408 }
    1409 if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
    1410 {
    1411 SCIPdebugMsg(origscip, "Converted %u integral variables to be continuous.\n", ncontconverted);
    1412 }
    1413#endif
    1414 SCIPdebugMsg(origscip, "Original variables: %d integral, %d continuous, %u shifted, %u complemented, %u at lb, %u at ub\n",
    1415 SCIPgetNBinVars(origscip) + SCIPgetNIntVars(origscip) + SCIPgetNImplVars(origscip), SCIPgetNContVars(origscip),
    1416 nshifted, ncomplemented, nlbounds, nubounds);
    1417
    1418 /* prepare upper bound on y-variables */
    1419 if ( sepadata->skipmultbounds )
    1420 multvarub = SCIPinfinity(origscip);
    1421 else
    1422 multvarub = 1.0 - EPSILONVALUE;
    1423
    1424 /* create artificial variables for row combinations (y-variables) */
    1425 cnt = 0;
    1426 for (i = 0; i < nrows; ++i)
    1427 {
    1428 SCIP_ROW* row;
    1429
    1430 row = rows[i];
    1431 assert( row != NULL );
    1432
    1433 mipdata->ylhs[i] = NULL;
    1434 mipdata->yrhs[i] = NULL;
    1435
    1436 /* skip modifiable rows and local rows, unless allowed */
    1437 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
    1438 continue;
    1439
    1440 /* skip rows that not have been active for a longer time */
    1441 if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage )
    1442 continue;
    1443
    1444 /* check whether we want to skip cuts produced by the CGMIP separator */
    1445 if ( sepadata->onlyrankone )
    1446 {
    1447 if ( SCIProwGetOriginSepa(row) == sepa )
    1448 continue;
    1449 }
    1450
    1451 /* if we have an equation */
    1452 if ( SCIPisEQ(origscip, lhs[i], rhs[i]) )
    1453 {
    1454 SCIP_Real weight = -sepadata->objweight;
    1455
    1456 assert( ! SCIPisInfinity(origscip, rhs[i]) );
    1457 assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) ); /* equations should always be active */
    1458 assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) );
    1459
    1460 if ( sepadata->objweightsize )
    1461 weight = - sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
    1462
    1463 /* create two variables for each equation */
    1464 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq1_%d", i);
    1465 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub,
    1466 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1467 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) );
    1468 ++cnt;
    1469
    1470#ifdef SCIP_MORE_DEBUG
    1471 SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row));
    1472#endif
    1473
    1474 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq2_%d", i);
    1475 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub,
    1476 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1477 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) );
    1478 ++cnt;
    1479
    1480#ifdef SCIP_MORE_DEBUG
    1481 SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row));
    1482#endif
    1483 }
    1484 else
    1485 {
    1486 /* create variable for lhs of row if necessary */
    1487 if ( ! SCIPisInfinity(origscip, -lhs[i]) )
    1488 {
    1489 SCIP_Bool isactive = FALSE;
    1490 SCIP_Real weight = 0.0;
    1491
    1492 /* if the row is active, use objective weight equal to -sepadata->objweight */
    1493 if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) )
    1494 {
    1495 isactive = TRUE;
    1496 if ( sepadata->objweightsize )
    1497 weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
    1498 else
    1499 weight = -sepadata->objweight;
    1500 }
    1501
    1502 if ( ! sepadata->onlyactiverows || isactive )
    1503 {
    1504 /* add variable */
    1505 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ylhs_%d", i);
    1506 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub,
    1507 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1508 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) );
    1509 ++cnt;
    1510
    1511#ifdef SCIP_MORE_DEBUG
    1512 SCIPdebugMsg(origscip, "Created variable <%s> for >= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight);
    1513#endif
    1514 }
    1515 }
    1516
    1517 /* create variable for rhs of row if necessary */
    1518 if ( ! SCIPisInfinity(origscip, rhs[i]) )
    1519 {
    1520 SCIP_Bool isactive = FALSE;
    1521 SCIP_Real weight = 0.0;
    1522
    1523 /* if the row is active, use objective weight equal to -sepadata->objweight */
    1524 if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) )
    1525 {
    1526 isactive = TRUE;
    1527 if ( sepadata->objweightsize )
    1528 weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
    1529 else
    1530 weight = -sepadata->objweight;
    1531 }
    1532
    1533 if ( ! sepadata->onlyactiverows || isactive )
    1534 {
    1535 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yrhs_%d", i);
    1536 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub,
    1537 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1538 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) );
    1539 ++cnt;
    1540
    1541#ifdef SCIP_MORE_DEBUG
    1542 SCIPdebugMsg(origscip, "Created variable <%s> for <= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight);
    1543#endif
    1544 }
    1545 }
    1546 }
    1547 }
    1548 assert( (int) cnt <= 2 * nrows );
    1549 mipdata->n += cnt;
    1550
    1551 /* create artificial variables for objective function (if required) (y-variables) */
    1552 if ( sepadata->useobjub || sepadata->useobjlb )
    1553 {
    1554 SCIP_Real weight = 0.0;
    1555
    1556 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
    1557 mipdata->ylhs[mipdata->nrows] = NULL;
    1558 mipdata->yrhs[mipdata->nrows] = NULL;
    1559 cnt = 0;
    1560
    1561 if ( sepadata->objweightsize )
    1562 weight = -sepadata->objweight * computeObjWeightSize(SCIPgetNObjVars(origscip), minrowsize, maxrowsize);
    1563 else
    1564 weight = -sepadata->objweight;
    1565
    1566 /* create variable for upper objective bound if necessary */
    1567 if ( sepadata->useobjub && ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) )
    1568 {
    1569 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjub");
    1570 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[mipdata->nrows]), name, 0.0, multvarub,
    1571 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1572 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[mipdata->nrows]) );
    1573 ++cnt;
    1574
    1575#ifdef SCIP_MORE_DEBUG
    1576 SCIPdebugMsg(origscip, "Created variable <%s> for upper bound on objective (weight: %f).\n", name, weight);
    1577#endif
    1578 }
    1579
    1580 /* create variable for lower bound objective if necessary */
    1581 if ( sepadata->useobjlb && ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) )
    1582 {
    1583 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjlb");
    1584 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[mipdata->nrows]), name, 0.0, multvarub,
    1585 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1586 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[mipdata->nrows]) );
    1587 ++cnt;
    1588
    1589#ifdef SCIP_MORE_DEBUG
    1590 SCIPdebugMsg(origscip, "Created variable <%s> for lower bound on objective (weight: %f).\n", name, weight);
    1591#endif
    1592 }
    1593
    1594 assert( (int) cnt <= 2 * ntotalrows );
    1595 mipdata->n += cnt;
    1596 }
    1597
    1598 /* create alpha, bound, and fractional variables */
    1599 cnt = 0;
    1600 ucnt = 0;
    1601 for (j = 0; j < ncols; ++j)
    1602 {
    1603 mipdata->z[j] = NULL;
    1604 mipdata->alpha[j] = NULL;
    1605 mipdata->fracalpha[j] = NULL;
    1606
    1607 if ( mipdata->coltype[j] == colPresent )
    1608 {
    1609 SCIP_Real obj;
    1610
    1611 if ( sepadata->objlone )
    1612 obj = 0.0;
    1613 else
    1614 obj = primsol[j];
    1615
    1616 /* create alpha variables */
    1617 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j);
    1618 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->alpha[j]), name, -sepadata->cutcoefbnd, sepadata->cutcoefbnd, obj,
    1619 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1620 SCIP_CALL( SCIPaddVar(subscip, mipdata->alpha[j]) );
    1621 ++cnt;
    1622
    1623 /* create fractional variables */
    1624 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "f_%d", j);
    1625 if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) )
    1626 {
    1627 /* fix fractional value to be zero for free original variables */
    1628 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 0.0, 0.0,
    1629 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1630 }
    1631 else
    1632 {
    1633 /* fractional value in [0, 1) for variables with finite bounds */
    1634 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 1.0-EPSILONVALUE, 0.0,
    1635 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1636 }
    1637 SCIP_CALL( SCIPaddVar(subscip, mipdata->fracalpha[j]) );
    1638 ++cnt;
    1639
    1640 /* create variables for upper bounds */
    1641 if ( ! SCIPisInfinity(origscip, ub[j]) )
    1642 {
    1643 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "zub_%d", j);
    1644 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->z[j]), name, 0.0, multvarub,
    1645 0.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1646 SCIP_CALL( SCIPaddVar(subscip, mipdata->z[j]) );
    1647 ++ucnt;
    1648 }
    1649 }
    1650 }
    1651 assert( (int) cnt <= 2 * ncols );
    1652 assert( (int) ucnt <= ncols );
    1653
    1654 /* create variable for the rhs of the cut */
    1655 if ( sepadata->objlone )
    1656 {
    1657 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, 0.0,
    1658 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1659 }
    1660 else
    1661 {
    1662 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, -1.0,
    1663 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1664 }
    1665 SCIP_CALL( SCIPaddVar(subscip, mipdata->beta) );
    1666
    1667 /* create fractional variable for the rhs */
    1668 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracbeta), "fracbeta", 0.0, 1.0-BETAEPSILONVALUE, 0.0,
    1669 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
    1670 SCIP_CALL( SCIPaddVar(subscip, mipdata->fracbeta) );
    1671 mipdata->n += cnt + ucnt + 2;
    1672
    1673 /* get temporary storage */
    1674 SCIP_CALL( SCIPallocBufferArray(origscip, &consvals, (int) mipdata->n) );
    1675 SCIP_CALL( SCIPallocBufferArray(origscip, &consvars, (int) mipdata->n) );
    1676
    1677 /* create constraints for alpha variables of CG-cut */
    1678 cnt = 0;
    1679 for (j = 0; j < ncols; ++j)
    1680 {
    1681 SCIP_ROW** colrows;
    1682 SCIP_Real* colvals;
    1683
    1684 /* create ordinary part for all selected variables */
    1685 if ( mipdata->coltype[j] == colPresent )
    1686 {
    1687 SCIP_Real sigma;
    1688
    1689 assert( cols[j] != NULL );
    1690 colrows = SCIPcolGetRows(cols[j]);
    1691 colvals = SCIPcolGetVals(cols[j]);
    1692 nconsvars = 0;
    1693
    1694 if ( mipdata->iscomplemented[j] )
    1695 sigma = -1.0;
    1696 else
    1697 sigma = 1.0;
    1698
    1699 /* add part for columns */
    1700 for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i)
    1701 {
    1702 SCIP_ROW* row;
    1703 int pos;
    1704
    1705 row = colrows[i];
    1706 assert( row != NULL );
    1707
    1708 /* skip modifiable rows and local rows, unless allowed */
    1709 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
    1710 continue;
    1711
    1712 pos = SCIProwGetLPPos(row);
    1713 assert( 0 <= pos && pos < nrows );
    1714
    1715 if ( mipdata->ylhs[pos] != NULL )
    1716 {
    1717 consvars[nconsvars] = mipdata->ylhs[pos];
    1718 consvals[nconsvars] = -sigma * colvals[i];
    1719 ++nconsvars;
    1720 }
    1721 if ( mipdata->yrhs[pos] != NULL )
    1722 {
    1723 consvars[nconsvars] = mipdata->yrhs[pos];
    1724 consvals[nconsvars] = sigma * colvals[i];
    1725 ++nconsvars;
    1726 }
    1727 assert( nconsvars <= (int) mipdata->n );
    1728 }
    1729 /* add part for upper bounds */
    1730 if ( mipdata->z[j] != NULL )
    1731 {
    1732 assert( ! SCIPisInfinity(origscip, ub[j]) );
    1733 consvars[nconsvars] = mipdata->z[j];
    1734 consvals[nconsvars] = 1.0;
    1735 ++nconsvars;
    1736 }
    1737 assert( nconsvars <= (int) mipdata->n );
    1738
    1739 /* add alpha variable */
    1740 consvars[nconsvars] = mipdata->alpha[j];
    1741 consvals[nconsvars] = -1.0;
    1742 ++nconsvars;
    1743 assert( nconsvars <= (int) mipdata->n );
    1744
    1745 /* add fractional-alpha variable */
    1746 consvars[nconsvars] = mipdata->fracalpha[j];
    1747 consvals[nconsvars] = -1.0;
    1748 ++nconsvars;
    1749 assert( nconsvars <= (int) mipdata->n );
    1750
    1751 /* check for lower and upper objective bounds */
    1752 if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) )
    1753 {
    1754 /* add lower objective bound */
    1755 if ( mipdata->ylhs[mipdata->nrows] != NULL )
    1756 {
    1757 assert( sepadata->useobjlb );
    1758 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
    1759 consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]);
    1760 ++nconsvars;
    1761 }
    1762
    1763 /* add upper objective bound */
    1764 if ( mipdata->yrhs[mipdata->nrows] != NULL )
    1765 {
    1766 assert( sepadata->useobjub );
    1767 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
    1768 consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]);
    1769 ++nconsvars;
    1770 }
    1771 }
    1772
    1773 /* add linear constraint */
    1774 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j);
    1775 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, 0.0,
    1776 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
    1777 SCIP_CALL( SCIPaddCons(subscip, cons) );
    1778 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
    1779 ++cnt;
    1780 }
    1781 /* generate part that makes sure that cut is valid for continuous variables */
    1782 else if ( mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted )
    1783 {
    1784 SCIP_Real sigma;
    1785 SCIP_Real r;
    1786
    1787 assert( cols[j] != NULL );
    1788 colrows = SCIPcolGetRows(cols[j]);
    1789 colvals = SCIPcolGetVals(cols[j]);
    1790 nconsvars = 0;
    1791
    1792 if ( mipdata->iscomplemented[j] )
    1793 sigma = -1.0;
    1794 else
    1795 sigma = 1.0;
    1796
    1797 /* add part for columns */
    1798 for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i)
    1799 {
    1800 SCIP_ROW* row;
    1801 int pos;
    1802
    1803 row = colrows[i];
    1804 assert( row != NULL );
    1805
    1806 /* skip modifiable rows and local rows, unless allowed */
    1807 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
    1808 continue;
    1809
    1810 pos = SCIProwGetLPPos(row);
    1811 assert( 0 <= pos && pos < nrows );
    1812
    1813 if ( mipdata->ylhs[pos] != NULL )
    1814 {
    1815 consvars[nconsvars] = mipdata->ylhs[pos];
    1816 consvals[nconsvars] = -sigma * colvals[i];
    1817 ++nconsvars;
    1818 }
    1819 if ( mipdata->yrhs[pos] != NULL )
    1820 {
    1821 consvars[nconsvars] = mipdata->yrhs[pos];
    1822 consvals[nconsvars] = sigma * colvals[i];
    1823 ++nconsvars;
    1824 }
    1825 assert( nconsvars <= (int) mipdata->n );
    1826 }
    1827
    1828 /* check for lower and upper objective bounds */
    1829 if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) )
    1830 {
    1831 /* add lower objective bound */
    1832 if ( mipdata->ylhs[mipdata->nrows] )
    1833 {
    1834 assert( sepadata->useobjlb );
    1835 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
    1836 consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]);
    1837 ++nconsvars;
    1838 }
    1839
    1840 /* add upper objective bound */
    1841 if ( mipdata->yrhs[mipdata->nrows] )
    1842 {
    1843 assert( sepadata->useobjub );
    1844 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
    1845 consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]);
    1846 ++nconsvars;
    1847 }
    1848 }
    1849
    1850 /* add linear constraint */
    1851 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cont_%d", j);
    1852
    1853 /* for free continuous variables require equality */
    1854 r = SCIPinfinity(subscip);
    1855 if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) )
    1856 r = 0.0;
    1857 else
    1858 assert( SCIPisZero(origscip, lb[j]) );
    1859
    1860 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, r,
    1861 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
    1862 SCIP_CALL( SCIPaddCons(subscip, cons) );
    1863 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
    1864 ++cnt;
    1865 }
    1866 }
    1867 assert( (int) cnt <= ncols );
    1868 mipdata->m += cnt;
    1869
    1870 /* create constraints for rhs of cut */
    1871 nconsvars = 0;
    1872
    1873 /* first for the rows */
    1874 for (i = 0; i < nrows; ++i)
    1875 {
    1876 assert( rows[i] != NULL );
    1877
    1878 /* skip modifiable rows and local rows, unless allowed */
    1879 if ( SCIProwIsModifiable(rows[i]) || (SCIProwIsLocal(rows[i]) && !sepadata->allowlocal) )
    1880 continue;
    1881
    1882 /* if lhs is there */
    1883 if ( mipdata->ylhs[i] != NULL && ! SCIPisZero(origscip, lhs[i]) )
    1884 {
    1885 assert( ! SCIPisInfinity(origscip, -lhs[i]) );
    1886 consvars[nconsvars] = mipdata->ylhs[i];
    1887 consvals[nconsvars] = -lhs[i];
    1888 ++nconsvars;
    1889 }
    1890 /* if rhs is there */
    1891 if ( mipdata->yrhs[i] != NULL && ! SCIPisZero(origscip, rhs[i]) )
    1892 {
    1893 assert( ! SCIPisInfinity(origscip, rhs[i]) );
    1894 consvars[nconsvars] = mipdata->yrhs[i];
    1895 consvals[nconsvars] = rhs[i];
    1896 ++nconsvars;
    1897 }
    1898 assert( nconsvars <= (int) mipdata->n );
    1899 }
    1900
    1901 if ( sepadata->useobjub || sepadata->useobjlb )
    1902 {
    1903 /* add lower objective bound */
    1904 if ( mipdata->ylhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, lhs[mipdata->nrows]) )
    1905 {
    1906 assert( sepadata->useobjlb );
    1907 assert( ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) );
    1908 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
    1909 consvals[nconsvars] = -lhs[mipdata->nrows];
    1910 ++nconsvars;
    1911 }
    1912
    1913 /* add upper objective bound */
    1914 if ( mipdata->yrhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, rhs[mipdata->nrows]) )
    1915 {
    1916 assert( sepadata->useobjub );
    1917 assert( ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) );
    1918 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
    1919 consvals[nconsvars] = rhs[mipdata->nrows];
    1920 ++nconsvars;
    1921 }
    1922 assert( nconsvars <= (int) mipdata->n );
    1923 }
    1924
    1925 /* next for the columns */
    1926 for (j = 0; j < ncols; ++j)
    1927 {
    1928 /* if ub is there */
    1929 if ( mipdata->z[j] != NULL && ! SCIPisZero(origscip, ub[j]) )
    1930 {
    1931 assert( mipdata->coltype[j] == colPresent );
    1932 assert( ! SCIPisInfinity(origscip, ub[j]) );
    1933 consvars[nconsvars] = mipdata->z[j];
    1934 consvals[nconsvars] = ub[j];
    1935 ++nconsvars;
    1936 assert( nconsvars <= (int) mipdata->n );
    1937 }
    1938 }
    1939 /* add beta variable */
    1940 consvars[nconsvars] = mipdata->beta;
    1941 consvals[nconsvars] = -1.0;
    1942 ++nconsvars;
    1943
    1944 /* add fractional-beta variable */
    1945 consvars[nconsvars] = mipdata->fracbeta;
    1946 consvals[nconsvars] = -1.0;
    1947 ++nconsvars;
    1948 assert( nconsvars <= (int) mipdata->n );
    1949
    1950 /* add linear constraint */
    1951 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "beta", nconsvars, consvars, consvals, 0.0, 0.0,
    1952 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
    1953 SCIP_CALL( SCIPaddCons(subscip, cons) );
    1954 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
    1955 ++mipdata->m;
    1956
    1957 /* add primal separation constraint if required */
    1958 if ( sepadata->primalseparation )
    1959 {
    1960 SCIP_SOL* bestsol;
    1961 bestsol = SCIPgetBestSol(origscip);
    1962 if ( bestsol != NULL )
    1963 {
    1964 nconsvars = 0;
    1965 for (j = 0; j < ncols; ++j)
    1966 {
    1967 if ( mipdata->alpha[j] != NULL )
    1968 {
    1969 SCIP_Real val;
    1970 assert( mipdata->coltype[j] == colPresent );
    1971
    1972 val = SCIPgetSolVal(origscip, bestsol, SCIPcolGetVar(cols[j]));
    1973 consvars[nconsvars] = mipdata->alpha[j];
    1974 consvals[nconsvars] = val;
    1975 ++nconsvars;
    1976 assert( nconsvars <= (int) mipdata->n );
    1977 }
    1978 }
    1979 consvars[nconsvars] = mipdata->beta;
    1980 consvals[nconsvars] = -1.0;
    1981 ++nconsvars;
    1982
    1983 /* add linear constraint - allow slight deviation from equality */
    1984 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "primalseparation", nconsvars, consvars, consvals, -EPSILONVALUE, EPSILONVALUE,
    1985 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
    1986 SCIP_CALL( SCIPaddCons(subscip, cons) );
    1987 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
    1988 ++mipdata->m;
    1989 }
    1990 }
    1991
    1992 /* add constraint to force violated cuts if required */
    1993 if ( sepadata->addviolationcons )
    1994 {
    1995 nconsvars = 0;
    1996 for (j = 0; j < ncols; ++j)
    1997 {
    1998 if ( mipdata->alpha[j] != NULL )
    1999 {
    2000 consvars[nconsvars] = mipdata->alpha[j];
    2001 consvals[nconsvars] = primsol[j];
    2002 ++nconsvars;
    2003 assert( nconsvars <= (int) mipdata->n );
    2004 }
    2005 }
    2006 consvars[nconsvars] = mipdata->beta;
    2007 consvals[nconsvars] = -1.0;
    2008 ++nconsvars;
    2009
    2010 /* add linear constraint - allow slight deviation from equality */
    2011 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "violationConstraint", nconsvars, consvars, consvals, MINEFFICACY, SCIPinfinity(subscip),
    2012 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
    2013 SCIP_CALL( SCIPaddCons(subscip, cons) );
    2014 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
    2015 ++mipdata->m;
    2016 }
    2017
    2018 SCIPdebugMsg(origscip, "Subscip has %u vars (%d integral, %d continuous), %u conss.\n",
    2019 mipdata->n, SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip), mipdata->m);
    2020
    2021 /* free temporary memory */
    2022 SCIPfreeBufferArray(origscip, &consvars);
    2023 SCIPfreeBufferArray(origscip, &consvals);
    2024
    2025 SCIPfreeBufferArray(origscip, &primsol);
    2026 SCIPfreeBufferArray(origscip, &lb);
    2027 SCIPfreeBufferArray(origscip, &ub);
    2028
    2029 /* SCIPdebug( SCIP_CALL( SCIPprintOrigProblem(subscip, NULL, NULL, FALSE) ) ); */
    2030
    2031#ifdef SCIP_WRITEPROB
    2032 {
    2033 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.lp",
    2034 sepadata->objlone ? "_l1" : "",
    2035 sepadata->addviolationcons ? "_vc" : "",
    2036 sepadata->skipmultbounds ? "_ub" : "",
    2037 sepadata->primalseparation ? "_ps" : "",
    2038 SCIPgetProbName(origscip));
    2039 SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) );
    2040 SCIPinfoMessage(origscip, NULL, "Wrote subscip to file <%s>.\n", name);
    2041 }
    2042#endif
    2043
    2044 return SCIP_OKAY;
    2045}
    2046
    2047
    2048/** sets parameters for subscip */
    2049static
    2050SCIP_RETCODE subscipSetParams(
    2051 SCIP_SEPADATA* sepadata, /**< separator data */
    2052 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
    2053 )
    2054{
    2055 SCIP* subscip;
    2056
    2057 assert( sepadata != NULL );
    2058 assert( mipdata != NULL );
    2059
    2060 subscip = mipdata->subscip;
    2061 assert( subscip != NULL );
    2062
    2063 /* set objective limit, if no corresponding constraint has been added */
    2064 if ( ! sepadata->addviolationcons && ! sepadata->addviolconshdlr )
    2065 {
    2066 SCIP_CALL( SCIPsetObjlimit(subscip, MINEFFICACY) );
    2067 }
    2068
    2069 /* do not abort subscip on CTRL-C */
    2070 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
    2071
    2072 /* disable memory saving mode: this is likely to result in the maximal depth being reached. This is because DFS
    2073 * results in a repeated branching on the alpha-variables, which often have large bounds resulting in deep levels of
    2074 * the tree. */
    2075 SCIP_CALL( SCIPsetRealParam(subscip, "memory/savefac", 1.0) );
    2076
    2077 /* set number of solutions stored */
    2078 SCIP_CALL( SCIPsetIntParam(subscip, "limits/maxsol", MAXNSOLS) );
    2079
    2080 /* determine output to console */
    2081#ifdef SCIP_OUTPUT
    2082 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
    2083 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) );
    2084 SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) );
    2085#else
    2086 if ( sepadata->output )
    2087 {
    2088 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
    2089 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) );
    2090 SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) );
    2091 }
    2092 else
    2093 {
    2094 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
    2095 }
    2096#endif
    2097
    2098 if ( sepadata->subscipfast )
    2099 {
    2100 /* forbid recursive call of plugins solving subMIPs (also disables CG-separation) */
    2101#ifdef SCIP_OUTPUT
    2102 SCIP_CALL( SCIPsetSubscipsOff(subscip, FALSE) );
    2103#else
    2104 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); /* quiet */
    2105#endif
    2106 }
    2107 else
    2108 {
    2109 /* avoid recursive call */
    2110 if ( ! SCIPisParamFixed(subscip, "separating/cgmip/freq") )
    2111 {
    2112 SCIP_CALL( SCIPsetIntParam(subscip, "separating/cgmip/freq", -1) );
    2113 }
    2114 }
    2115
    2116#ifdef SCIP_DISABLED_CODE
    2117 /* the following possibly helps to improve performance (untested) */
    2118 SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
    2119#else
    2120
    2121 /* zirounding is often successful, so allow it some more calls */
    2122 if ( ! SCIPisParamFixed(subscip, "heuristics/zirounding/minstopncalls") )
    2123 {
    2124 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/zirounding/minstopncalls", 10000) );
    2125 }
    2126
    2127 if ( sepadata->subscipfast )
    2128 {
    2129 /* set other heuristics */
    2130 if ( ! SCIPisParamFixed(subscip, "heuristics/shifting/freq") )
    2131 {
    2132 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shifting/freq", 3) );
    2133 }
    2134 if ( ! SCIPisParamFixed(subscip, "heuristics/simplerounding/freq") )
    2135 {
    2136 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/simplerounding/freq", 1) );
    2137 }
    2138 if ( ! SCIPisParamFixed(subscip, "heuristics/rounding/freq") )
    2139 {
    2140 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rounding/freq", 1) );
    2141 }
    2142 if ( ! SCIPisParamFixed(subscip, "heuristics/oneopt/freq") )
    2143 {
    2144 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/oneopt/freq", 1) );
    2145 }
    2146
    2147 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/pscostdiving/freq", 1) ); */
    2148 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", 3) ); */
    2149
    2150 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/coefdiving/freq", -1) ); */
    2151 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) ); */
    2152 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/guideddiving/freq", -1) ); */
    2153 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/linesearchdiving/freq", -1) ); */
    2154 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/objpscostdiving/freq", -1) ); */
    2155 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rootsoldiving/freq", -1) ); */
    2156 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/veclendiving/freq", -1) ); */
    2157
    2158 /* use fast presolving */
    2159 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
    2160
    2161 /* disable conflict analysis */
    2162 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useprop", FALSE) ); */
    2163 /* SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useinflp", 'o') ); */
    2164 /* SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); */
    2165 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usesb", FALSE) ); */
    2166 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usepseudo", FALSE) ); */
    2167
    2168 /* use fast separation */
    2169 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
    2170 }
    2171#endif
    2172
    2173#ifdef SCIP_WRITEPROB
    2174 {
    2175 char name[SCIP_MAXSTRLEN];
    2176
    2177 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.set",
    2178 sepadata->objlone ? "_l1" : "",
    2179 sepadata->addviolationcons ? "_vc" : "",
    2180 sepadata->skipmultbounds ? "_ub" : "",
    2181 sepadata->primalseparation ? "_ps" : "",
    2182 SCIPgetProbName(mipdata->scip));
    2183 SCIP_CALL( SCIPwriteParams(subscip, name, TRUE, FALSE) );
    2184 SCIPinfoMessage(mipdata->scip, NULL, "Wrote settings to file <%s>.\n", name);
    2185 }
    2186#endif
    2187
    2188 return SCIP_OKAY;
    2189}
    2190
    2191
    2192/** try to convert fractional gomory cuts to primal solutions of CG-MIP */
    2193static
    2194SCIP_RETCODE createCGMIPprimalsols(
    2195 SCIP* scip, /**< original SCIP data structure */
    2196 SCIP_SEPADATA* sepadata, /**< separator data */
    2197 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
    2198 )
    2199{
    2200 SCIP_VAR** vars;
    2201 SCIP_ROW** rows;
    2202 SCIP_COL** cols;
    2203 SCIP_Real* binvrow;
    2204 SCIP_Real* cutcoefs;
    2205 int* basisind;
    2206 int nvars;
    2207 int nrows;
    2208 int ncols;
    2209 int ngen = 0;
    2210 int ntried = 0;
    2211 int i;
    2212
    2213 assert( scip != NULL );
    2214 assert( sepadata != NULL );
    2215 assert( mipdata != NULL );
    2216
    2217 /* get variables */
    2218 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
    2219
    2220 /* get rows and columns */
    2221 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
    2222 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    2223 assert( ncols <= nvars );
    2224
    2225 /* get storage */
    2226 SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
    2227 SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
    2228 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
    2229
    2230 /* get basis indices */
    2231 SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
    2232
    2233 /* loop through rows */
    2234 for (i = 0; i < nrows; ++i)
    2235 {
    2236 SCIP_Bool tryrow = FALSE;
    2237 SCIP_Real primsol = SCIP_INVALID;
    2238 int c;
    2239 int r;
    2240
    2241 c = basisind[i];
    2242 assert( c < ncols );
    2243
    2244 if ( c >= 0 )
    2245 {
    2246 SCIP_VAR* var;
    2247
    2248 var = SCIPcolGetVar(cols[c]);
    2249
    2250 if( SCIPvarIsIntegral(var) )
    2251 {
    2252 primsol = SCIPcolGetPrimsol(cols[c]);
    2253 assert( SCIPgetVarSol(scip, var) == primsol ); /*lint !e777*/
    2254
    2255 if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY )
    2256 tryrow = TRUE;
    2257 }
    2258 }
    2259#if ( SEPARATEROWS == TRUE )
    2260 else
    2261 {
    2262 SCIP_ROW* row;
    2263
    2264 assert(0 <= -c-1 && -c-1 < nrows);
    2265
    2266 row = rows[-c-1];
    2267
    2268 if ( SCIProwIsIntegral(row) && ! SCIProwIsModifiable(row) )
    2269 {
    2270 /* Compute value of the slack variable (we only care about the correct fractionality) */
    2271 if ( SCIPisInfinity(scip, SCIProwGetRhs(row)) )
    2272 primsol = SCIProwGetLhs(row) - SCIPgetRowLPActivity(scip, row);
    2273 else
    2274 primsol = SCIProwGetRhs(row) - SCIPgetRowLPActivity(scip, row);
    2275
    2276 if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY )
    2277 tryrow = TRUE;
    2278 }
    2279 }
    2280#endif
    2281
    2282 if ( tryrow )
    2283 {
    2284 SCIP_Bool success;
    2285 SCIP_SOL* sol;
    2286 SCIP_Real cutrhs = 0.0;
    2287 SCIP_ROW* row;
    2288 SCIP_Real val;
    2289 int j;
    2290
    2291 assert( primsol != SCIP_INVALID ); /*lint !e777*/
    2292
    2293 /* get the row of B^-1 for this basic integer variable with fractional solution value */
    2294 SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, NULL, NULL) );
    2295
    2296 /* clear cutcoefs */
    2297 BMSclearMemoryArray(cutcoefs, ncols);
    2298
    2299 /* create solution */
    2300 SCIP_CALL( SCIPcreateSol(mipdata->subscip, &sol, NULL) );
    2301
    2302 /* add values of multipliers to solution and compute coefficients */
    2303 for (r = 0; r < nrows; ++r)
    2304 {
    2305 SCIP_COL** rowcols;
    2306 SCIP_Real* rowvals;
    2307 SCIP_Real binvval;
    2308 SCIP_Real weight;
    2309
    2310 row = rows[r];
    2311 assert( row != NULL );
    2312
    2313 binvval = binvrow[r];
    2314 binvval = SCIPfrac(scip, binvval); /* can always take fractional value */
    2315 if ( ! SCIPisFeasZero(scip, binvval) )
    2316 {
    2317 SCIP_Real lhs;
    2318 SCIP_Real rhs;
    2319 SCIP_Bool uselhs;
    2320
    2321 lhs = SCIProwGetLhs(row);
    2322 rhs = SCIProwGetRhs(row);
    2323
    2324 if ( ! SCIPisEQ(scip, lhs, rhs) )
    2325 {
    2326 SCIP_BASESTAT stat;
    2327
    2328 stat = SCIProwGetBasisStatus(row);
    2329
    2330 if ( stat == SCIP_BASESTAT_LOWER )
    2331 {
    2332 assert( ! SCIPisInfinity(scip, -lhs) );
    2333 uselhs = TRUE;
    2334 }
    2335 else if ( stat == SCIP_BASESTAT_UPPER )
    2336 {
    2337 assert( ! SCIPisInfinity(scip, rhs) );
    2338 uselhs = FALSE;
    2339 }
    2340 else if ( SCIPisInfinity(scip, rhs) )
    2341 uselhs = TRUE;
    2342 else
    2343 uselhs = FALSE;
    2344 }
    2345 else if ( binvval < 0.0 )
    2346 uselhs = TRUE;
    2347 else
    2348 uselhs = FALSE;
    2349
    2350 if ( uselhs )
    2351 {
    2352 assert( mipdata->ylhs[r] != NULL );
    2353 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->ylhs[r], fabs(binvval)) );
    2354 weight = -fabs(binvval);
    2355 }
    2356 else
    2357 {
    2358 assert( mipdata->yrhs[r] != NULL );
    2359 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->yrhs[r], fabs(binvval)) );
    2360 weight = fabs(binvval);
    2361 }
    2362
    2363 /* update cut coefficients */
    2364 rowcols = SCIProwGetCols(row);
    2365 rowvals = SCIProwGetVals(row);
    2366
    2367 /* add the row coefficients to the sum */
    2368 for (j = 0; j < SCIProwGetNLPNonz(row); ++j)
    2369 {
    2370 int idx;
    2371
    2372 assert( rowcols[j] != NULL );
    2373
    2374 idx = SCIPcolGetLPPos(rowcols[j]);
    2375 assert( 0 <= idx && idx < ncols );
    2376
    2377 cutcoefs[idx] += weight * rowvals[j];
    2378 }
    2379
    2380 /* compute rhs */
    2381 if ( uselhs )
    2382 {
    2383 assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
    2384 val = mipdata->lhs[r];
    2385 }
    2386 else
    2387 {
    2388 assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
    2389 val = mipdata->rhs[r];
    2390 }
    2391 cutrhs += weight * val;
    2392 }
    2393 }
    2394
    2395 /* fill in values of cut */
    2396 for (c = 0; c < ncols; ++c)
    2397 {
    2398 if ( mipdata->coltype[c] != colPresent )
    2399 continue;
    2400
    2401 val = SCIPfloor(scip, cutcoefs[c]);
    2402 if ( mipdata->iscomplemented[c] )
    2403 val = -val;
    2404 if ( ! SCIPisFeasZero(scip, val) )
    2405 {
    2406 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->alpha[c], val) );
    2407 }
    2408 val = SCIPfeasFrac(scip, cutcoefs[c]);
    2409 if ( ! SCIPisFeasZero(scip, val) )
    2410 {
    2411 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracalpha[c], val) );
    2412 }
    2413 }
    2414
    2415 if ( ! SCIPisFeasZero(scip, SCIPfloor(scip, cutrhs)) )
    2416 {
    2417 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->beta, SCIPfloor(scip, cutrhs)) );
    2418 }
    2419 if ( ! SCIPisFeasZero(scip, SCIPfeasFrac(scip, cutrhs)) )
    2420 {
    2421 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracbeta, SCIPfeasFrac(scip, cutrhs)) );
    2422 }
    2423
    2424 SCIP_CALL( SCIPtrySolFree(mipdata->subscip, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
    2425 ++ntried;
    2426 if ( success )
    2427 ++ngen;
    2428 }
    2429 }
    2430
    2431 SCIPfreeBufferArray(scip, &cutcoefs);
    2432 SCIPfreeBufferArray(scip, &binvrow);
    2433 SCIPfreeBufferArray(scip, &basisind);
    2434
    2435 SCIPdebugMsg(scip, "Created %d primal solutions for CG-MIP from tableau cuts (tried: %d).\n", ngen, ntried);
    2436
    2437 return SCIP_OKAY;
    2438}
    2439
    2440
    2441/** solve subscip */
    2442static
    2443SCIP_RETCODE solveSubscip(
    2444 SCIP* origscip, /**< SCIP data structure */
    2445 SCIP_SEPADATA* sepadata, /**< separator data */
    2446 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
    2447 SCIP_Bool* success /**< if setting was successful -> stop */
    2448 )
    2449{
    2450 SCIP* subscip;
    2451 SCIP_RETCODE retcode;
    2452 SCIP_STATUS status;
    2453 SCIP_Real timelimit;
    2454 SCIP_Real memorylimit;
    2455 SCIP_Longint nodelimit;
    2456
    2457 assert( origscip != NULL );
    2458 assert( sepadata != NULL );
    2459 assert( mipdata != NULL );
    2460 assert( success != NULL );
    2461
    2462 *success = TRUE;
    2463
    2464 subscip = mipdata->subscip;
    2465
    2466 SCIP_CALL( SCIPcheckCopyLimits(origscip, success) );
    2467
    2468 if ( ! (*success) )
    2469 return SCIP_OKAY;
    2470
    2471 /* @todo Check whether copying the parameters is useful */
    2472 /* SCIP_CALL( SCIPcopyLimits(origscip, subscip) ); */
    2473
    2474 /* determine time limit */
    2475 SCIP_CALL( SCIPgetRealParam(origscip, "limits/time", &timelimit) );
    2476 if ( sepadata->timelimit < timelimit )
    2477 timelimit = sepadata->timelimit;
    2478
    2479 if ( ! SCIPisInfinity(origscip, timelimit) )
    2480 {
    2481 timelimit -= SCIPgetSolvingTime(origscip);
    2482 if ( timelimit > 0.0 )
    2483 {
    2484 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
    2485 }
    2486 else
    2487 {
    2488 SCIPdebugMsg(origscip, "Reached timelimit.\n");
    2489 *success = FALSE;
    2490 return SCIP_OKAY;
    2491 }
    2492 }
    2493
    2494 /* determine memory limit */
    2495 SCIP_CALL( SCIPgetRealParam(origscip, "limits/memory", &memorylimit) );
    2496 if ( sepadata->memorylimit < memorylimit )
    2497 memorylimit = sepadata->memorylimit;
    2498
    2499 if ( ! SCIPisInfinity(origscip, memorylimit) )
    2500 {
    2501 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
    2502 memorylimit -= SCIPgetMemUsed(origscip)/1048576.0;
    2503 memorylimit -= SCIPgetMemExternEstim(origscip)/1048576.0;
    2504 if ( memorylimit > 0.0 )
    2505 {
    2506 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
    2507 }
    2508 else
    2509 {
    2510 SCIPdebugMsg(origscip, "Reached memorylimit.\n");
    2511 *success = TRUE;
    2512 return SCIP_OKAY;
    2513 }
    2514 }
    2515
    2516 /* set node limit for subproblem */
    2517 if ( sepadata->minnodelimit < 0 || sepadata->maxnodelimit < 0 )
    2518 nodelimit = SCIP_LONGINT_MAX;
    2519 else
    2520 {
    2521 assert( sepadata->minnodelimit >= 0 && sepadata->maxnodelimit >= 0 );
    2522 nodelimit = SCIPgetNLPIterations(origscip);
    2523 nodelimit = MAX(sepadata->minnodelimit, nodelimit);
    2524 nodelimit = MIN(sepadata->maxnodelimit, nodelimit);
    2525 }
    2526 assert( nodelimit >= 0 );
    2527 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
    2528
    2529 /* try to create primal solutions of CG-MIP problem via tableau cuts */
    2530 if ( sepadata->genprimalsols )
    2531 {
    2532 SCIP_CALL( SCIPtransformProb(subscip) );
    2533 SCIP_CALL( createCGMIPprimalsols(origscip, sepadata, mipdata) );
    2534 }
    2535
    2536 SCIPdebugMsg(origscip, "Solving sub-SCIP (time limit: %f mem limit: %f node limit: %" SCIP_LONGINT_FORMAT ") ...\n", timelimit, memorylimit, nodelimit);
    2537
    2538 /* disable statistic timing inside sub SCIP */
    2539 if ( ! sepadata->output )
    2540 {
    2541 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
    2542 }
    2543
    2544 /* check whether we want a complete solve */
    2545 if ( ! sepadata->earlyterm )
    2546 {
    2547 retcode = SCIPsolve(subscip);
    2548 SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n",
    2549 SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit);
    2550
    2551 /* errors in solving the subproblem should not kill the overall solving process;
    2552 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
    2553 if ( retcode != SCIP_OKAY )
    2554 {
    2555#ifndef NDEBUG
    2556 SCIP_CALL( retcode );
    2557#endif
    2558 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
    2559 *success = FALSE;
    2560 return SCIP_OKAY;
    2561 }
    2562
    2563 status = SCIPgetStatus(subscip);
    2564
    2565#ifdef SCIP_OUTPUT
    2566 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
    2567#else
    2568 if ( sepadata->output )
    2569 {
    2570 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
    2571 }
    2572#endif
    2573
    2574 /* if the problem is infeasible (can happen because of violation constraint) */
    2575 if ( status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD )
    2576 {
    2577 SCIPdebugMsg(origscip, "CG-MIP separation problem infeasible.\n");
    2578 *success = FALSE;
    2579 return SCIP_OKAY;
    2580 }
    2581
    2582 /* if the solution ran into the time limit */
    2583 if ( status == SCIP_STATUS_TIMELIMIT )
    2584 {
    2585 SCIPdebugMsg(origscip, "CG-MIP separation problem ran into time limit.\n");
    2586 *success = FALSE;
    2587 return SCIP_OKAY;
    2588 }
    2589
    2590 /* if the solution process was terminated */
    2591 if ( status == SCIP_STATUS_USERINTERRUPT )
    2592 {
    2593 SCIPdebugMsg(origscip, "CG-MIP separation problem stopped by user interrupt.\n");
    2594 *success = FALSE;
    2595 return SCIP_OKAY;
    2596 }
    2597
    2598 /* all other statuses except optimal or node limit are invalid */
    2599 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_NODELIMIT )
    2600 {
    2601 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
    2602 return SCIP_ERROR;
    2603 }
    2604 }
    2605 else
    2606 {
    2607 /* otherwise we want a heuristic solve */
    2608
    2609 /* -> solve until first solution is found */
    2610 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 1) );
    2611 retcode = SCIPsolve(subscip);
    2612 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", -1) );
    2613
    2614 /* errors in solving the subproblem should not kill the overall solving process;
    2615 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
    2616 if ( retcode != SCIP_OKAY )
    2617 {
    2618#ifndef NDEBUG
    2619 SCIP_CALL( retcode );
    2620#endif
    2621 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
    2622 *success = FALSE;
    2623 return SCIP_OKAY;
    2624 }
    2625
    2626 status = SCIPgetStatus(subscip);
    2627
    2628 /* if the solution process was terminated or the problem is infeasible (can happen because of violation constraint) */
    2629 if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_NODELIMIT ||
    2630 status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD || status == SCIP_STATUS_MEMLIMIT )
    2631 {
    2632 /* output statistics before stopping */
    2633#ifdef SCIP_OUTPUT
    2634 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
    2635#else
    2636 if ( sepadata->output )
    2637 {
    2638 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
    2639 }
    2640#endif
    2641 *success = FALSE;
    2642 return SCIP_OKAY;
    2643 }
    2644
    2645 /* all other statuses except optimal or bestsollimit are invalid - (problem cannot be infeasible) */
    2646 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_BESTSOLLIMIT )
    2647 {
    2648 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
    2649 return SCIP_ERROR;
    2650 }
    2651
    2652 /* solve some more, if a feasible solution was found */
    2653 if ( status == SCIP_STATUS_BESTSOLLIMIT )
    2654 {
    2655 SCIPdebugMsg(origscip, "Continue solving separation problem (current time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ") ...\n",
    2656 SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip));
    2657
    2658 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", STALLNODELIMIT) );
    2659 retcode = SCIPsolve(subscip);
    2660 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", -1LL) );
    2661
    2662 SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n",
    2663 SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit);
    2664
    2665 /* errors in solving the subproblem should not kill the overall solving process;
    2666 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
    2667 if ( retcode != SCIP_OKAY )
    2668 {
    2669#ifndef NDEBUG
    2670 SCIP_CALL( retcode );
    2671#endif
    2672 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
    2673 *success = FALSE;
    2674 return SCIP_OKAY;
    2675 }
    2676
    2677 status = SCIPgetStatus(subscip);
    2678 assert( status != SCIP_STATUS_BESTSOLLIMIT );
    2679
    2680#ifdef SCIP_OUTPUT
    2681 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
    2682#else
    2683 if ( sepadata->output )
    2684 {
    2685 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
    2686 }
    2687#endif
    2688
    2689 /* if the solution process was terminated */
    2690 if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_MEMLIMIT )
    2691 {
    2692 *success = FALSE;
    2693 return SCIP_OKAY;
    2694 }
    2695
    2696 /* all other statuses except optimal or bestsollimit are invalid */
    2697 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_STALLNODELIMIT && status != SCIP_STATUS_NODELIMIT )
    2698 {
    2699 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
    2700 return SCIP_ERROR;
    2701 }
    2702 }
    2703 }
    2704
    2705 return SCIP_OKAY;
    2706}
    2707
    2708/** Computes cut from the given multipliers
    2709 *
    2710 * When computing the cut, we take the fractional part of the multipliers. This is known to produce stronger cuts in
    2711 * the pure integer case, since the cut is the sum of the one using fractional parts and integer multiples of the
    2712 * original constraints. However, if there are continuous variables, the resulting cut might not be valid. This is
    2713 * checked and returned.
    2714 *
    2715 * Moreover, the cut computed here in general will not be the same as the one computed with the
    2716 * sub-MIP, because of numerical differences. Here, we only combine rows whose corresponding
    2717 * multiplier is positive w.r.t. the feasibility tolerance. In the sub-MIP, however, the rows are
    2718 * combined in any case. This makes a difference, if the coefficients in the matrix are large and
    2719 * hence yield a value that is larger than the tolerance.
    2720 *
    2721 * Because of the transformations we have the following:
    2722 *
    2723 * If variable \f$x_j\f$ was complemented, we have \f$x'_j = u_j - x_j\f$. If in the transformed
    2724 * system the lower bound is used, its corresponding multiplier is \f$y^T A'_j - \lfloor y^T A'_j
    2725 * \rfloor\f$, which corresponds to
    2726 * \f[
    2727 * y^T A'_j - \lfloor y^T A'_j \rfloor = - y^T A_j - \lfloor - y^T A_j \rfloor = - y^T A_j + \lceil y^T A_j \rceil
    2728 * \f]
    2729 * in the original system.
    2730 *
    2731 * If such a variable was at its upper bound before the transformation, it is at its lower bound
    2732 * afterwards. Hence, its contribution to the cut is 0.
    2733 *
    2734 * Note that if the original LP-solution does not satisfy some of the rows with equality, the
    2735 * violation of the cut might be smaller than what is computed with the reduced sub-MIP.
    2736 *
    2737 * Furthermore, note that if continuous variables have been shifted, the computed violation may be
    2738 * different as well, because the necessary changes in the lhs/rhs are not used here anymore.
    2739 *
    2740 * @todo Check if cut is correct if continuous variables have been shifted.
    2741 */
    2742static
    2743SCIP_RETCODE computeCut(
    2744 SCIP* scip, /**< original scip */
    2745 SCIP_SEPA* sepa, /**< separator */
    2746 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
    2747 SCIP_SEPADATA* sepadata, /**< separator data */
    2748 SCIP_SOL* sol, /**< current solution for sub-MIP */
    2749 SCIP_Bool usefrac, /**< use fractional value of multipliers */
    2750 SCIP_Real* cutcoefs, /**< coefficients of the cut */
    2751 SCIP_Real* cutrhs, /**< rhs of the cut */
    2752 SCIP_Bool* localrowsused, /**< pointer to store whether local rows were used in summation */
    2753 SCIP_Bool* localboundsused, /**< pointer to store whether local bounds were used in summation */
    2754 int* cutrank, /**< pointer to store the cut rank */
    2755 SCIP_Bool* success /**< whether we produced a valid cut */
    2756 )
    2757{
    2758 SCIP* subscip;
    2759 SCIP_VAR** vars;
    2760 SCIP_ROW** rows;
    2761 SCIP_COL** cols;
    2762 SCIP_Real val;
    2763 SCIP_Real maxabsweight;
    2764 int nvars;
    2765 int ncols;
    2766 int nrows;
    2767 int i;
    2768 int j;
    2769
    2770 assert( scip != NULL );
    2771 assert( mipdata != NULL );
    2772 assert( sepadata != NULL );
    2773 assert( cutcoefs != NULL );
    2774 assert( cutrhs != NULL );
    2775 assert( localrowsused != NULL );
    2776 assert( localboundsused != NULL );
    2777 assert( cutrank != NULL );
    2778 assert( success != NULL );
    2779
    2780 /* initialize */
    2781 *localrowsused = FALSE;
    2782 *localboundsused = FALSE;
    2783 *cutrank = 0;
    2784 *success = TRUE;
    2785
    2786 subscip = mipdata->subscip;
    2787 assert( subscip != NULL );
    2788
    2789 /* get data */
    2790 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
    2791 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
    2792 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    2793 assert( nrows == (int) mipdata->nrows );
    2794 assert( ncols == (int) mipdata->ncols );
    2795
    2796 BMSclearMemoryArray(cutcoefs, nvars);
    2797 *cutrhs = 0.0;
    2798
    2799 /* find maximal absolute weight */
    2800 maxabsweight = 0.0;
    2801 for (i = 0; i < nrows; ++i)
    2802 {
    2803 SCIP_ROW* row;
    2804 SCIP_Real absweight = 0.0;
    2805
    2806 row = rows[i];
    2807 assert( row != NULL );
    2808
    2809 /* skip modifiable rows and local rows, unless allowed */
    2810 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
    2811 {
    2812 assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
    2813 continue;
    2814 }
    2815
    2816 /* get weight from solution (take larger of the values of lhs/rhs) */
    2817 if ( mipdata->ylhs[i] != NULL )
    2818 {
    2819 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]);
    2820
    2821 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    2822 if ( usefrac )
    2823 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    2824
    2825 if ( SCIPisFeasPositive(scip, val) )
    2826 absweight = val;
    2827
    2828 assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa );
    2829 }
    2830 if ( mipdata->yrhs[i] != NULL )
    2831 {
    2832 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]);
    2833
    2834 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    2835 if ( usefrac )
    2836 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    2837
    2838 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
    2839 if ( SCIPisFeasGT(scip, val, absweight) )
    2840 absweight = val;
    2841
    2842 assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa );
    2843 }
    2844 assert( ! SCIPisNegative(scip, absweight) );
    2845
    2846 if ( absweight > maxabsweight )
    2847 maxabsweight = absweight;
    2848 }
    2849
    2850 /* get weight from objective cuts */
    2851 if ( sepadata->useobjub || sepadata->useobjlb )
    2852 {
    2853 SCIP_Real absweight = 0.0;
    2854
    2855 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
    2856
    2857 if ( mipdata->ylhs[mipdata->nrows] != NULL )
    2858 {
    2859 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
    2860 if ( usefrac )
    2861 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    2862
    2863 if ( SCIPisFeasPositive(scip, val) )
    2864 absweight = val;
    2865 }
    2866 if ( mipdata->yrhs[mipdata->nrows] != NULL )
    2867 {
    2868 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
    2869 if ( usefrac )
    2870 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    2871
    2872 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
    2873 if ( SCIPisFeasGT(scip, val, absweight) )
    2874 absweight = val;
    2875 }
    2876
    2877 if ( absweight > maxabsweight )
    2878 maxabsweight = absweight;
    2879 }
    2880
    2881 /* calculate the row summation */
    2882 for (i = 0; i < nrows; ++i)
    2883 {
    2884 SCIP_ROW* row;
    2885 SCIP_Real weight;
    2886 SCIP_Real absweight;
    2887 SCIP_Bool uselhs;
    2888
    2889 row = rows[i];
    2890 assert( row != NULL );
    2891
    2892 /* skip modifiable rows and local rows, unless allowed */
    2893 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && ! sepadata->allowlocal) )
    2894 {
    2895 assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
    2896 continue;
    2897 }
    2898
    2899 /* get weight from solution */
    2900 weight = 0.0;
    2901 uselhs = FALSE;
    2902 if ( mipdata->ylhs[i] != NULL )
    2903 {
    2904 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]);
    2905 assert( ! SCIPisFeasNegative(subscip, val) );
    2906
    2907 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    2908 if ( usefrac )
    2909 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    2910
    2911 if ( SCIPisFeasPositive(scip, val) )
    2912 {
    2913 uselhs = TRUE;
    2914 weight = -val;
    2915 }
    2916 }
    2917 if ( mipdata->yrhs[i] != NULL )
    2918 {
    2919 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]);
    2920 assert( ! SCIPisFeasNegative(subscip, val) );
    2921
    2922 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    2923 if ( usefrac )
    2924 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    2925
    2926 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
    2927 if ( SCIPisFeasGT(scip, val, REALABS(weight)) )
    2928 {
    2929 uselhs = FALSE;
    2930 weight = val;
    2931 }
    2932 }
    2933
    2934 /* add row if weight is nonzero and lies within range */
    2935 absweight = REALABS(weight);
    2936 if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight )
    2937 {
    2938 SCIP_COL** rowcols;
    2939 SCIP_Real* rowvals;
    2940
    2941 rowcols = SCIProwGetCols(row);
    2942 rowvals = SCIProwGetVals(row);
    2943
    2944 /* add the row coefficients to the sum */
    2945 for (j = 0; j < SCIProwGetNLPNonz(row); ++j)
    2946 {
    2947 SCIP_VAR* var;
    2948 int idx;
    2949
    2950 assert( rowcols[j] != NULL );
    2951 var = SCIPcolGetVar(rowcols[j]);
    2952
    2953 assert( var != NULL );
    2954 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
    2955 assert( SCIPvarGetCol(var) == rowcols[j] );
    2956
    2957 idx = SCIPvarGetProbindex(var);
    2958 assert( 0 <= idx && idx < nvars );
    2959
    2960 cutcoefs[idx] += weight * rowvals[j];
    2961 }
    2962
    2963 /* compute rhs */
    2964 if ( uselhs )
    2965 {
    2966 assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
    2967 val = SCIProwGetLhs(row) - SCIProwGetConstant(row);
    2968 if ( SCIProwIsIntegral(row) )
    2969 val = SCIPfeasCeil(scip, val); /* row is integral: round left hand side up */
    2970 }
    2971 else
    2972 {
    2973 assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
    2974 val = SCIProwGetRhs(row) - SCIProwGetConstant(row);
    2975 if ( SCIProwIsIntegral(row) )
    2976 val = SCIPfeasFloor(scip, val); /* row is integral: round right hand side down */
    2977 }
    2978 *cutrhs += weight * val;
    2979
    2980 *localrowsused = *localrowsused || SCIProwIsLocal(row);
    2981
    2982 if ( SCIProwGetRank(row) > *cutrank )
    2983 *cutrank = SCIProwGetRank(row);
    2984 }
    2985 }
    2986 /* add 1 to cutrank */
    2987 ++(*cutrank);
    2988
    2989 /* get weight from objective bounds */
    2990 if ( sepadata->useobjub || sepadata->useobjlb )
    2991 {
    2992 SCIP_Real weight = 0.0;
    2993 SCIP_Bool uselhs = FALSE;
    2994 SCIP_Real absweight;
    2995
    2996 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
    2997
    2998 if ( mipdata->ylhs[mipdata->nrows] != NULL )
    2999 {
    3000 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
    3001 assert( ! SCIPisFeasNegative(subscip, val) );
    3002 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    3003 if ( usefrac )
    3004 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    3005
    3006 if ( SCIPisFeasPositive(scip, val) )
    3007 {
    3008 uselhs = TRUE;
    3009 weight = -val;
    3010 }
    3011 }
    3012 if ( mipdata->yrhs[mipdata->nrows] != NULL )
    3013 {
    3014 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
    3015 assert( ! SCIPisFeasNegative(subscip, val) );
    3016 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    3017 if ( usefrac )
    3018 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    3019
    3020 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
    3021 if ( SCIPisFeasGT(scip, val, REALABS(weight)) )
    3022 {
    3023 uselhs = FALSE;
    3024 weight = val;
    3025 }
    3026 }
    3027
    3028 /* add objective row if weight is nonzero and lies within range */
    3029 absweight = REALABS(weight);
    3030 if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight )
    3031 {
    3032 SCIP_Real obj;
    3033 int idx;
    3034
    3035 /* add the objective row coefficients to the sum */
    3036 for (j = 0; j < ncols; ++j)
    3037 {
    3038 assert( cols[j] != NULL );
    3039
    3040 obj = SCIPcolGetObj(cols[j]);
    3041 if ( ! SCIPisZero(scip, obj) )
    3042 {
    3043 idx = SCIPvarGetProbindex( SCIPcolGetVar(cols[j]) );
    3044 assert( 0 <= idx && idx < nvars );
    3045 cutcoefs[idx] += weight * obj;
    3046 }
    3047 }
    3048
    3049 /* compute rhs */
    3050 if ( uselhs )
    3051 {
    3052 val = SCIPgetLowerbound(scip);
    3053 assert( ! SCIPisInfinity(scip, -val) );
    3054 if ( SCIPisObjIntegral(scip) )
    3055 val = SCIPfeasCeil(scip, val); /* objective is integral: round left hand side up */
    3056 }
    3057 else
    3058 {
    3059 val = SCIPgetUpperbound(scip);
    3060 assert( ! SCIPisInfinity(scip, val) );
    3061 if ( SCIPisObjIntegral(scip) )
    3062 val = SCIPfeasFloor(scip, val); /* objective is integral: round right hand side down */
    3063 }
    3064 *cutrhs += weight * val;
    3065 }
    3066 }
    3067
    3068 /* add upper bounds */
    3069 for (j = 0; j < ncols; ++j)
    3070 {
    3071 assert( cols[j] != NULL );
    3072 if ( mipdata->z[j] != NULL )
    3073 {
    3074 assert( mipdata->coltype[j] == colPresent );
    3075
    3076 val = SCIPgetSolVal(subscip, sol, mipdata->z[j]);
    3077 assert( ! SCIPisFeasNegative(subscip, val) );
    3078
    3079 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    3080 if ( usefrac )
    3081 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    3082
    3083 /* if a bound has been used */
    3084 if ( SCIPisSumPositive(subscip, val) )
    3085 {
    3086 SCIP_VAR* var;
    3087 int idx;
    3088
    3089 var = SCIPcolGetVar(cols[j]);
    3090
    3091 assert( var != NULL );
    3092 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
    3093 assert( SCIPvarIsIntegral(var) );
    3094 assert( SCIPvarGetCol(var) == cols[j] );
    3095
    3096 idx = SCIPvarGetProbindex(var);
    3097 assert( 0 <= idx && idx < nvars );
    3098
    3099 /* check whether variable is complemented */
    3100 if ( mipdata->iscomplemented[j] )
    3101 {
    3102 SCIP_Real lbnd;
    3103 lbnd = SCIPvarGetLbGlobal(var);
    3104 assert( ! SCIPisInfinity(scip, -lbnd) );
    3105 assert( SCIPisIntegral(scip, lbnd) );
    3106 assert( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPcolGetLb(cols[j])) );
    3107
    3108 /* variable should not be free */
    3109 assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
    3110
    3111 /* if allowed, try to use stronger local bound */
    3112 if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd )
    3113 {
    3114 lbnd = SCIPvarGetLbLocal(var);
    3115 assert( SCIPisIntegral(scip, lbnd) );
    3116 *localboundsused = TRUE;
    3117 }
    3118
    3119 cutcoefs[idx] -= val;
    3120 *cutrhs -= lbnd * val;
    3121 }
    3122 else
    3123 {
    3124 SCIP_Real ubnd;
    3125 ubnd = SCIPvarGetUbGlobal(var);
    3126 assert( ! SCIPisInfinity(scip, ubnd) );
    3127 assert( SCIPisIntegral(scip, ubnd) );
    3128 assert( SCIPisEQ(scip, SCIPvarGetUbLocal(var), SCIPcolGetUb(cols[j])) );
    3129
    3130 /* if allowed, try to use stronger local bound */
    3131 if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd )
    3132 {
    3133 ubnd = SCIPvarGetUbLocal(var);
    3134 assert( SCIPisIntegral(scip, ubnd) );
    3135 *localboundsused = TRUE;
    3136 }
    3137
    3138 cutcoefs[idx] += val;
    3139 *cutrhs += ubnd * val;
    3140 }
    3141 }
    3142 }
    3143 }
    3144
    3145 /* check lower bounds for integral variables */
    3146 for (j = 0; j < nvars; ++j)
    3147 {
    3148 SCIP_VAR* var;
    3149 int pos;
    3150
    3151 var = vars[j];
    3152 assert( var != NULL );
    3153 pos = SCIPcolGetLPPos(SCIPvarGetCol(var));
    3154
    3155 /* a variable may have status COLUMN, but the corresponding column may not (yet) be in the LP */
    3156 if ( pos >= 0 && mipdata->coltype[pos] != colContinuous && mipdata->coltype[pos] != colConverted )
    3157 {
    3158 assert( pos < ncols );
    3159 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
    3160 assert( SCIPvarIsIntegral(var) );
    3161
    3162 /* check whether variable is complemented */
    3163 if ( mipdata->iscomplemented[pos] )
    3164 {
    3165 assert( ! mipdata->isshifted[pos] );
    3166 /* if the variable is complemented, the multiplier for the upper bound arises from the
    3167 lower bound multiplier for the transformed problem - because of the minus-sign in the
    3168 transformation this yields a round-up operation. */
    3169 val = SCIPfeasCeil(scip, cutcoefs[j]) - cutcoefs[j];
    3170 assert( ! SCIPisFeasNegative(scip, val) );
    3171
    3172 /* only if variable needs to be rounded */
    3173 if ( SCIPisSumPositive(scip, val) )
    3174 {
    3175 SCIP_Real ubnd;
    3176 ubnd = SCIPvarGetUbGlobal(var);
    3177 assert( ! SCIPisInfinity(scip, ubnd) );
    3178 assert( SCIPisIntegral(scip, ubnd) );
    3179
    3180 /* variable should not be free */
    3181 assert( ! SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || ! SCIPisInfinity(scip, ubnd) );
    3182
    3183 /* if allowed, try to use stronger local bound */
    3184 if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd )
    3185 {
    3186 ubnd = SCIPvarGetUbLocal(var);
    3187 assert( SCIPisIntegral(scip, ubnd) );
    3188 *localboundsused = TRUE;
    3189 }
    3190
    3191 /* round cut coefficients, i.e., add val to cutcoefs[j] */
    3192 cutcoefs[j] = SCIPfeasCeil(scip, cutcoefs[j]);
    3193
    3194 /* correct rhs */
    3195 if ( ! SCIPisSumZero(scip, ubnd) )
    3196 *cutrhs += ubnd * val;
    3197 }
    3198 }
    3199 else
    3200 {
    3201 /* compute multiplier for lower bound: */
    3202 val = cutcoefs[j] - SCIPfeasFloor(scip, cutcoefs[j]);
    3203 assert( ! SCIPisFeasNegative(scip, val) );
    3204
    3205 /* only if variable needs to be rounded */
    3206 if ( SCIPisSumPositive(scip, val) )
    3207 {
    3208 SCIP_Real lbnd;
    3209 lbnd = SCIPvarGetLbGlobal(var);
    3210 assert( ! SCIPisInfinity(scip, -lbnd) );
    3211 assert( SCIPisIntegral(scip, lbnd) );
    3212
    3213 /* variable should not be free */
    3214 assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
    3215
    3216 /* if allowed, try to use stronger local bound */
    3217 if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd )
    3218 {
    3219 lbnd = SCIPvarGetLbLocal(var);
    3220 assert( SCIPisIntegral(scip, lbnd) );
    3221 *localboundsused = TRUE;
    3222 }
    3223
    3224 /* round cut coefficients, i.e., subtract val from cutcoefs[j] */
    3225 cutcoefs[j] = SCIPfeasFloor(scip, cutcoefs[j]);
    3226
    3227 /* correct rhs */
    3228 if ( ! SCIPisSumZero(scip, lbnd) )
    3229 *cutrhs -= lbnd * val;
    3230 }
    3231 }
    3232 }
    3233 else
    3234 {
    3235 /* force coefficients of all continuous variables or of variables not in the lp to zero */
    3236 assert( pos == -1 || mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted );
    3237
    3238 /* check whether all coefficients for continuous or converted variables are nonnegative */
    3239 if ( pos >= 0 )
    3240 {
    3241 if ( SCIPisFeasNegative(scip, cutcoefs[j]) )
    3242 {
    3243 *success = FALSE;
    3244 break;
    3245 }
    3246 }
    3247
    3248 cutcoefs[j] = 0.0;
    3249 }
    3250 }
    3251
    3252 /* round rhs */
    3253 *cutrhs = SCIPfeasFloor(scip, *cutrhs);
    3254
    3255 return SCIP_OKAY;
    3256}
    3257
    3258/** Create CG-cut directly from solution of sub-MIP */
    3259static
    3260SCIP_RETCODE createCGCutDirect(
    3261 SCIP* scip, /**< SCIP data structure */
    3262 SCIP_SEPA* sepa, /**< separator */
    3263 SCIP_SEPADATA* sepadata, /**< separator data */
    3264 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
    3265 SCIP_SOL* sol, /**< solution of sub-MIP */
    3266 SCIP_Real* cutcoefs, /**< cut coefficients */
    3267 int* cutinds, /**< problem indices of variables appearing in cut */
    3268 SCIP_Real* cutvals, /**< values of variables in cut */
    3269 SCIP_Real* varsolvals, /**< solution value of variables */
    3270 SCIP_Real* weights, /**< weights to compute cmir cut */
    3271 int* nprevrows, /**< number of previously generated rows */
    3272 SCIP_ROW** prevrows, /**< previously generated rows */
    3273 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
    3274 unsigned int* ngen /**< number of generated cuts */
    3275 )
    3276{
    3277 char name[SCIP_MAXSTRLEN];
    3278 SCIP_Bool cutislocal;
    3279 SCIP_Bool localrowsused;
    3280 SCIP_Bool localboundsused;
    3281 SCIP_Real cutrhs;
    3282 SCIP_Real cutact;
    3283 SCIP_Bool success;
    3284 SCIP_VAR** vars;
    3285 int cutrank = 0;
    3286 int nvars;
    3287 int k;
    3288
    3289 assert( scip != NULL );
    3290 assert( sepadata != NULL );
    3291 assert( mipdata != NULL );
    3292 assert( sol != NULL );
    3293 assert( cutcoefs != NULL );
    3294 assert( cutinds != NULL );
    3295 assert( cutvals != NULL );
    3296 assert( varsolvals != NULL );
    3297 assert( weights != NULL );
    3298 assert( nprevrows != NULL );
    3299 assert( prevrows != NULL );
    3300 assert( cutoff != NULL );
    3301 assert( ngen != NULL );
    3302
    3303 /* get variable data */
    3304 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
    3305
    3306 cutrhs = 0.0;
    3307 localrowsused = FALSE;
    3308 localboundsused = FALSE;
    3309 *cutoff = FALSE;
    3310 success = TRUE;
    3311
    3312 /* compute coefficients */
    3313 SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, TRUE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
    3314 cutislocal = localrowsused || localboundsused;
    3315
    3316 /* Take next solution if cut was not valid - this can easily happen for mixed-integer problems, see function computeCut(). */
    3317 if ( ! success )
    3318 {
    3319 /* try again without using fractional value */
    3320 SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, FALSE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
    3321 cutislocal = localrowsused || localboundsused;
    3322
    3323 if ( ! success )
    3324 {
    3325 SCIPdebugMsg(scip, "cut not valid - skipping ...\n");
    3326 return SCIP_OKAY;
    3327 }
    3328 }
    3329
    3330 /* compute activity */
    3331 cutact = 0.0;
    3332 for (k = 0; k < nvars; ++k)
    3333 cutact += cutcoefs[k] * varsolvals[k];
    3334
    3335#ifdef SCIP_DISABLED_CODE
    3336 /* the following test should be treated with care because of numerical differences - see computeCut() */
    3337 {
    3338 /* check for correctness of computed values */
    3339 SCIP* subscip;
    3340 SCIP_Real obj = 0.0;
    3341 SCIP_Real val;
    3342 SCIP_Bool contVarShifted = FALSE;
    3343 unsigned int j;
    3344 SCIP_COL** cols;
    3345 int ncols;
    3346
    3347 subscip = mipdata->subscip;
    3348 assert( subscip != NULL );
    3349
    3350 SCIP_CALL( SCIPprintSol(subscip, sol, NULL, FALSE) );
    3351
    3352 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    3353 for (j = 0; j < mipdata->ncols; ++j)
    3354 {
    3355 if ( mipdata->coltype[j] == colPresent )
    3356 {
    3357 int idx;
    3358 assert( mipdata->alpha[j] != NULL );
    3359 val = SCIPgetSolVal(subscip, sol, mipdata->alpha[j]);
    3360 assert( SCIPisFeasIntegral(subscip, val) );
    3361 idx = SCIPvarGetProbindex(SCIPcolGetVar(cols[j]));
    3362 assert( SCIPisFeasEQ(scip, val, cutcoefs[idx]) );
    3363 obj += val * SCIPvarGetObj(mipdata->alpha[j]);
    3364 }
    3365 else
    3366 {
    3367 if ( (mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted) && mipdata->isshifted[j] )
    3368 contVarShifted = TRUE;
    3369 }
    3370 }
    3371 assert( mipdata->beta != NULL );
    3372 val = SCIPgetSolVal(subscip, sol, mipdata->beta);
    3373 assert( SCIPisFeasIntegral(subscip, val) );
    3374 obj += val * SCIPvarGetObj(mipdata->beta);
    3375 assert( contVarShifted || SCIPisFeasEQ(scip, obj, cutact - cutrhs) );
    3376 }
    3377#endif
    3378
    3379 /* if successful, convert dense cut into sparse row, and add the row as a cut */
    3380 if ( SCIPisFeasGT(scip, cutact, cutrhs) )
    3381 {
    3382 SCIP_Real cutnorm;
    3383 int cutlen;
    3384
    3385 /* store the cut as sparse row, calculate activity and norm of cut */
    3386 SCIP_CALL( storeCutInArrays(scip, nvars, cutcoefs, varsolvals, mipdata->normtype,
    3387 cutinds, cutvals, &cutlen, &cutact, &cutnorm) );
    3388
    3389 SCIPdebugMsg(scip, "act=%f, rhs=%f, norm=%f, eff=%f\n", cutact, cutrhs, cutnorm, (cutact - cutrhs)/cutnorm);
    3390
    3391 /* if norm is 0, the cut is trivial */
    3392 if ( SCIPisPositive(scip, cutnorm) )
    3393 {
    3394 SCIP_Bool violated = SCIPisEfficacious(scip, (cutact - cutrhs)/cutnorm);
    3395
    3396 if ( violated || (sepadata->usecutpool && ! cutislocal ) )
    3397 {
    3398 SCIP_ROW* cut;
    3399
    3400 /* create the cut */
    3401 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
    3402 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
    3403 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
    3404
    3405 for (k = 0; k < cutlen; ++k)
    3406 {
    3407 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutvals[k]) );
    3408 }
    3409
    3410 /* set cut rank */
    3411 SCIProwChgRank(cut, cutrank);
    3412
    3413 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
    3414
    3415 /*SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) );*/
    3416
    3417 /* add cut to pool */
    3418 if ( ! cutislocal )
    3419 {
    3420 assert( violated || sepadata->usecutpool );
    3421 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
    3422 }
    3423
    3424 /* add cut if it is violated */
    3425 if ( violated )
    3426 {
    3427 /* check whether cut has been found before - may happened due to projection */
    3428 for (k = 0; k < *nprevrows; ++k)
    3429 {
    3430 SCIP_Real parval;
    3431
    3432 assert( prevrows[k] != NULL );
    3433 parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
    3434 /* exit if row is parallel to existing cut and rhs is not better */
    3435 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
    3436 break;
    3437 }
    3438
    3439 /* if cut is new */
    3440 if ( k >= *nprevrows )
    3441 {
    3442 prevrows[*nprevrows] = cut;
    3443 ++(*nprevrows);
    3444
    3445 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
    3446 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
    3447 SCIPgetCutEfficacy(scip, NULL, cut),
    3448 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
    3449 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
    3450#ifdef SCIP_DEBUG
    3451 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3452#else
    3453 if ( sepadata->output )
    3454 {
    3455 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3456 }
    3457#endif
    3458 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
    3459 ++(*ngen);
    3460 }
    3461 else
    3462 {
    3463 SCIPdebugMsg(scip, "Cut already exists.\n");
    3464 /* release the row */
    3465 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
    3466 }
    3467 }
    3468 else
    3469 {
    3470 /* release the row */
    3471 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
    3472 }
    3473 }
    3474 }
    3475 }
    3476
    3477 return SCIP_OKAY;
    3478}
    3479
    3480
    3481/** create CG-cut via CMIR-function */
    3482static
    3483SCIP_RETCODE createCGCutCMIR(
    3484 SCIP* scip, /**< SCIP data structure */
    3485 SCIP_SEPA* sepa, /**< separator */
    3486 SCIP_SEPADATA* sepadata, /**< separator data */
    3487 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
    3488 SCIP_SOL* sol, /**< solution of sub-MIP */
    3489 SCIP_AGGRROW* aggrrow, /**< aggregation row to use for creating MIR cut */
    3490 SCIP_Real* cutcoefs, /**< cut coefficients */
    3491 int* cutinds, /**< problem indices of variables appearing in cut */
    3492 SCIP_Real* cutvals, /**< values of variables in cut */
    3493 SCIP_Real* varsolvals, /**< solution value of variables */
    3494 SCIP_Real* weights, /**< weights to compute cmir cut */
    3495 int* boundsfortrans, /**< bounds for cmir function of NULL */
    3496 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds for cmir function or NULL */
    3497 int* nprevrows, /**< number of previously generated rows */
    3498 SCIP_ROW** prevrows, /**< previously generated rows */
    3499 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
    3500 unsigned int* ngen /**< number of generated cuts */
    3501 )
    3502{
    3503 char name[SCIP_MAXSTRLEN];
    3504 SCIP_Longint maxdnom;
    3505 SCIP_Bool cutislocal;
    3506 SCIP_Real maxscale;
    3507 SCIP_Real cutrhs;
    3508 SCIP_Real cutefficacy;
    3509 SCIP_Bool success;
    3510 SCIP_ROW** rows;
    3511 SCIP_VAR** vars;
    3512 SCIP* subscip;
    3513 int nrows;
    3514 int nvars;
    3515 int k;
    3516 int cutrank;
    3517 int cutnnz;
    3518
    3519 assert( scip != NULL );
    3520 assert( sepadata != NULL );
    3521 assert( mipdata != NULL );
    3522 assert( sol != NULL );
    3523 assert( cutcoefs != NULL );
    3524 assert( cutinds != NULL );
    3525 assert( cutvals != NULL );
    3526 assert( varsolvals != NULL );
    3527 assert( weights != NULL );
    3528 assert( nprevrows != NULL );
    3529 assert( prevrows != NULL );
    3530 assert( cutoff != NULL );
    3531 assert( ngen != NULL );
    3532
    3533 *cutoff = FALSE;
    3534 subscip = mipdata->subscip;
    3535 assert( subscip != NULL );
    3536
    3537 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
    3538 assert( nrows > 0 );
    3539 assert( (int) mipdata->nrows == nrows );
    3540
    3541 /* @todo more advanced settings - compare sepa_gomory.c */
    3542 maxdnom = (SCIP_Longint) sepadata->cutcoefbnd+1;
    3543 maxscale = 10000.0;
    3544
    3545 /* get variable data */
    3546 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
    3547
    3548 /* generate weights */
    3549 for (k = 0; k < nrows; ++k)
    3550 {
    3551 SCIP_Real val;
    3552
    3553 weights[k] = 0;
    3554 if ( mipdata->ylhs[k] != NULL )
    3555 {
    3556 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
    3557
    3558 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]);
    3559 assert( ! SCIPisFeasNegative(subscip, val) );
    3560
    3561 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    3562 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    3563
    3564 if ( SCIPisFeasPositive(subscip, val) )
    3565 weights[k] = -val;
    3566 }
    3567
    3568 if ( mipdata->yrhs[k] != NULL )
    3569 {
    3570 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
    3571
    3572 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]);
    3573 assert( ! SCIPisFeasNegative(subscip, val) );
    3574
    3575 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    3576 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    3577
    3578 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
    3579 if ( SCIPisFeasGT(scip, val, ABS(weights[k])) )
    3580 weights[k] = val;
    3581 }
    3582 }
    3583
    3584 /* set up data for bounds to use */
    3585 if ( sepadata->cmirownbounds )
    3586 {
    3587 int typefortrans;
    3588
    3589 assert( boundsfortrans != NULL );
    3590 assert( boundtypesfortrans != NULL );
    3591
    3592 if ( sepadata->allowlocal )
    3593 typefortrans = -2;
    3594 else
    3595 typefortrans = -1;
    3596
    3597 /* check all variables */
    3598 for (k = 0; k < nvars; ++k)
    3599 {
    3600 int pos;
    3601 SCIP_VAR* var;
    3602
    3603 var = vars[k];
    3604 assert( var != NULL );
    3605 pos = SCIPcolGetLPPos(SCIPvarGetCol(var));
    3606
    3607 if ( pos < 0 )
    3608 continue;
    3609
    3610 assert( pos < (int) mipdata->ncols );
    3611 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
    3612
    3613 boundsfortrans[k] = typefortrans;
    3614 boundtypesfortrans[k] = SCIP_BOUNDTYPE_LOWER;
    3615
    3616 if ( mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted )
    3617 {
    3618 assert( SCIPvarIsIntegral(var) || mipdata->coltype[pos] != colContinuous );
    3619 continue;
    3620 }
    3621
    3622 /* check upper bound */
    3623 if ( mipdata->z[pos] != NULL && SCIPisSumPositive(subscip, SCIPgetSolVal(subscip, sol, mipdata->z[pos])) )
    3624 {
    3625 /* check whether variable is complemented */
    3626 if ( ! mipdata->iscomplemented[pos] )
    3627 boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER;
    3628 /* otherwise use lower bound */
    3629 }
    3630 else
    3631 {
    3632 /* check whether variable is complemented */
    3633 if ( mipdata->iscomplemented[pos] )
    3634 boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER;
    3635 /* otherwise use lower bound */
    3636 }
    3637 }
    3638 }
    3639
    3640 /* create a MIR cut using the above calculated weights */
    3641 cutefficacy = -1.0;
    3642 cutrhs = -1.0;
    3643 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE,
    3644 sepadata->allowlocal, 2, (int) MAXAGGRLEN(nvars), &success) );
    3645
    3646 if ( ! success )
    3647 return SCIP_OKAY;
    3648
    3649 SCIP_CALL( SCIPcalcMIR(scip, NULL, POSTPROCESS, BOUNDSWITCH, VARTYPEUSEVBDS, sepadata->allowlocal, FIXINTEGRALRHS, boundsfortrans,
    3650 boundtypesfortrans, MINFRAC, MAXFRAC, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy,
    3651 &cutrank, &cutislocal, &success) );
    3652
    3653 assert( sepadata->allowlocal || !cutislocal );
    3654 SCIPdebugMsg(scip, "CMIR: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
    3655 SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs);
    3656
    3657 /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is
    3658 * not violated we might store non-local cuts in the pool. */
    3659 if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
    3660 {
    3661 SCIP_ROW* cut;
    3662
    3663 /* create the cut */
    3664 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
    3665 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
    3666
    3667 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
    3668
    3669 for (k = 0; k < cutnnz; ++k)
    3670 {
    3671 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) );
    3672 }
    3673
    3674 assert( success );
    3675
    3676 /* set cut rank */
    3677 SCIProwChgRank(cut, cutrank);
    3678
    3679#ifdef SCIP_DEBUG
    3680 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3681#else
    3682 if ( sepadata->output )
    3683 {
    3684 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3685 }
    3686#endif
    3687
    3688 /* try to scale the cut to integral values */
    3689 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
    3690 maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
    3691
    3692 /* if the cut could be made integral */
    3693 if ( success )
    3694 {
    3695 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
    3696
    3697 /* add cut to pool */
    3698 if ( ! cutislocal )
    3699 {
    3700 assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool );
    3701 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
    3702 }
    3703
    3704 if ( ! SCIPisCutEfficacious(scip, NULL, cut) )
    3705 {
    3706 SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
    3707 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
    3708 SCIPgetCutEfficacy(scip, NULL, cut));
    3709
    3710 /* release the row */
    3711 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
    3712 }
    3713 else
    3714 {
    3715 /* check whether cut has been found before - may happend due to projection */
    3716 for (k = 0; k < *nprevrows; ++k)
    3717 {
    3718 SCIP_Real parval;
    3719
    3720 assert( prevrows[k] != NULL );
    3721 parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
    3722 /* exit if row is parallel to existing cut and rhs is not better */
    3723 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
    3724 break;
    3725 }
    3726
    3727 /* if cut is new */
    3728 if ( k >= *nprevrows )
    3729 {
    3730 prevrows[*nprevrows] = cut;
    3731 ++(*nprevrows);
    3732
    3733 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
    3734 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
    3735 SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut),
    3736 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
    3737 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
    3738#ifdef SCIP_OUTPUT
    3739 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3740#else
    3741 if ( sepadata->output )
    3742 {
    3743 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3744 }
    3745#endif
    3746 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
    3747 ++(*ngen);
    3748 }
    3749 else
    3750 {
    3751 SCIPdebugMsg(scip, "Cut already exists.\n");
    3752 /* release the row */
    3753 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
    3754 }
    3755 }
    3756 }
    3757 else
    3758 {
    3759 SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
    3760 name, cutefficacy, cutrhs);
    3761
    3762 /* release the row */
    3763 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
    3764 }
    3765 }
    3766
    3767 return SCIP_OKAY;
    3768}
    3769
    3770
    3771/** create CG-cut via strong-CG-function */
    3772static
    3773SCIP_RETCODE createCGCutStrongCG(
    3774 SCIP* scip, /**< SCIP data structure */
    3775 SCIP_SEPA* sepa, /**< separator */
    3776 SCIP_SEPADATA* sepadata, /**< separator data */
    3777 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
    3778 SCIP_SOL* sol, /**< solution of sub-MIP */
    3779 SCIP_AGGRROW* aggrrow, /**< aggregation row to use for creating MIR cut */
    3780 SCIP_Real* cutcoefs, /**< cut coefficients */
    3781 int* cutinds, /**< problem indices of variables appearing in cut */
    3782 SCIP_Real* cutvals, /**< values of variables in cut */
    3783 SCIP_Real* varsolvals, /**< solution value of variables */
    3784 SCIP_Real* weights, /**< weights to compute cmir cut */
    3785 int* nprevrows, /**< number of previously generated rows */
    3786 SCIP_ROW** prevrows, /**< previously generated rows */
    3787 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
    3788 unsigned int* ngen /**< number of generated cuts */
    3789 )
    3790{
    3791 char name[SCIP_MAXSTRLEN];
    3792 SCIP_Longint maxdnom;
    3793 SCIP_Bool cutislocal;
    3794 SCIP_Real maxscale;
    3795 SCIP_Real cutrhs;
    3796 SCIP_Real cutefficacy;
    3797 SCIP_Bool success;
    3798 SCIP_ROW** rows;
    3799 SCIP_VAR** vars;
    3800 SCIP* subscip;
    3801 int nrows;
    3802 int nvars;
    3803 int k;
    3804 int cutrank;
    3805 int cutnnz;
    3806
    3807 assert( scip != NULL );
    3808 assert( sepadata != NULL );
    3809 assert( mipdata != NULL );
    3810 assert( sol != NULL );
    3811 assert( cutcoefs != NULL );
    3812 assert( cutinds != NULL );
    3813 assert( cutvals != NULL );
    3814 assert( varsolvals != NULL );
    3815 assert( weights != NULL );
    3816 assert( nprevrows != NULL );
    3817 assert( prevrows != NULL );
    3818 assert( cutoff != NULL );
    3819 assert( ngen != NULL );
    3820
    3821 *cutoff = FALSE;
    3822 subscip = mipdata->subscip;
    3823 assert( subscip != NULL );
    3824
    3825 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
    3826 assert( nrows > 0 );
    3827 assert( (int) mipdata->nrows == nrows );
    3828
    3829 /* @todo more advanced settings - compare sepa_gomory.c */
    3830 maxdnom = (SCIP_Longint) sepadata->cutcoefbnd + 1;
    3831 maxscale = 10000.0;
    3832
    3833 /* get variable data */
    3834 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
    3835
    3836 /* generate weights */
    3837 for (k = 0; k < nrows; ++k)
    3838 {
    3839 SCIP_Real val;
    3840
    3841 weights[k] = 0;
    3842 if ( mipdata->ylhs[k] != NULL )
    3843 {
    3844 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
    3845
    3846 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]);
    3847 assert( ! SCIPisFeasNegative(subscip, val) );
    3848
    3849 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    3850 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    3851
    3852 if ( SCIPisFeasPositive(subscip, val) )
    3853 weights[k] = -val;
    3854 }
    3855
    3856 if ( mipdata->yrhs[k] != NULL )
    3857 {
    3858 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
    3859
    3860 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]);
    3861 assert( ! SCIPisFeasNegative(subscip, val) );
    3862
    3863 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
    3864 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
    3865
    3866 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
    3867 if ( SCIPisFeasGT(scip, val, ABS(weights[k])) )
    3868 weights[k] = val;
    3869 }
    3870 }
    3871
    3872 /* create a strong CG cut out of the weighted LP rows using the B^-1 row as weights */
    3873 cutefficacy = -1.0;
    3874 cutrhs = -1.0;
    3875 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE,
    3876 sepadata->allowlocal, 1, (int) MAXAGGRLEN(nvars), &success) );
    3877
    3878 if ( ! success )
    3879 return SCIP_OKAY;
    3880
    3881 SCIP_CALL( SCIPcalcStrongCG(scip, NULL, POSTPROCESS, BOUNDSWITCH, VARTYPEUSEVBDS, sepadata->allowlocal, MINFRAC, MAXFRAC,
    3882 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
    3883
    3884 assert( sepadata->allowlocal || !cutislocal );
    3885 SCIPdebugMsg(scip, "Strong-CG: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
    3886 SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs);
    3887
    3888 /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is
    3889 * not violated we might store non-local cuts in the pool. */
    3890 if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
    3891 {
    3892 SCIP_ROW* cut;
    3893
    3894 /* create the cut */
    3895 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
    3896 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
    3897
    3898 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
    3899
    3900 for (k = 0; k < cutnnz; ++k)
    3901 {
    3902 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) );
    3903 }
    3904
    3905 assert( success );
    3906
    3907 /* set cut rank */
    3908 SCIProwChgRank(cut, cutrank);
    3909
    3910#ifdef SCIP_DEBUG
    3911 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3912#else
    3913 if ( sepadata->output )
    3914 {
    3915 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3916 }
    3917#endif
    3918
    3919 /* try to scale the cut to integral values */
    3920 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
    3921 maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
    3922
    3923 /* if the cut could be made integral */
    3924 if ( success )
    3925 {
    3926 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
    3927
    3928 /* add cut to pool */
    3929 if ( ! cutislocal )
    3930 {
    3931 assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool );
    3932 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
    3933 }
    3934
    3935 if ( ! SCIPisCutEfficacious(scip, NULL, cut) )
    3936 {
    3937 SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
    3938 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
    3939 SCIPgetCutEfficacy(scip, NULL, cut));
    3940
    3941 /* release the row */
    3942 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
    3943 }
    3944 else
    3945 {
    3946 /* check whether cut has been found before - may happend due to projection */
    3947 for (k = 0; k < *nprevrows; ++k)
    3948 {
    3949 SCIP_Real parval;
    3950
    3951 assert( prevrows[k] != NULL );
    3952 parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
    3953 /* exit if row is parallel to existing cut and rhs is not better */
    3954 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
    3955 break;
    3956 }
    3957
    3958 /* if cut is new */
    3959 if ( k >= *nprevrows )
    3960 {
    3961 prevrows[*nprevrows] = cut;
    3962 ++(*nprevrows);
    3963
    3964 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
    3965 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
    3966 SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut),
    3967 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
    3968 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
    3969#ifdef SCIP_OUTPUT
    3970 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3971#else
    3972 if ( sepadata->output )
    3973 {
    3974 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
    3975 }
    3976#endif
    3977 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
    3978 ++(*ngen);
    3979 }
    3980 else
    3981 {
    3982 SCIPdebugMsg(scip, "Cut already exists.\n");
    3983 /* release the row */
    3984 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
    3985 }
    3986 }
    3987 }
    3988 else
    3989 {
    3990 SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
    3991 name, cutefficacy, cutrhs);
    3992
    3993 /* release the row */
    3994 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
    3995 }
    3996 }
    3997
    3998 return SCIP_OKAY;
    3999}
    4000
    4001
    4002/** Create CG-cuts from solutions of sub-MIP */
    4003static
    4004SCIP_RETCODE createCGCuts(
    4005 SCIP* scip, /**< SCIP data structure */
    4006 SCIP_SEPA* sepa, /**< separator */
    4007 SCIP_SEPADATA* sepadata, /**< separator data */
    4008 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
    4009 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
    4010 unsigned int* ngen /**< number of generated cuts */
    4011 )
    4012{
    4013 SCIP_BOUNDTYPE* boundtypesfortrans;
    4014 SCIP_STAGE stage;
    4015 SCIP_AGGRROW* aggrrow = NULL;
    4016 SCIP_Real* varsolvals;
    4017 SCIP_Real* weights;
    4018 int* cutinds;
    4019 SCIP_Real* cutvals;
    4020 SCIP_Real* cutcoefs;
    4021 SCIP_ROW** prevrows;
    4022 SCIP_SOL** sols;
    4023 SCIP_VAR** vars;
    4024 SCIP* subscip;
    4025 int* boundsfortrans;
    4026 int nprevrows;
    4027 int ntotalrows;
    4028 int nsols;
    4029 int nvars;
    4030 int k;
    4031 int s;
    4032
    4033 assert( scip != NULL );
    4034 assert( sepadata != NULL );
    4035 assert( mipdata != NULL );
    4036 assert( cutoff != NULL );
    4037 assert( ngen != NULL );
    4038
    4039 subscip = mipdata->subscip;
    4040 assert( subscip != NULL );
    4041
    4042 *cutoff = FALSE;
    4043 *ngen = 0;
    4044
    4045 /* check if solving was successful and get solutions */
    4046 stage = SCIPgetStage(subscip);
    4047 if ( stage == SCIP_STAGE_SOLVING || stage == SCIP_STAGE_SOLVED )
    4048 nsols = SCIPgetNSols(subscip);
    4049 else
    4050 nsols = 0;
    4051
    4052 /* only if solutions have been found */
    4053 if ( nsols == 0 )
    4054 return SCIP_OKAY;
    4055
    4056 SCIPdebugMsg(scip, "Generating CG-cuts from %d sols (cmir: %u, strong-cg: %u) ...\n", nsols, sepadata->usecmir, sepadata->usestrongcg);
    4057
    4058 sols = SCIPgetSols(subscip);
    4059
    4060 /* get variable data */
    4061 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
    4062
    4063 /* allocate temporary memory */
    4064 assert(mipdata->ntotalrows <= INT_MAX);
    4065 ntotalrows = (int)mipdata->ntotalrows;
    4066 assert( ntotalrows >= SCIPgetNLPRows(scip) && ntotalrows <= SCIPgetNLPRows(scip) + 1 );
    4067 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
    4068 SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) );
    4069 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) );
    4070 SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars) );
    4071 SCIP_CALL( SCIPallocBufferArray(scip, &weights, ntotalrows) );
    4072 SCIP_CALL( SCIPallocBufferArray(scip, &prevrows, 2 * nsols) );
    4073
    4074 if ( sepadata->usecmir || sepadata->usestrongcg )
    4075 {
    4076 SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
    4077 }
    4078
    4079 /* prepare arrays for bound information, if requested */
    4080 if ( sepadata->usecmir && sepadata->cmirownbounds )
    4081 {
    4082 SCIP_CALL( SCIPallocBufferArray(scip, &boundsfortrans, nvars) );
    4083 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesfortrans, nvars) );
    4084 }
    4085 else
    4086 {
    4087 boundsfortrans = NULL;
    4088 boundtypesfortrans = NULL;
    4089 }
    4090
    4091 /* get solution values */
    4092 for (k = 0; k < nvars; ++k)
    4093 {
    4094 if ( SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_COLUMN )
    4095 varsolvals[k] = SCIPvarGetLPSol(vars[k]);
    4096 else
    4097 varsolvals[k] = 0.0;
    4098 }
    4099
    4100 /* loop through solutions found */
    4101 nprevrows = 0;
    4102 for (s = 0; s < nsols; ++s)
    4103 {
    4104 SCIP_SOL* sol;
    4105 sol = sols[s];
    4106
    4107 /* generate cuts by the C-MIR and/or Strong-CG functions */
    4108 if ( sepadata->usecmir )
    4109 {
    4110 SCIP_CALL( createCGCutCMIR(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
    4111 boundsfortrans, boundtypesfortrans, &nprevrows, prevrows, cutoff, ngen) );
    4112 }
    4113
    4114 if ( sepadata->usestrongcg )
    4115 {
    4116 SCIP_CALL( createCGCutStrongCG(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
    4117 &nprevrows, prevrows, cutoff, ngen) );
    4118 }
    4119
    4120 if ( ! sepadata->usecmir && ! sepadata->usestrongcg )
    4121 {
    4122 SCIP_CALL( createCGCutDirect(scip, sepa, sepadata, mipdata, sol, cutcoefs, cutinds, cutvals, varsolvals, weights,
    4123 &nprevrows, prevrows, cutoff, ngen) );
    4124
    4125 assert(! sepadata->usecmir && ! sepadata->usestrongcg);
    4126 }
    4127 }
    4128 assert( nprevrows <= 2 * nsols );
    4129 assert( sepadata->usecmir || nprevrows <= nsols );
    4130 assert( sepadata->usestrongcg || nprevrows <= nsols );
    4131
    4132 /* release rows */
    4133 for (k = 0; k < nprevrows; ++k)
    4134 {
    4135 SCIP_CALL( SCIPreleaseRow(scip, &(prevrows[k])) );
    4136 }
    4137
    4138 if ( sepadata->usecmir || sepadata->usestrongcg )
    4139 SCIPaggrRowFree(scip, &aggrrow);
    4140
    4141 /* free temporary memory */
    4142 SCIPfreeBufferArrayNull(scip, &boundsfortrans);
    4143 SCIPfreeBufferArrayNull(scip, &boundtypesfortrans);
    4144
    4145 SCIPfreeBufferArray(scip, &prevrows);
    4146 SCIPfreeBufferArray(scip, &weights);
    4147 SCIPfreeBufferArray(scip, &cutvals);
    4148 SCIPfreeBufferArray(scip, &cutinds);
    4149 SCIPfreeBufferArray(scip, &varsolvals);
    4150 SCIPfreeBufferArray(scip, &cutcoefs);
    4151
    4152 return SCIP_OKAY;
    4153}
    4154
    4155
    4156/** frees "subscip" data */
    4157static
    4158SCIP_RETCODE freeSubscip(
    4159 SCIP* scip, /**< SCIP data structure */
    4160 SCIP_SEPA* sepa, /**< separator data */
    4161 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
    4162 )
    4163{
    4164 SCIP_SEPADATA* sepadata;
    4165 unsigned int i, j;
    4166 SCIP* subscip;
    4167
    4168 assert( scip != NULL );
    4169 assert( sepa != NULL );
    4170 assert( mipdata != NULL );
    4171
    4172 /* free separator data */
    4173 sepadata = SCIPsepaGetData(sepa);
    4174 assert( sepadata != NULL );
    4175
    4176 SCIPdebugMsg(scip, "Freeing subscip ...\n");
    4177
    4178 subscip = mipdata->subscip;
    4179 assert( subscip != NULL );
    4180
    4181 for (j = 0; j < mipdata->ncols; ++j)
    4182 {
    4183 if ( mipdata->coltype[j] == colPresent )
    4184 {
    4185 assert( mipdata->alpha[j] != NULL );
    4186 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->alpha[j])) );
    4187 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracalpha[j])) );
    4188 }
    4189 }
    4190 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->beta)) );
    4191 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracbeta)) );
    4192
    4193 for (i = 0; i < mipdata->nrows; ++i)
    4194 {
    4195 if ( mipdata->ylhs[i] != NULL )
    4196 {
    4197 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[i])) );
    4198 }
    4199 if ( mipdata->yrhs[i] != NULL )
    4200 {
    4201 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[i])) );
    4202 }
    4203 }
    4204
    4205 if ( sepadata->useobjub || sepadata->useobjlb )
    4206 {
    4207 if ( mipdata->yrhs[mipdata->nrows] )
    4208 {
    4209 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[mipdata->nrows])) );
    4210 }
    4211 if ( mipdata->ylhs[mipdata->nrows] )
    4212 {
    4213 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[mipdata->nrows])) );
    4214 }
    4215 }
    4216
    4217 for (j = 0; j < mipdata->ncols; ++j)
    4218 {
    4219 if ( mipdata->z[j] != NULL )
    4220 {
    4221 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->z[j])) );
    4222 }
    4223 }
    4224
    4225 SCIP_CALL( SCIPfree(&(mipdata->subscip)) );
    4226
    4227 SCIPfreeBlockMemoryArray(scip, &(mipdata->rhs), mipdata->ntotalrows);
    4228 SCIPfreeBlockMemoryArray(scip, &(mipdata->lhs), mipdata->ntotalrows);
    4229 SCIPfreeBlockMemoryArray(scip, &(mipdata->z), 2*mipdata->ncols); /*lint !e647*/
    4230 SCIPfreeBlockMemoryArray(scip, &(mipdata->yrhs), mipdata->ntotalrows);
    4231 SCIPfreeBlockMemoryArray(scip, &(mipdata->ylhs), mipdata->ntotalrows);
    4232 SCIPfreeBlockMemoryArray(scip, &(mipdata->isshifted), mipdata->ncols);
    4233 SCIPfreeBlockMemoryArray(scip, &(mipdata->iscomplemented), mipdata->ncols);
    4234 SCIPfreeBlockMemoryArray(scip, &(mipdata->coltype), mipdata->ncols);
    4235 SCIPfreeBlockMemoryArray(scip, &(mipdata->fracalpha), mipdata->ncols);
    4236 SCIPfreeBlockMemoryArray(scip, &(mipdata->alpha), mipdata->ncols);
    4237
    4238 return SCIP_OKAY;
    4239}
    4240
    4241
    4242/*
    4243 * Callback methods
    4244 */
    4245
    4246
    4247/** initialization method of separator (called after problem was transformed) */
    4248static
    4249SCIP_DECL_SEPAINIT(sepaInitCGMIP)
    4250{
    4251 SCIP_SEPADATA* sepadata;
    4252
    4253 sepadata = SCIPsepaGetData(sepa);
    4254 assert(sepadata != NULL);
    4255
    4256 /* create and initialize random number generator */
    4257 SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, DEFAULT_RANDSEED, TRUE) );
    4258
    4259 return SCIP_OKAY;
    4260}
    4261
    4262/** deinitialization method of separator (called before transformed problem is freed) */
    4263static
    4264SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
    4265{ /*lint --e{715}*/
    4266 SCIP_SEPADATA* sepadata;
    4267
    4268 sepadata = SCIPsepaGetData(sepa);
    4269 assert(sepadata != NULL);
    4270
    4271 SCIPfreeRandom(scip, &sepadata->randnumgen);
    4272
    4273 return SCIP_OKAY;
    4274}
    4275
    4276/** copy method for separator plugins (called when SCIP copies plugins) */
    4277static
    4278SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
    4279{ /*lint --e{715}*/
    4280 assert( scip != NULL );
    4281 assert( sepa != NULL );
    4282
    4283 SCIP_STRINGEQ( SCIPsepaGetName(sepa), SEPA_NAME, SCIP_INVALIDCALL );
    4284
    4285 /* call inclusion method of constraint handler */
    4286 SCIP_CALL( SCIPincludeSepaCGMIP(scip) );
    4287
    4288 return SCIP_OKAY;
    4289}
    4290
    4291
    4292/** destructor of separator to free user data (called when SCIP is exiting) */
    4293static
    4294SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
    4295{ /*lint --e{715}*/
    4296 SCIP_SEPADATA* sepadata;
    4297
    4298 assert( scip != NULL );
    4299 assert( sepa != NULL );
    4300
    4301 SCIP_STRINGEQ( SCIPsepaGetName(sepa), SEPA_NAME, SCIP_INVALIDCALL );
    4302
    4303 /* free separator data */
    4304 sepadata = SCIPsepaGetData(sepa);
    4305 assert( sepadata != NULL );
    4306
    4307 SCIPfreeBlockMemory(scip, &sepadata);
    4308
    4309 SCIPsepaSetData(sepa, NULL);
    4310
    4311 return SCIP_OKAY;
    4312}
    4313
    4314
    4315/** LP solution separation method of separator */
    4316static
    4317SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
    4318{ /*lint --e{715}*/
    4319 SCIP_SEPADATA* sepadata;
    4320 CGMIP_MIPDATA* mipdata;
    4321
    4322 int ncalls;
    4323 int ncols;
    4324 int nrows;
    4325 unsigned int ngen = 0;
    4326 SCIP_Bool success;
    4327 SCIP_Bool cutoff = FALSE;
    4328
    4329 assert( scip != NULL );
    4330 assert( sepa != NULL );
    4331 assert( result != NULL );
    4332
    4333 SCIP_STRINGEQ( SCIPsepaGetName(sepa), SEPA_NAME, SCIP_INVALIDCALL );
    4334
    4335 *result = SCIP_DIDNOTRUN;
    4336
    4337 sepadata = SCIPsepaGetData(sepa);
    4338 assert(sepadata != NULL);
    4339
    4340 /* only call separator, if we are not close to terminating */
    4341 if ( SCIPisStopped(scip) )
    4342 return SCIP_OKAY;
    4343
    4344 /* only call separator up to a maximum depth */
    4345 if ( sepadata->maxdepth >= 0 && depth > sepadata->maxdepth )
    4346 return SCIP_OKAY;
    4347
    4348 /* only call separator a given number of times at each node */
    4349 ncalls = SCIPsepaGetNCallsAtNode(sepa);
    4350 if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
    4351 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
    4352 return SCIP_OKAY;
    4353
    4354 /* only call separator, if an optimal LP solution is at hand */
    4355 if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
    4356 return SCIP_OKAY;
    4357
    4358 /* skip separation if there are continuous variables, but only integers required */
    4359 if ( SCIPgetNContVars(scip) > 0 && sepadata->onlyintvars )
    4360 return SCIP_OKAY;
    4361
    4362 /* only call separator, if there are fractional variables */
    4363 if ( SCIPgetNLPBranchCands(scip) == 0 )
    4364 return SCIP_OKAY;
    4365
    4366 /* check for parameters */
    4367 if ( ( sepadata->useobjub || sepadata->useobjlb ) && ( sepadata->usecmir || sepadata->usestrongcg ) )
    4368 {
    4369 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
    4370 "WARNING - sepa_cgmip: Using objective function bounds and CMIR or Strong-CG functions is useless. Turning off usage of objective function bounds.\n");
    4371 SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjub", FALSE) );
    4372 SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjlb", FALSE) );
    4373 }
    4374 sepadata->allowlocal = allowlocal;
    4375
    4376 /* get LP data */
    4377 ncols = SCIPgetNLPCols(scip);
    4378 nrows = SCIPgetNLPRows(scip);
    4379 if ( ncols <= NCOLSTOOSMALL || nrows <= NROWSTOOSMALL )
    4380 return SCIP_OKAY;
    4381
    4382 /* determine whether we should run the separation based on a decision tree */
    4383 if ( sepadata->decisiontree )
    4384 {
    4385 SCIP_Bool separate;
    4386 SCIP_Real firstlptime;
    4387
    4388 separate = FALSE;
    4389 firstlptime = SCIPgetFirstLPTime(scip);
    4390
    4391 if ( nrows <= 136 && firstlptime <= 0.05 && ncols <= 143 )
    4392 separate = TRUE;
    4393 else if ( nrows <= 136 && 0.05 < firstlptime && firstlptime <= 0.15 && ncols <= 143 )
    4394 separate = TRUE;
    4395 else if ( 136 < nrows && nrows <= 332 && ncols <= 143 )
    4396 separate = TRUE;
    4397 else if ( 136 < nrows && nrows <= 332 && 655 < ncols && ncols <= 1290 )
    4398 separate = TRUE;
    4399 else if ( 333 < nrows && nrows <= 874 && 0.15 < firstlptime && firstlptime <= 0.25 && 2614 < ncols && ncols <= 5141 )
    4400 separate = TRUE;
    4401 else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 143 < ncols && ncols <= 265 )
    4402 separate = TRUE;
    4403 else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 265 < ncols && ncols <= 654 )
    4404 separate = TRUE;
    4405 else if ( 875 < nrows && nrows <= 1676 && 0.05 < firstlptime && firstlptime <= 0.15 )
    4406 separate = TRUE;
    4407 else if ( 875 < nrows && nrows <= 1676 && 0.15 < firstlptime && firstlptime <= 0.25 && 1291 < ncols && ncols <= 2613 )
    4408 separate = TRUE;
    4409 else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 655 < ncols && ncols <= 1290 )
    4410 separate = TRUE;
    4411 else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 1291 < ncols && ncols <= 2613 )
    4412 separate = TRUE;
    4413 else if ( nrows > 8146 && firstlptime > 6.25 )
    4414 separate = TRUE;
    4415
    4416 if ( ! separate )
    4417 {
    4418 return SCIP_OKAY;
    4419 }
    4420 }
    4421
    4422 /* preceed with separation */
    4423 *result = SCIP_DIDNOTFIND;
    4424
    4425 SCIPdebugMsg(scip, "separating CG-cuts via sub-MIPs: %d cols, %d rows\n", ncols, nrows);
    4426
    4427 /* prepare data */
    4428 SCIP_CALL( SCIPallocBlockMemory(scip, &mipdata) );
    4429 mipdata->subscip = NULL;
    4430 mipdata->alpha = NULL;
    4431 mipdata->fracalpha = NULL;
    4432 mipdata->beta = NULL;
    4433 mipdata->fracbeta = NULL;
    4434 mipdata->coltype = NULL;
    4435 mipdata->iscomplemented = NULL;
    4436 mipdata->isshifted = NULL;
    4437 mipdata->ylhs = NULL;
    4438 mipdata->yrhs = NULL;
    4439 mipdata->z = NULL;
    4440 mipdata->lhs = NULL;
    4441 mipdata->rhs = NULL;
    4442 mipdata->normtype = ' ';
    4443
    4444 mipdata->conshdlrfullnorm = CONSHDLRFULLNORM;
    4445 mipdata->scip = scip;
    4446 mipdata->sepa = sepa;
    4447 mipdata->sepadata = sepadata;
    4448
    4449 /* get the type of norm to use for efficacy calculations */
    4450 SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &mipdata->normtype) );
    4451
    4452 /* create subscip */
    4453 SCIP_CALL( createSubscip(scip, sepa, sepadata, mipdata) );
    4454
    4455 /* set parameters */
    4456 SCIP_CALL( subscipSetParams(sepadata, mipdata) );
    4457
    4458 if ( ! SCIPisStopped(scip) )
    4459 {
    4460 /* solve subscip */
    4461 SCIP_CALL( solveSubscip(scip, sepadata, mipdata, &success) );
    4462
    4463 /* preceed if solution was successful */
    4464 if ( success && ! SCIPisStopped(scip) )
    4465 {
    4466 SCIP_CALL( createCGCuts(scip, sepa, sepadata, mipdata, &cutoff, &ngen) );
    4467 }
    4468 }
    4469
    4470 SCIP_CALL( freeSubscip(scip, sepa, mipdata) );
    4471 SCIPfreeBlockMemory(scip, &mipdata);
    4472
    4473 SCIPdebugMsg(scip, "Found %u CG-cuts.\n", ngen);
    4474
    4475 if ( cutoff )
    4476 *result = SCIP_CUTOFF;
    4477 else if ( ngen > 0 )
    4478 *result = SCIP_SEPARATED;
    4479
    4480#ifdef SCIP_OUTPUT
    4481 /* SCIP_CALL( SCIPwriteLP(scip, "cuts.lp") ); */
    4482 /* SCIP_CALL( SCIPwriteMIP(scip, "cuts.lp", FALSE, TRUE) ); */
    4483#endif
    4484
    4485 return SCIP_OKAY;
    4486}
    4487
    4488/*
    4489 * separator specific interface methods
    4490 */
    4491
    4492/** creates the CGMIP MIR cut separator and includes it in SCIP */
    4493SCIP_RETCODE SCIPincludeSepaCGMIP(
    4494 SCIP* scip /**< SCIP data structure */
    4495 )
    4496{
    4497 SCIP_SEPADATA* sepadata;
    4498 SCIP_SEPA* sepa = NULL;
    4499
    4500 /* create separator data */
    4501 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
    4502
    4503 /* include separator */
    4504 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
    4505 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpCGMIP, NULL, sepadata) );
    4506 assert(sepa != NULL);
    4507
    4508 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyCGMIP) );
    4509 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeCGMIP) );
    4510 SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitCGMIP) );
    4511 SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitCGMIP) );
    4512
    4513 /* add separator parameters */
    4514 SCIP_CALL( SCIPaddIntParam(scip,
    4515 "separating/" SEPA_NAME "/maxrounds",
    4516 "maximal number of cgmip separation rounds per node (-1: unlimited)",
    4517 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
    4518
    4519 SCIP_CALL( SCIPaddIntParam(scip,
    4520 "separating/" SEPA_NAME "/maxroundsroot",
    4521 "maximal number of cgmip separation rounds in the root node (-1: unlimited)",
    4522 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
    4523
    4524 SCIP_CALL( SCIPaddIntParam(scip,
    4525 "separating/" SEPA_NAME "/maxdepth",
    4526 "maximal depth at which the separator is applied (-1: unlimited)",
    4527 &sepadata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
    4528
    4529 SCIP_CALL( SCIPaddBoolParam(scip,
    4530 "separating/" SEPA_NAME "/decisiontree",
    4531 "Use decision tree to turn separation on/off?",
    4532 &sepadata->decisiontree, FALSE, DEFAULT_DECISIONTREE, NULL, NULL) );
    4533
    4534 SCIP_CALL( SCIPaddRealParam(scip,
    4535 "separating/" SEPA_NAME "/timelimit",
    4536 "time limit for sub-MIP",
    4537 &sepadata->timelimit, TRUE, DEFAULT_TIMELIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
    4538
    4539 SCIP_CALL( SCIPaddRealParam(scip,
    4540 "separating/" SEPA_NAME "/memorylimit",
    4541 "memory limit for sub-MIP",
    4542 &sepadata->memorylimit, TRUE, DEFAULT_MEMORYLIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
    4543
    4544 SCIP_CALL( SCIPaddLongintParam(scip,
    4545 "separating/" SEPA_NAME "/minnodelimit",
    4546 "minimum number of nodes considered for sub-MIP (-1: unlimited)",
    4547 &sepadata->minnodelimit, FALSE, DEFAULT_MINNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
    4548
    4549 SCIP_CALL( SCIPaddLongintParam(scip,
    4550 "separating/" SEPA_NAME "/maxnodelimit",
    4551 "maximum number of nodes considered for sub-MIP (-1: unlimited)",
    4552 &sepadata->maxnodelimit, FALSE, DEFAULT_MAXNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
    4553
    4554 SCIP_CALL( SCIPaddRealParam(scip,
    4555 "separating/" SEPA_NAME "/cutcoefbnd",
    4556 "bounds on the values of the coefficients in the CG-cut",
    4557 &sepadata->cutcoefbnd, TRUE, DEFAULT_CUTCOEFBND, 0.0, SCIP_REAL_MAX, NULL, NULL) );
    4558
    4559 SCIP_CALL( SCIPaddBoolParam(scip,
    4560 "separating/" SEPA_NAME "/onlyactiverows",
    4561 "Use only active rows to generate cuts?",
    4562 &sepadata->onlyactiverows, FALSE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) );
    4563
    4564 SCIP_CALL( SCIPaddIntParam(scip,
    4565 "separating/" SEPA_NAME "/maxrowage",
    4566 "maximal age of rows to consider if onlyactiverows is false",
    4567 &sepadata->maxrowage, FALSE, DEFAULT_MAXROWAGE, -1, INT_MAX, NULL, NULL) );
    4568
    4569 SCIP_CALL( SCIPaddBoolParam(scip,
    4570 "separating/" SEPA_NAME "/onlyrankone",
    4571 "Separate only rank 1 inequalities w.r.t. CG-MIP separator?",
    4572 &sepadata->onlyrankone, FALSE, DEFAULT_ONLYRANKONE, NULL, NULL) );
    4573
    4574 SCIP_CALL( SCIPaddBoolParam(scip,
    4575 "separating/" SEPA_NAME "/onlyintvars",
    4576 "Generate cuts for problems with only integer variables?",
    4577 &sepadata->onlyintvars, FALSE, DEFAULT_ONLYINTVARS, NULL, NULL) );
    4578
    4579 SCIP_CALL( SCIPaddBoolParam(scip,
    4580 "separating/" SEPA_NAME "/contconvert",
    4581 "Convert some integral variables to be continuous to reduce the size of the sub-MIP?",
    4582 &sepadata->contconvert, FALSE, DEFAULT_CONTCONVERT, NULL, NULL) );
    4583
    4584 SCIP_CALL( SCIPaddRealParam(scip,
    4585 "separating/" SEPA_NAME "/contconvfrac",
    4586 "fraction of integral variables converted to be continuous (if contconvert)",
    4587 &sepadata->contconvfrac, FALSE, DEFAULT_CONTCONVFRAC, 0.0, 1.0, NULL, NULL) );
    4588
    4589 SCIP_CALL( SCIPaddIntParam(scip,
    4590 "separating/" SEPA_NAME "/contconvmin",
    4591 "minimum number of integral variables before some are converted to be continuous",
    4592 &sepadata->contconvmin, FALSE, DEFAULT_CONTCONVMIN, -1, INT_MAX, NULL, NULL) );
    4593
    4594 SCIP_CALL( SCIPaddBoolParam(scip,
    4595 "separating/" SEPA_NAME "/intconvert",
    4596 "Convert some integral variables attaining fractional values to have integral value?",
    4597 &sepadata->intconvert, FALSE, DEFAULT_INTCONVERT, NULL, NULL) );
    4598
    4599 SCIP_CALL( SCIPaddRealParam(scip,
    4600 "separating/" SEPA_NAME "/intconvfrac",
    4601 "fraction of frac. integral variables converted to have integral value (if intconvert)",
    4602 &sepadata->intconvfrac, FALSE, DEFAULT_INTCONVFRAC, 0.0, 1.0, NULL, NULL) );
    4603
    4604 SCIP_CALL( SCIPaddIntParam(scip,
    4605 "separating/" SEPA_NAME "/intconvmin",
    4606 "minimum number of integral variables before some are converted to have integral value",
    4607 &sepadata->intconvmin, FALSE, DEFAULT_INTCONVMIN, -1, INT_MAX, NULL, NULL) );
    4608
    4609 SCIP_CALL( SCIPaddBoolParam(scip,
    4610 "separating/" SEPA_NAME "/skipmultbounds",
    4611 "Skip the upper bounds on the multipliers in the sub-MIP?",
    4612 &sepadata->skipmultbounds, FALSE, DEFAULT_SKIPMULTBOUNDS, NULL, NULL) );
    4613
    4614 SCIP_CALL( SCIPaddBoolParam(scip,
    4615 "separating/" SEPA_NAME "/objlone",
    4616 "Should the objective of the sub-MIP minimize the l1-norm of the multipliers?",
    4617 &sepadata->objlone, FALSE, DEFAULT_OBJLONE, NULL, NULL) );
    4618
    4619 SCIP_CALL( SCIPaddRealParam(scip,
    4620 "separating/" SEPA_NAME "/objweight",
    4621 "weight used for the row combination coefficient in the sub-MIP objective",
    4622 &sepadata->objweight, TRUE, DEFAULT_OBJWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
    4623
    4624 SCIP_CALL( SCIPaddBoolParam(scip,
    4625 "separating/" SEPA_NAME "/objweightsize",
    4626 "Weight each row by its size?",
    4627 &sepadata->objweightsize, FALSE, DEFAULT_OBJWEIGHTSIZE, NULL, NULL) );
    4628
    4629 SCIP_CALL( SCIPaddBoolParam(scip,
    4630 "separating/" SEPA_NAME "/dynamiccuts",
    4631 "should generated cuts be removed from the LP if they are no longer tight?",
    4632 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
    4633
    4634 SCIP_CALL( SCIPaddBoolParam(scip,
    4635 "separating/" SEPA_NAME "/usecmir",
    4636 "use CMIR-generator (otherwise add cut directly)?",
    4637 &sepadata->usecmir, FALSE, DEFAULT_USECMIR, NULL, NULL) );
    4638
    4639 SCIP_CALL( SCIPaddBoolParam(scip,
    4640 "separating/" SEPA_NAME "/usestrongcg",
    4641 "use strong CG-function to strengthen cut?",
    4642 &sepadata->usestrongcg, FALSE, DEFAULT_USESTRONGCG, NULL, NULL) );
    4643
    4644 SCIP_CALL( SCIPaddBoolParam(scip,
    4645 "separating/" SEPA_NAME "/cmirownbounds",
    4646 "tell CMIR-generator which bounds to used in rounding?",
    4647 &sepadata->cmirownbounds, FALSE, DEFAULT_CMIROWNBOUNDS, NULL, NULL) );
    4648
    4649 SCIP_CALL( SCIPaddBoolParam(scip,
    4650 "separating/" SEPA_NAME "/usecutpool",
    4651 "use cutpool to store CG-cuts even if the are not efficient?",
    4652 &sepadata->usecutpool, FALSE, DEFAULT_USECUTPOOL, NULL, NULL) );
    4653
    4654 SCIP_CALL( SCIPaddBoolParam(scip,
    4655 "separating/" SEPA_NAME "/primalseparation",
    4656 "only separate cuts that are tight for the best feasible solution?",
    4657 &sepadata->primalseparation, FALSE, DEFAULT_PRIMALSEPARATION, NULL, NULL) );
    4658
    4659 SCIP_CALL( SCIPaddBoolParam(scip,
    4660 "separating/" SEPA_NAME "/earlyterm",
    4661 "terminate separation if a violated (but possibly sub-optimal) cut has been found?",
    4662 &sepadata->earlyterm, FALSE, DEFAULT_EARLYTERM, NULL, NULL) );
    4663
    4664 SCIP_CALL( SCIPaddBoolParam(scip,
    4665 "separating/" SEPA_NAME "/addviolationcons",
    4666 "add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?",
    4667 &sepadata->addviolationcons, FALSE, DEFAULT_ADDVIOLATIONCONS, NULL, NULL) );
    4668
    4669 SCIP_CALL( SCIPaddBoolParam(scip,
    4670 "separating/" SEPA_NAME "/addviolconshdlr",
    4671 "add constraint handler to filter out violated cuts?",
    4672 &sepadata->addviolconshdlr, FALSE, DEFAULT_ADDVIOLCONSHDLR, NULL, NULL) );
    4673
    4674 SCIP_CALL( SCIPaddBoolParam(scip,
    4675 "separating/" SEPA_NAME "/conshdlrusenorm",
    4676 "should the violation constraint handler use the norm of a cut to check for feasibility?",
    4677 &sepadata->conshdlrusenorm, FALSE, DEFAULT_CONSHDLRUSENORM, NULL, NULL) );
    4678
    4679 SCIP_CALL( SCIPaddBoolParam(scip,
    4680 "separating/" SEPA_NAME "/useobjub",
    4681 "Use upper bound on objective function (via primal solution)?",
    4682 &sepadata->useobjub, FALSE, DEFAULT_USEOBJUB, NULL, NULL) );
    4683
    4684 SCIP_CALL( SCIPaddBoolParam(scip,
    4685 "separating/" SEPA_NAME "/useobjlb",
    4686 "Use lower bound on objective function (via primal solution)?",
    4687 &sepadata->useobjlb, FALSE, DEFAULT_USEOBJLB, NULL, NULL) );
    4688
    4689 SCIP_CALL( SCIPaddBoolParam(scip,
    4690 "separating/" SEPA_NAME "/subscipfast",
    4691 "Should the settings for the sub-MIP be optimized for speed?",
    4692 &sepadata->subscipfast, FALSE, DEFAULT_SUBSCIPFAST, NULL, NULL) );
    4693
    4694 SCIP_CALL( SCIPaddBoolParam(scip,
    4695 "separating/" SEPA_NAME "/output",
    4696 "Should information about the sub-MIP and cuts be displayed?",
    4697 &sepadata->output, FALSE, DEFAULT_OUTPUT, NULL, NULL) );
    4698
    4699 SCIP_CALL( SCIPaddBoolParam(scip,
    4700 "separating/" SEPA_NAME "/genprimalsols",
    4701 "Try to generate primal solutions from Gomory cuts?",
    4702 &sepadata->genprimalsols, FALSE, DEFAULT_GENPRIMALSOLS, NULL, NULL) );
    4703
    4704 return SCIP_OKAY;
    4705}
    a
    SCIP_VAR * a
    Definition: circlepacking.c:66
    r
    SCIP_Real * r
    Definition: circlepacking.c:59
    cons_linear.h
    Constraint handler for linear constraints in their most general form, .
    cuts.h
    methods for the aggregation rows
    NULL
    #define NULL
    Definition: def.h:257
    SCIP_MAXSTRLEN
    #define SCIP_MAXSTRLEN
    Definition: def.h:278
    SCIP_Longint
    #define SCIP_Longint
    Definition: def.h:150
    SCIP_REAL_MAX
    #define SCIP_REAL_MAX
    Definition: def.h:167
    SCIP_INVALID
    #define SCIP_INVALID
    Definition: def.h:187
    SCIP_Bool
    #define SCIP_Bool
    Definition: def.h:100
    MIN
    #define MIN(x, y)
    Definition: def.h:233
    SCIP_STRINGEQ
    #define SCIP_STRINGEQ(name, reference, retcode)
    Definition: def.h:454
    SCIP_Real
    #define SCIP_Real
    Definition: def.h:165
    ABS
    #define ABS(x)
    Definition: def.h:225
    SQR
    #define SQR(x)
    Definition: def.h:208
    TRUE
    #define TRUE
    Definition: def.h:102
    FALSE
    #define FALSE
    Definition: def.h:103
    MAX
    #define MAX(x, y)
    Definition: def.h:229
    SCIP_LONGINT_FORMAT
    #define SCIP_LONGINT_FORMAT
    Definition: def.h:157
    REALABS
    #define REALABS(x)
    Definition: def.h:191
    SCIP_LONGINT_MAX
    #define SCIP_LONGINT_MAX
    Definition: def.h:151
    SCIP_CALL
    #define SCIP_CALL(x)
    Definition: def.h:364
    SCIPcreateConsLinear
    SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
    Definition: cons_linear.c:17767
    SCIPsetSubscipDepth
    void SCIPsetSubscipDepth(SCIP *scip, int newdepth)
    Definition: scip_copy.c:2610
    SCIPcheckCopyLimits
    SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
    Definition: scip_copy.c:3250
    SCIPgetSubscipDepth
    int SCIPgetSubscipDepth(SCIP *scip)
    Definition: scip_copy.c:2589
    SCIPisStopped
    SCIP_Bool SCIPisStopped(SCIP *scip)
    Definition: scip_general.c:767
    SCIPfree
    SCIP_RETCODE SCIPfree(SCIP **scip)
    Definition: scip_general.c:402
    SCIPcreate
    SCIP_RETCODE SCIPcreate(SCIP **scip)
    Definition: scip_general.c:370
    SCIPgetStatus
    SCIP_STATUS SCIPgetStatus(SCIP *scip)
    Definition: scip_general.c:562
    SCIPgetStage
    SCIP_STAGE SCIPgetStage(SCIP *scip)
    Definition: scip_general.c:444
    SCIPgetNObjVars
    int SCIPgetNObjVars(SCIP *scip)
    Definition: scip_prob.c:2616
    SCIPaddVar
    SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
    Definition: scip_prob.c:1907
    SCIPgetNIntVars
    int SCIPgetNIntVars(SCIP *scip)
    Definition: scip_prob.c:2340
    SCIPgetNImplVars
    int SCIPgetNImplVars(SCIP *scip)
    Definition: scip_prob.c:2387
    SCIPgetProbName
    const char * SCIPgetProbName(SCIP *scip)
    Definition: scip_prob.c:1242
    SCIPgetNContVars
    int SCIPgetNContVars(SCIP *scip)
    Definition: scip_prob.c:2569
    SCIPwriteOrigProblem
    SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
    Definition: scip_prob.c:742
    SCIPsetObjlimit
    SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
    Definition: scip_prob.c:1661
    SCIPgetVarsData
    SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
    Definition: scip_prob.c:2115
    SCIPaddCons
    SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
    Definition: scip_prob.c:3274
    SCIPsetObjsense
    SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
    Definition: scip_prob.c:1417
    SCIPcreateProb
    SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
    Definition: scip_prob.c:119
    SCIPgetNBinVars
    int SCIPgetNBinVars(SCIP *scip)
    Definition: scip_prob.c:2293
    SCIPisObjIntegral
    SCIP_Bool SCIPisObjIntegral(SCIP *scip)
    Definition: scip_prob.c:1801
    SCIPinfoMessage
    void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
    Definition: scip_message.c:208
    SCIPverbMessage
    void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
    Definition: scip_message.c:225
    SCIPdebugMsg
    #define SCIPdebugMsg
    Definition: scip_message.h:78
    SCIPwarningMessage
    void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
    Definition: scip_message.c:120
    SCIPaddLongintParam
    SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
    Definition: scip_param.c:111
    SCIPisParamFixed
    SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
    Definition: scip_param.c:219
    SCIPaddIntParam
    SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
    Definition: scip_param.c:83
    SCIPsetLongintParam
    SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
    Definition: scip_param.c:545
    SCIPaddRealParam
    SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
    Definition: scip_param.c:139
    SCIPsetIntParam
    SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
    Definition: scip_param.c:487
    SCIPsetSubscipsOff
    SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
    Definition: scip_param.c:904
    SCIPgetRealParam
    SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
    Definition: scip_param.c:307
    SCIPwriteParams
    SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
    Definition: scip_param.c:813
    SCIPsetPresolving
    SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
    Definition: scip_param.c:956
    SCIPsetEmphasis
    SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
    Definition: scip_param.c:882
    SCIPaddBoolParam
    SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
    Definition: scip_param.c:57
    SCIPsetBoolParam
    SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
    Definition: scip_param.c:429
    SCIPsetRealParam
    SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
    Definition: scip_param.c:603
    SCIPsetSeparating
    SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
    Definition: scip_param.c:985
    SCIPgetCharParam
    SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
    Definition: scip_param.c:326
    SCIPgetNLPBranchCands
    int SCIPgetNLPBranchCands(SCIP *scip)
    Definition: scip_branch.c:436
    SCIPcolGetLPPos
    int SCIPcolGetLPPos(SCIP_COL *col)
    Definition: lp.c:17487
    SCIPcolGetVar
    SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
    Definition: lp.c:17425
    SCIPcolIsIntegral
    SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
    Definition: lp.c:17455
    SCIPcolGetObj
    SCIP_Real SCIPcolGetObj(SCIP_COL *col)
    Definition: lp.c:17336
    SCIPcolGetVals
    SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
    Definition: lp.c:17555
    SCIPcolGetRows
    SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
    Definition: lp.c:17545
    SCIPcolGetLb
    SCIP_Real SCIPcolGetLb(SCIP_COL *col)
    Definition: lp.c:17346
    SCIPcolGetPrimsol
    SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
    Definition: lp.c:17379
    SCIPcolGetUb
    SCIP_Real SCIPcolGetUb(SCIP_COL *col)
    Definition: lp.c:17356
    SCIPcolGetNLPNonz
    int SCIPcolGetNLPNonz(SCIP_COL *col)
    Definition: lp.c:17534
    SCIPincludeConshdlrBasic
    SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
    Definition: scip_cons.c:181
    SCIPsetConshdlrFree
    SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
    Definition: scip_cons.c:372
    SCIPconshdlrGetData
    SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
    Definition: cons.c:4340
    SCIPreleaseCons
    SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
    Definition: scip_cons.c:1173
    SCIPaddPoolCut
    SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
    Definition: scip_cut.c:336
    SCIPgetCutEfficacy
    SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
    Definition: scip_cut.c:94
    SCIPcalcMIR
    SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, int vartypeusevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
    Definition: cuts.c:7934
    SCIPaggrRowCreate
    SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
    Definition: cuts.c:2679
    SCIPisCutEfficacious
    SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
    Definition: scip_cut.c:117
    SCIPisEfficacious
    SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
    Definition: scip_cut.c:135
    SCIPcalcStrongCG
    SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, int vartypeusevbds, SCIP_Bool allowlocal, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
    Definition: cuts.c:13313
    SCIPaggrRowFree
    void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
    Definition: cuts.c:2711
    SCIPaddRow
    SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
    Definition: scip_cut.c:225
    SCIPaggrRowSumRows
    SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
    Definition: cuts.c:3534
    SCIPgetLPBasisInd
    SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
    Definition: scip_lp.c:692
    SCIPgetLPColsData
    SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
    Definition: scip_lp.c:477
    SCIPgetLPRowsData
    SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
    Definition: scip_lp.c:576
    SCIPgetNLPRows
    int SCIPgetNLPRows(SCIP *scip)
    Definition: scip_lp.c:632
    SCIPgetLPSolstat
    SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
    Definition: scip_lp.c:174
    SCIPgetNLPCols
    int SCIPgetNLPCols(SCIP *scip)
    Definition: scip_lp.c:533
    SCIPgetLPBInvRow
    SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
    Definition: scip_lp.c:720
    SCIPgetMemExternEstim
    SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
    Definition: scip_mem.c:126
    SCIPfreeBlockMemoryArray
    #define SCIPfreeBlockMemoryArray(scip, ptr, num)
    Definition: scip_mem.h:110
    SCIPgetMemUsed
    SCIP_Longint SCIPgetMemUsed(SCIP *scip)
    Definition: scip_mem.c:100
    SCIPallocBufferArray
    #define SCIPallocBufferArray(scip, ptr, num)
    Definition: scip_mem.h:124
    SCIPfreeBufferArray
    #define SCIPfreeBufferArray(scip, ptr)
    Definition: scip_mem.h:136
    SCIPallocBlockMemoryArray
    #define SCIPallocBlockMemoryArray(scip, ptr, num)
    Definition: scip_mem.h:93
    SCIPfreeBlockMemory
    #define SCIPfreeBlockMemory(scip, ptr)
    Definition: scip_mem.h:108
    SCIPfreeBufferArrayNull
    #define SCIPfreeBufferArrayNull(scip, ptr)
    Definition: scip_mem.h:137
    SCIPallocBlockMemory
    #define SCIPallocBlockMemory(scip, ptr)
    Definition: scip_mem.h:89
    SCIProwIsIntegral
    SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
    Definition: lp.c:17785
    SCIPgetRowMaxCoef
    SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:1886
    SCIProwGetLhs
    SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
    Definition: lp.c:17686
    SCIPgetRowMinCoef
    SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:1868
    SCIProwIsModifiable
    SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
    Definition: lp.c:17805
    SCIPcacheRowExtensions
    SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:1581
    SCIProwGetParallelism
    SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
    Definition: lp.c:7970
    SCIProwGetCols
    SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
    Definition: lp.c:17632
    SCIPgetRowLPActivity
    SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:1957
    SCIProwGetRhs
    SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
    Definition: lp.c:17696
    SCIProwGetAge
    int SCIProwGetAge(SCIP_ROW *row)
    Definition: lp.c:17765
    SCIProwGetNLPNonz
    int SCIProwGetNLPNonz(SCIP_ROW *row)
    Definition: lp.c:17621
    SCIProwGetNorm
    SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
    Definition: lp.c:17662
    SCIProwGetLPPos
    int SCIProwGetLPPos(SCIP_ROW *row)
    Definition: lp.c:17895
    SCIPflushRowExtensions
    SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:1604
    SCIProwIsLocal
    SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
    Definition: lp.c:17795
    SCIPmakeRowIntegral
    SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
    Definition: scip_lp.c:1790
    SCIPaddVarToRow
    SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
    Definition: scip_lp.c:1646
    SCIPprintRow
    SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
    Definition: scip_lp.c:2176
    SCIProwGetName
    const char * SCIProwGetName(SCIP_ROW *row)
    Definition: lp.c:17745
    SCIProwGetOriginSepa
    SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
    Definition: lp.c:17870
    SCIPreleaseRow
    SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
    Definition: scip_lp.c:1508
    SCIPcreateEmptyRowSepa
    SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
    Definition: scip_lp.c:1429
    SCIProwGetRank
    int SCIProwGetRank(SCIP_ROW *row)
    Definition: lp.c:17775
    SCIProwChgRank
    void SCIProwChgRank(SCIP_ROW *row, int rank)
    Definition: lp.c:17928
    SCIProwGetConstant
    SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
    Definition: lp.c:17652
    SCIProwGetVals
    SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
    Definition: lp.c:17642
    SCIProwGetBasisStatus
    SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
    Definition: lp.c:17734
    SCIPsetSepaExit
    SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
    Definition: scip_sepa.c:205
    SCIPincludeSepaBasic
    SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
    Definition: scip_sepa.c:115
    SCIPsepaGetName
    const char * SCIPsepaGetName(SCIP_SEPA *sepa)
    Definition: sepa.c:746
    SCIPsepaGetNCallsAtNode
    int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
    Definition: sepa.c:893
    SCIPsetSepaFree
    SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
    Definition: scip_sepa.c:173
    SCIPsepaGetData
    SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
    Definition: sepa.c:636
    SCIPsepaSetData
    void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
    Definition: sepa.c:646
    SCIPsetSepaCopy
    SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
    Definition: scip_sepa.c:157
    SCIPsetSepaInit
    SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
    Definition: scip_sepa.c:189
    SCIPgetBestSol
    SCIP_SOL * SCIPgetBestSol(SCIP *scip)
    Definition: scip_sol.c:2986
    SCIPcreateSol
    SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
    Definition: scip_sol.c:514
    SCIPprintSol
    SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
    Definition: scip_sol.c:2351
    SCIPgetNSols
    int SCIPgetNSols(SCIP *scip)
    Definition: scip_sol.c:2887
    SCIPgetSols
    SCIP_SOL ** SCIPgetSols(SCIP *scip)
    Definition: scip_sol.c:2936
    SCIPtrySolFree
    SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
    Definition: scip_sol.c:4114
    SCIPsetSolVal
    SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
    Definition: scip_sol.c:1569
    SCIPgetSolVal
    SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
    Definition: scip_sol.c:1763
    SCIPtransformProb
    SCIP_RETCODE SCIPtransformProb(SCIP *scip)
    Definition: scip_solve.c:232
    SCIPsolve
    SCIP_RETCODE SCIPsolve(SCIP *scip)
    Definition: scip_solve.c:2611
    SCIPgetUpperbound
    SCIP_Real SCIPgetUpperbound(SCIP *scip)
    Definition: scip_solvingstats.c:1734
    SCIPgetNNodes
    SCIP_Longint SCIPgetNNodes(SCIP *scip)
    Definition: scip_solvingstats.c:214
    SCIPgetDualbound
    SCIP_Real SCIPgetDualbound(SCIP *scip)
    Definition: scip_solvingstats.c:1428
    SCIPprintStatistics
    SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
    Definition: scip_solvingstats.c:5951
    SCIPgetLowerbound
    SCIP_Real SCIPgetLowerbound(SCIP *scip)
    Definition: scip_solvingstats.c:1491
    SCIPgetNLPs
    SCIP_Longint SCIPgetNLPs(SCIP *scip)
    Definition: scip_solvingstats.c:457
    SCIPgetNLPIterations
    SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
    Definition: scip_solvingstats.c:503
    SCIPgetFirstLPTime
    SCIP_Real SCIPgetFirstLPTime(SCIP *scip)
    Definition: scip_timing.c:468
    SCIPgetSolvingTime
    SCIP_Real SCIPgetSolvingTime(SCIP *scip)
    Definition: scip_timing.c:378
    SCIPisSumPositive
    SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:747
    SCIPinfinity
    SCIP_Real SCIPinfinity(SCIP *scip)
    Definition: scip_numerics.c:501
    SCIPisGE
    SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:488
    SCIPisIntegral
    SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:585
    SCIPfeasFrac
    SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:932
    SCIPisFeasEQ
    SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:771
    SCIPisPositive
    SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:561
    SCIPfeasCeil
    SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:908
    SCIPisFeasZero
    SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:836
    SCIPfloor
    SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:622
    SCIPfeasFloor
    SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:896
    SCIPisInfinity
    SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:512
    SCIPisFeasLT
    SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:784
    SCIPisFeasNegative
    SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:860
    SCIPisFeasLE
    SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:797
    SCIPisFeasIntegral
    SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:872
    SCIPfrac
    SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:658
    SCIPisGT
    SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:475
    SCIPisNegative
    SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:573
    SCIPisFeasGT
    SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:810
    SCIPisEQ
    SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:436
    SCIPisSumZero
    SCIP_Bool SCIPisSumZero(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:735
    SCIPisZero
    SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:549
    SCIPepsilon
    SCIP_Real SCIPepsilon(SCIP *scip)
    Definition: scip_numerics.c:140
    SCIPsumepsilon
    SCIP_Real SCIPsumepsilon(SCIP *scip)
    Definition: scip_numerics.c:154
    SCIPisLT
    SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:449
    SCIPisFeasPositive
    SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:848
    SCIPvarGetCol
    SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
    Definition: var.c:23715
    SCIPvarGetStatus
    SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
    Definition: var.c:23418
    SCIPvarGetUbLocal
    SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
    Definition: var.c:24300
    SCIPvarGetObj
    SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
    Definition: var.c:23932
    SCIPvarGetUbGlobal
    SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
    Definition: var.c:24174
    SCIPvarGetProbindex
    int SCIPvarGetProbindex(SCIP_VAR *var)
    Definition: var.c:23694
    SCIPreleaseVar
    SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
    Definition: scip_var.c:1887
    SCIPvarIsIntegral
    SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
    Definition: var.c:23522
    SCIPvarGetLPSol
    SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
    Definition: var.c:24696
    SCIPgetVarSol
    SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
    Definition: scip_var.c:3051
    SCIPvarGetLbLocal
    SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
    Definition: var.c:24266
    SCIPcreateVar
    SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
    Definition: scip_var.c:120
    SCIPvarGetLbGlobal
    SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
    Definition: var.c:24152
    SCIPfreeRandom
    void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
    Definition: scip_randnumgen.c:79
    SCIPrandomGetReal
    SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
    Definition: misc.c:10245
    SCIPcreateRandom
    SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
    Definition: scip_randnumgen.c:56
    SCIPincludeSepaCGMIP
    SCIP_RETCODE SCIPincludeSepaCGMIP(SCIP *scip)
    Definition: sepa_cgmip.c:4493
    SCIPsnprintf
    int SCIPsnprintf(char *t, int len, const char *s,...)
    Definition: misc.c:10827
    memory.h
    memory allocation routines
    BMSclearMemoryArray
    #define BMSclearMemoryArray(ptr, num)
    Definition: memory.h:130
    pub_cons.h
    public methods for managing constraints
    pub_lp.h
    public methods for LP management
    pub_message.h
    public methods for message output
    SCIPerrorMessage
    #define SCIPerrorMessage
    Definition: pub_message.h:64
    pub_misc.h
    public data structures and miscellaneous methods
    pub_sepa.h
    public methods for separators
    pub_var.h
    public methods for problem variables
    scip_branch.h
    public methods for branching rule plugins and branching
    scip_cons.h
    public methods for constraint handler plugins and constraints
    scip_copy.h
    public methods for problem copies
    scip_cut.h
    public methods for cuts and aggregation rows
    scip_general.h
    general public methods
    scip_lp.h
    public methods for the LP relaxation, rows and columns
    scip_mem.h
    public methods for memory management
    scip_message.h
    public methods for message handling
    scip_numerics.h
    public methods for numerical tolerances
    scip_param.h
    public methods for SCIP parameter handling
    scip_prob.h
    public methods for global and local (sub)problems
    scip_randnumgen.h
    public methods for random numbers
    scip_sepa.h
    public methods for separator plugins
    scip_sol.h
    public methods for solutions
    scip_solve.h
    public solving methods
    scip_solvingstats.h
    public methods for querying solving statistics
    scip_timing.h
    public methods for timing
    scip_tree.h
    public methods for the branch-and-bound tree
    scip_var.h
    public methods for SCIP variables
    SCIPincludeDefaultPlugins
    SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
    Definition: scipdefplugins.c:37
    scipdefplugins.h
    default SCIP plugins
    DEFAULT_CUTCOEFBND
    #define DEFAULT_CUTCOEFBND
    Definition: sepa_cgmip.c:119
    EPSILONVALUE
    #define EPSILONVALUE
    Definition: sepa_cgmip.c:157
    SEPA_PRIORITY
    #define SEPA_PRIORITY
    Definition: sepa_cgmip.c:107
    DEFAULT_USECUTPOOL
    #define DEFAULT_USECUTPOOL
    Definition: sepa_cgmip.c:140
    DEFAULT_CONSHDLRUSENORM
    #define DEFAULT_CONSHDLRUSENORM
    Definition: sepa_cgmip.c:145
    DEFAULT_ADDVIOLCONSHDLR
    #define DEFAULT_ADDVIOLCONSHDLR
    Definition: sepa_cgmip.c:144
    createSubscip
    static SCIP_RETCODE createSubscip(SCIP *origscip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
    Definition: sepa_cgmip.c:1046
    DEFAULT_INTCONVMIN
    #define DEFAULT_INTCONVMIN
    Definition: sepa_cgmip.c:131
    BOUNDSWITCH
    #define BOUNDSWITCH
    Definition: sepa_cgmip.c:166
    SEPA_DELAY
    #define SEPA_DELAY
    Definition: sepa_cgmip.c:111
    DEFAULT_ADDVIOLATIONCONS
    #define DEFAULT_ADDVIOLATIONCONS
    Definition: sepa_cgmip.c:143
    createCGCutCMIR
    static SCIP_RETCODE createCGCutCMIR(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
    Definition: sepa_cgmip.c:3483
    CONSHDLR_DESC
    #define CONSHDLR_DESC
    Definition: sepa_cgmip.c:282
    solveSubscip
    static SCIP_RETCODE solveSubscip(SCIP *origscip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success)
    Definition: sepa_cgmip.c:2443
    DEFAULT_OBJWEIGHT
    #define DEFAULT_OBJWEIGHT
    Definition: sepa_cgmip.c:134
    DEFAULT_SKIPMULTBOUNDS
    #define DEFAULT_SKIPMULTBOUNDS
    Definition: sepa_cgmip.c:132
    MAXFRAC
    #define MAXFRAC
    Definition: sepa_cgmip.c:171
    NROWSTOOSMALL
    #define NROWSTOOSMALL
    Definition: sepa_cgmip.c:154
    DEFAULT_DYNAMICCUTS
    #define DEFAULT_DYNAMICCUTS
    Definition: sepa_cgmip.c:136
    DEFAULT_MINNODELIMIT
    #define DEFAULT_MINNODELIMIT
    Definition: sepa_cgmip.c:120
    DEFAULT_CONTCONVERT
    #define DEFAULT_CONTCONVERT
    Definition: sepa_cgmip.c:126
    computeCut
    static SCIP_RETCODE computeCut(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Bool usefrac, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, SCIP_Bool *localrowsused, SCIP_Bool *localboundsused, int *cutrank, SCIP_Bool *success)
    Definition: sepa_cgmip.c:2743
    DEFAULT_USEOBJLB
    #define DEFAULT_USEOBJLB
    Definition: sepa_cgmip.c:147
    POSTPROCESS
    #define POSTPROCESS
    Definition: sepa_cgmip.c:169
    SEPA_DESC
    #define SEPA_DESC
    Definition: sepa_cgmip.c:106
    createCGCutDirect
    static SCIP_RETCODE createCGCutDirect(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
    Definition: sepa_cgmip.c:3260
    SCIP_DECL_SEPACOPY
    static SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
    Definition: sepa_cgmip.c:4278
    SCIP_DECL_CONSENFOLP
    static SCIP_DECL_CONSENFOLP(consEnfolpViolatedCuts)
    Definition: sepa_cgmip.c:525
    CGMIP_ColType
    CGMIP_ColType
    Definition: sepa_cgmip.c:228
    colConverted
    @ colConverted
    Definition: sepa_cgmip.c:231
    colContinuous
    @ colContinuous
    Definition: sepa_cgmip.c:230
    colPresent
    @ colPresent
    Definition: sepa_cgmip.c:229
    colAtUb
    @ colAtUb
    Definition: sepa_cgmip.c:232
    colAtLb
    @ colAtLb
    Definition: sepa_cgmip.c:233
    MAKECONTINTEGRAL
    #define MAKECONTINTEGRAL
    Definition: sepa_cgmip.c:173
    NCOLSTOOSMALL
    #define NCOLSTOOSMALL
    Definition: sepa_cgmip.c:155
    DEFAULT_ONLYINTVARS
    #define DEFAULT_ONLYINTVARS
    Definition: sepa_cgmip.c:125
    DEFAULT_DECISIONTREE
    #define DEFAULT_DECISIONTREE
    Definition: sepa_cgmip.c:116
    DEFAULT_MAXROUNDSROOT
    #define DEFAULT_MAXROUNDSROOT
    Definition: sepa_cgmip.c:114
    SEPA_USESSUBSCIP
    #define SEPA_USESSUBSCIP
    Definition: sepa_cgmip.c:110
    DEFAULT_GENPRIMALSOLS
    #define DEFAULT_GENPRIMALSOLS
    Definition: sepa_cgmip.c:151
    DEFAULT_MAXDEPTH
    #define DEFAULT_MAXDEPTH
    Definition: sepa_cgmip.c:115
    SCIP_DECL_SEPAINIT
    static SCIP_DECL_SEPAINIT(sepaInitCGMIP)
    Definition: sepa_cgmip.c:4249
    computeObjWeightSize
    static SCIP_Real computeObjWeightSize(int rowsize, int minrowsize, int maxrowsize)
    Definition: sepa_cgmip.c:888
    createCGCutStrongCG
    static SCIP_RETCODE createCGCutStrongCG(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
    Definition: sepa_cgmip.c:3773
    DEFAULT_ONLYRANKONE
    #define DEFAULT_ONLYRANKONE
    Definition: sepa_cgmip.c:124
    VARTYPEUSEVBDS
    #define VARTYPEUSEVBDS
    Definition: sepa_cgmip.c:167
    DEFAULT_INTCONVERT
    #define DEFAULT_INTCONVERT
    Definition: sepa_cgmip.c:129
    FIXINTEGRALRHS
    #define FIXINTEGRALRHS
    Definition: sepa_cgmip.c:172
    DEFAULT_CMIROWNBOUNDS
    #define DEFAULT_CMIROWNBOUNDS
    Definition: sepa_cgmip.c:139
    DEFAULT_OUTPUT
    #define DEFAULT_OUTPUT
    Definition: sepa_cgmip.c:149
    DEFAULT_OBJLONE
    #define DEFAULT_OBJLONE
    Definition: sepa_cgmip.c:133
    SCIP_DECL_CONSLOCK
    static SCIP_DECL_CONSLOCK(consLockViolatedCuts)
    Definition: sepa_cgmip.c:592
    createCGMIPprimalsols
    static SCIP_RETCODE createCGMIPprimalsols(SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
    Definition: sepa_cgmip.c:2194
    DEFAULT_EARLYTERM
    #define DEFAULT_EARLYTERM
    Definition: sepa_cgmip.c:142
    CONSHDLRFULLNORM
    #define CONSHDLRFULLNORM
    Definition: sepa_cgmip.c:160
    CGMIP_MIPDATA
    struct CGMIP_MIPData CGMIP_MIPDATA
    Definition: sepa_cgmip.c:273
    SCIPincludeConshdlrViolatedCut
    static SCIP_RETCODE SCIPincludeConshdlrViolatedCut(SCIP *scip, CGMIP_MIPDATA *mipdata)
    Definition: sepa_cgmip.c:601
    DEFAULT_PRIMALSEPARATION
    #define DEFAULT_PRIMALSEPARATION
    Definition: sepa_cgmip.c:141
    freeSubscip
    static SCIP_RETCODE freeSubscip(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata)
    Definition: sepa_cgmip.c:4158
    SEPA_MAXBOUNDDIST
    #define SEPA_MAXBOUNDDIST
    Definition: sepa_cgmip.c:109
    DEFAULT_CONTCONVMIN
    #define DEFAULT_CONTCONVMIN
    Definition: sepa_cgmip.c:128
    MAXNSOLS
    #define MAXNSOLS
    Definition: sepa_cgmip.c:162
    BETAEPSILONVALUE
    #define BETAEPSILONVALUE
    Definition: sepa_cgmip.c:158
    SCIP_DECL_CONSENFOPS
    static SCIP_DECL_CONSENFOPS(consEnfopsViolatedCuts)
    Definition: sepa_cgmip.c:552
    SEPA_FREQ
    #define SEPA_FREQ
    Definition: sepa_cgmip.c:108
    MAXWEIGHTRANGE
    #define MAXWEIGHTRANGE
    Definition: sepa_cgmip.c:174
    SCIP_DECL_SEPAEXECLP
    static SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
    Definition: sepa_cgmip.c:4317
    SCIP_DECL_SEPAEXIT
    static SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
    Definition: sepa_cgmip.c:4264
    MINFRAC
    #define MINFRAC
    Definition: sepa_cgmip.c:170
    DEFAULT_USEOBJUB
    #define DEFAULT_USEOBJUB
    Definition: sepa_cgmip.c:146
    DEFAULT_RANDSEED
    #define DEFAULT_RANDSEED
    Definition: sepa_cgmip.c:150
    MAXAGGRLEN
    #define MAXAGGRLEN(nvars)
    Definition: sepa_cgmip.c:178
    DEFAULT_OBJWEIGHTSIZE
    #define DEFAULT_OBJWEIGHTSIZE
    Definition: sepa_cgmip.c:135
    SCIP_DECL_CONSCHECK
    static SCIP_DECL_CONSCHECK(consCheckViolatedCuts)
    Definition: sepa_cgmip.c:566
    storeCutInArrays
    static SCIP_RETCODE storeCutInArrays(SCIP *scip, int nvars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, int *cutinds, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
    Definition: sepa_cgmip.c:637
    SEPA_NAME
    #define SEPA_NAME
    Definition: sepa_cgmip.c:105
    SCIP_DECL_CONSFREE
    static SCIP_DECL_CONSFREE(consFreeViolatedCuts)
    Definition: sepa_cgmip.c:508
    transformColumn
    static SCIP_RETCODE transformColumn(SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_COL *col, SCIP_Real offset, SCIP_Real sigma, SCIP_Real *lhs, SCIP_Real *rhs, SCIP_Real *lb, SCIP_Real *ub, SCIP_Real *primsol)
    Definition: sepa_cgmip.c:777
    DEFAULT_ONLYACTIVEROWS
    #define DEFAULT_ONLYACTIVEROWS
    Definition: sepa_cgmip.c:122
    subscipSetParams
    static SCIP_RETCODE subscipSetParams(SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
    Definition: sepa_cgmip.c:2050
    AWAY
    #define AWAY
    Definition: sepa_cgmip.c:175
    DEFAULT_MAXROUNDS
    #define DEFAULT_MAXROUNDS
    Definition: sepa_cgmip.c:113
    DEFAULT_MEMORYLIMIT
    #define DEFAULT_MEMORYLIMIT
    Definition: sepa_cgmip.c:118
    DEFAULT_MAXROWAGE
    #define DEFAULT_MAXROWAGE
    Definition: sepa_cgmip.c:123
    DEFAULT_USECMIR
    #define DEFAULT_USECMIR
    Definition: sepa_cgmip.c:137
    OBJWEIGHTRANGE
    #define OBJWEIGHTRANGE
    Definition: sepa_cgmip.c:163
    CONSHDLR_NAME
    #define CONSHDLR_NAME
    Definition: sepa_cgmip.c:281
    solCutIsViolated
    static SCIP_RETCODE solCutIsViolated(SCIP *scip, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Bool *violated)
    Definition: sepa_cgmip.c:309
    DEFAULT_SUBSCIPFAST
    #define DEFAULT_SUBSCIPFAST
    Definition: sepa_cgmip.c:148
    MINEFFICACY
    #define MINEFFICACY
    Definition: sepa_cgmip.c:161
    STALLNODELIMIT
    #define STALLNODELIMIT
    Definition: sepa_cgmip.c:159
    DEFAULT_MAXNODELIMIT
    #define DEFAULT_MAXNODELIMIT
    Definition: sepa_cgmip.c:121
    DEFAULT_CONTCONVFRAC
    #define DEFAULT_CONTCONVFRAC
    Definition: sepa_cgmip.c:127
    createCGCuts
    static SCIP_RETCODE createCGCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *cutoff, unsigned int *ngen)
    Definition: sepa_cgmip.c:4004
    DEFAULT_INTCONVFRAC
    #define DEFAULT_INTCONVFRAC
    Definition: sepa_cgmip.c:130
    CGMIP_COLTYPE
    enum CGMIP_ColType CGMIP_COLTYPE
    Definition: sepa_cgmip.c:235
    SCIP_DECL_SEPAFREE
    static SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
    Definition: sepa_cgmip.c:4294
    DEFAULT_TIMELIMIT
    #define DEFAULT_TIMELIMIT
    Definition: sepa_cgmip.c:117
    DEFAULT_USESTRONGCG
    #define DEFAULT_USESTRONGCG
    Definition: sepa_cgmip.c:138
    sepa_cgmip.h
    Chvatal-Gomory cuts computed via a sub-MIP.
    separate
    static SCIP_RETCODE separate(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
    Main separation function.
    Definition: sepa_flower.c:1219
    SCIP_AggrRow
    Definition: struct_cuts.h:43
    SCIP_Col
    Definition: struct_lp.h:138
    SCIP_Cons
    Definition: struct_cons.h:47
    SCIP_Conshdlr
    Definition: struct_cons.h:128
    SCIP_RandNumGen
    Definition: struct_misc.h:270
    SCIP_Row
    Definition: struct_lp.h:205
    SCIP_Sepa
    Definition: struct_sepa.h:47
    SCIP_Sol
    Definition: struct_sol.h:74
    SCIP_Var
    Definition: struct_var.h:262
    SCIP_CONSHDLRDATA
    struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
    Definition: type_cons.h:64
    SCIP_BOUNDTYPE_UPPER
    @ SCIP_BOUNDTYPE_UPPER
    Definition: type_lp.h:58
    SCIP_BOUNDTYPE_LOWER
    @ SCIP_BOUNDTYPE_LOWER
    Definition: type_lp.h:57
    SCIP_BOUNDTYPE
    enum SCIP_BoundType SCIP_BOUNDTYPE
    Definition: type_lp.h:60
    SCIP_LPSOLSTAT_OPTIMAL
    @ SCIP_LPSOLSTAT_OPTIMAL
    Definition: type_lp.h:44
    SCIP_BASESTAT_UPPER
    @ SCIP_BASESTAT_UPPER
    Definition: type_lpi.h:93
    SCIP_BASESTAT_LOWER
    @ SCIP_BASESTAT_LOWER
    Definition: type_lpi.h:91
    SCIP_BASESTAT
    enum SCIP_BaseStat SCIP_BASESTAT
    Definition: type_lpi.h:96
    SCIP_VERBLEVEL_NORMAL
    @ SCIP_VERBLEVEL_NORMAL
    Definition: type_message.h:60
    SCIP_PARAMSETTING_FAST
    @ SCIP_PARAMSETTING_FAST
    Definition: type_paramset.h:62
    SCIP_PARAMEMPHASIS_FEASIBILITY
    @ SCIP_PARAMEMPHASIS_FEASIBILITY
    Definition: type_paramset.h:74
    SCIP_OBJSENSE_MAXIMIZE
    @ SCIP_OBJSENSE_MAXIMIZE
    Definition: type_prob.h:47
    SCIP_DIDNOTRUN
    @ SCIP_DIDNOTRUN
    Definition: type_result.h:42
    SCIP_CUTOFF
    @ SCIP_CUTOFF
    Definition: type_result.h:48
    SCIP_FEASIBLE
    @ SCIP_FEASIBLE
    Definition: type_result.h:45
    SCIP_DIDNOTFIND
    @ SCIP_DIDNOTFIND
    Definition: type_result.h:44
    SCIP_SEPARATED
    @ SCIP_SEPARATED
    Definition: type_result.h:49
    SCIP_INFEASIBLE
    @ SCIP_INFEASIBLE
    Definition: type_result.h:46
    SCIP_INVALIDDATA
    @ SCIP_INVALIDDATA
    Definition: type_retcode.h:52
    SCIP_OKAY
    @ SCIP_OKAY
    Definition: type_retcode.h:42
    SCIP_INVALIDCALL
    @ SCIP_INVALIDCALL
    Definition: type_retcode.h:51
    SCIP_ERROR
    @ SCIP_ERROR
    Definition: type_retcode.h:43
    SCIP_RETCODE
    enum SCIP_Retcode SCIP_RETCODE
    Definition: type_retcode.h:63
    SCIP_SEPADATA
    struct SCIP_SepaData SCIP_SEPADATA
    Definition: type_sepa.h:52
    SCIP_STAGE_SOLVED
    @ SCIP_STAGE_SOLVED
    Definition: type_set.h:54
    SCIP_STAGE_SOLVING
    @ SCIP_STAGE_SOLVING
    Definition: type_set.h:53
    SCIP_STAGE
    enum SCIP_Stage SCIP_STAGE
    Definition: type_set.h:59
    SCIP_STATUS_OPTIMAL
    @ SCIP_STATUS_OPTIMAL
    Definition: type_stat.h:43
    SCIP_STATUS_BESTSOLLIMIT
    @ SCIP_STATUS_BESTSOLLIMIT
    Definition: type_stat.h:60
    SCIP_STATUS_USERINTERRUPT
    @ SCIP_STATUS_USERINTERRUPT
    Definition: type_stat.h:47
    SCIP_STATUS_INFORUNBD
    @ SCIP_STATUS_INFORUNBD
    Definition: type_stat.h:46
    SCIP_STATUS_STALLNODELIMIT
    @ SCIP_STATUS_STALLNODELIMIT
    Definition: type_stat.h:52
    SCIP_STATUS_TIMELIMIT
    @ SCIP_STATUS_TIMELIMIT
    Definition: type_stat.h:54
    SCIP_STATUS_INFEASIBLE
    @ SCIP_STATUS_INFEASIBLE
    Definition: type_stat.h:44
    SCIP_STATUS_NODELIMIT
    @ SCIP_STATUS_NODELIMIT
    Definition: type_stat.h:49
    SCIP_STATUS_MEMLIMIT
    @ SCIP_STATUS_MEMLIMIT
    Definition: type_stat.h:55
    SCIP_STATUS
    enum SCIP_Status SCIP_STATUS
    Definition: type_stat.h:64
    SCIP_VARTYPE_INTEGER
    @ SCIP_VARTYPE_INTEGER
    Definition: type_var.h:65
    SCIP_VARTYPE_CONTINUOUS
    @ SCIP_VARTYPE_CONTINUOUS
    Definition: type_var.h:71
    SCIP_VARSTATUS_COLUMN
    @ SCIP_VARSTATUS_COLUMN
    Definition: type_var.h:53