Scippy

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