Scippy

    SCIP

    Solving Constraint Integer Programs

    sepa_lagromory.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
    25/**@file sepa_lagromory.c
    26 * @ingroup DEFPLUGINS_SEPA
    27 * @brief Lagromory separator
    28 * @author Suresh Bolusani
    29 * @author Mark Ruben Turner
    30 * @author Mathieu Besançon
    31 *
    32 * This separator is based on the following article that discusses Lagromory separation using the relax-and-cut
    33 * framework. Multiple enhancements have been implemented on top of the basic algorithm described in the article.
    34 *
    35 * Fischetti M. and Salvagnin D. (2011).@n
    36 * A relax-and-cut framework for Gomory mixed-integer cuts.@n
    37 * Mathematical Programming Computation, 3, 79-102.
    38 *
    39 * Consider the following linear relaxation at a node:
    40 *
    41 * \f[
    42 * \begin{array}{rrl}
    43 * \min & c^T x &\\
    44 * & x & \in P,
    45 * \end{array}
    46 * \f]
    47 *
    48 * where \f$P\f$ is the feasible region of the relaxation. Let the following be the cuts generated so far in the current
    49 * separation round.
    50 *
    51 * \f[
    52 * {\alpha^i}^T x \leq \alpha^i_0, i = 1, 2, \ldots, M
    53 * \f]
    54 *
    55 * Then, the following is the Lagrangian dual problem considered in the relax-and-cut framework used in the separator.
    56 *
    57 * \f[
    58 * z_D := \max\limits_{u \geq 0} \left\{L(u) := \min \left\{c^T x + \sum\limits_{i = 1}^{M} \left(u_i
    59 * \left({\alpha^i}^T x - \alpha^i_0\right) \right) \mid x \in P\right\} \right\},
    60 * \f]
    61 *
    62 * where \f$u\f$ are the Lagrangian multipliers (referred to as \a dualvector in this separator) used for penalizing the
    63 * violation of the generated cuts, and \f$z_D\f$ is the optimal objective value (which is approximated via \a ubparam in this separator).
    64 * Then, the following are the steps of the relax-and-cut algorithm implemented in this separator.
    65 *
    66 * - Generate an initial pool of cuts to build the initial Lagrangian dual problem.
    67 * - Select initial values for Lagrangian multipliers \f$u^0\f$ (e.g., all zeroes vector).
    68 * - In the outer main loop \f$i\f$ of the algorithm:
    69 * 1. Solve the Lagrangian dual problem until certain termination criterion is met. This results in an inner
    70 * subgradient loop, whose iteration \f$j\f$ is described below.
    71 * 1. Fix \f$u^j\f$, and solve the LP corresponding to the Lagrangian dual with fixed multipliers.
    72 * Gather its optimal simplex tableau and optimal objective value (i.e., the Lagrangian value)
    73 * \f$L(u^j)\f$.
    74 * 2. Update \f$u^j\f$ to \f$u^{j+1}\f$ as follows.
    75 * \f[
    76 * u^{j+1} = \left(u^j + \lambda_j s^k\right)_+,
    77 * \f]
    78 * where \f$\lambda_j\f$ is the step length:
    79 * \f[
    80 * \lambda_j = \frac{\mu_j (UB - L(u^j))}{\|s^j\|^2_2},
    81 * \f]
    82 * where \f$mu_j\f$ is a factor (i.e., \a muparam) such that \f$0 < \mu_j \leq 2\f$, UB is \p ubparam,
    83 * and \f$s^j\f$ is the subgradient vector defined as:
    84 * \f[
    85 * s^j_k = \left({\alpha^k}^T x - \alpha^k_0\right), k = 1, 2, \ldots, M.
    86 * \f]
    87 * The factor \f$mu_j\f$ is updated as below.
    88 * \f[
    89 * mu_j = \begin{cases}
    90 * mubacktrackfactor * mu_j & \text{if } L(u^j) < bestLB - \delta\\
    91 * \begin{cases}
    92 * muslab1factor * mu_j & \text{if } bestLB - avgLB < deltaslab1ub * delta\\
    93 * muslab2factor * mu_j & \text{if } deltaslab1ub * \delta \leq bestLB - avgLB < deltaslab2ub * delta\\
    94 * muslab3factor * mu_j & \text{otherwise}
    95 * \end{cases} & \text{otherwise},
    96 * \end{cases}
    97 * \f]
    98 * where \f$bestLB\f$ and \f$avgLB\f$ are best and average Lagrangian values found so far, and
    99 * \f$\delta = UB - bestLB\f$.
    100 * 3. Stabilize \f$u^{j+1}\f$ by projecting onto a norm ball followed by taking a convex combination
    101 * with a core vector of Lagrangian multipliers.
    102 * 4. Generate GMI cuts based on the optimal simplex tableau.
    103 * 5. Relax the newly generated cuts by penalizing and adding them to the objective function.
    104 * 6. Go to the next iteration \f$j+1\f$.
    105 * 2. Gather all the generated cuts and build an LP by adding all these cuts to the node relaxation.
    106 * 3. Solve this LP to obtain its optimal primal and dual solutions.
    107 * 4. If this primal solution is MIP primal feasible, then add this solution to the solution pool, add all
    108 * the generated cuts to the cutpool or sepastore as needed, and exit the separator.
    109 * 5. Otherwise, update the Lagrangian multipliers based on this optimal dual solution, and go to the next
    110 * iteration \f$i+1\f$.
    111 *
    112 * @todo store all LP sols in a data structure, and send them to fix-and-propagate at the end.
    113 *
    114 * @todo test heuristics such as feasibility pump with multiple input solutions.
    115 *
    116 * @todo find dual degenerate problems and test the separator on these problems.
    117 *
    118 * @todo identify instance classes where these cuts work better.
    119 *
    120 * @todo add termination criteria based on failed efforts.
    121 *
    122 * @todo for warm starting, if there are additional rows/cols, set their basis status to non-basic and then set WS info.
    123 *
    124 * @todo filter cuts using multiple explored LP solutions.
    125 *
    126 * @todo for bases on optimal face only, aggregate to get a new basis and separate it.
    127 *
    128 * @todo generate other separators in addition to GMI cuts (0-1/2).
    129 *
    130 * @todo convert iters from int to SCIP_Longint.
    131 */
    132
    133/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    134
    135#include "scip/heur_trysol.h"
    136#include "scip/sepa_lagromory.h"
    137
    138#define SEPA_NAME "lagromory"
    139#define SEPA_DESC "separator for Lagromory cuts for MIP relaxations"
    140#define SEPA_PRIORITY -8000
    141#define SEPA_FREQ -1
    142#define SEPA_MAXBOUNDDIST 1.0
    143#define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
    144#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
    145
    146/* generic parameters */
    147#define DEFAULT_AWAY 0.01 /**< minimal integrality violation of a basis variable to try separation */
    148#define DEFAULT_DELAYEDCUTS FALSE /**< should cuts be added to the delayed cut pool? */
    149#define DEFAULT_SEPARATEROWS TRUE /**< separate rows with integral slack? */
    150#define DEFAULT_SORTCUTOFFSOL TRUE /**< sort fractional integer columns based on fractionality? */
    151#define DEFAULT_SIDETYPEBASIS TRUE /**< choose side types of row (lhs/rhs) based on basis information? */
    152#define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
    153#define DEFAULT_MAKEINTEGRAL FALSE /**< try to scale all cuts to integral coefficients? */
    154#define DEFAULT_FORCECUTS FALSE /**< force cuts to be added to the LP? */
    155#define DEFAULT_ALLOWLOCAL FALSE /**< should locally valid cuts be generated? */
    156
    157/* parameters related to the separator's termination check */
    158#define DEFAULT_MAXROUNDSROOT 1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
    159#define DEFAULT_MAXROUNDS 1 /**< maximal number of separation rounds per node (-1: unlimited) */
    160#define DEFAULT_DUALDEGENERACYRATETHRESHOLD 0.5 /**< minimum dual degeneracy rate for separator execution */
    161#define DEFAULT_VARCONSRATIOTHRESHOLD 1.0 /**< minimum variable-constraint ratio on optimal face for separator execution */
    162#define DEFAULT_MINRESTART 1 /**< minimum restart round for separator execution (0: from beginning of the
    163 * instance solving, >= n with n >= 1: from restart round n) */
    164#define DEFAULT_PERLPMAXCUTSROOT 50 /**< maximal number of cuts separated per Lagromory LP in the root node */
    165#define DEFAULT_PERLPMAXCUTS 10 /**< maximal number of cuts separated per Lagromory LP in the non-root node */
    166#define DEFAULT_PERROUNDLPITERLIMITFACTOR -1.0 /**< factor w.r.t. root node LP iterations for maximal separating LP iterations
    167 * per separation round (negative for no limit) */
    168#define DEFAULT_ROOTLPITERLIMITFACTOR -1.0 /**< factor w.r.t. root node LP iterations for maximal separating LP iterations
    169 * in the root node (negative for no limit) */
    170#define DEFAULT_TOTALLPITERLIMITFACTOR -1.0 /**< factor w.r.t. root node LP iterations for maximal separating LP iterations
    171 * in the tree (negative for no limit) */
    172#define DEFAULT_PERROUNDMAXLPITERS 50000 /**< maximal number of separating LP iterations per separation round (-1: unlimited) */
    173#define DEFAULT_PERROUNDCUTSFACTORROOT 1.0 /**< factor w.r.t. number of integer columns for number of cuts separated per
    174 * separation round in root node */
    175#define DEFAULT_PERROUNDCUTSFACTOR 0.5 /**< factor w.r.t. number of integer columns for number of cuts separated per
    176 * separation round at a non-root node */
    177#define DEFAULT_TOTALCUTSFACTOR 50.0 /**< factor w.r.t. number of integer columns for total number of cuts separated */
    178#define DEFAULT_MAXMAINITERS 4 /**< maximal number of main loop iterations of the relax-and-cut algorithm */
    179#define DEFAULT_MAXSUBGRADIENTITERS 6 /**< maximal number of subgradient loop iterations of the relax-and-cut algorithm */
    180
    181/* parameters related to the relax-and-cut algorithm */
    182#define DEFAULT_MUPARAMCONST TRUE /**< is the mu parameter (factor for step length) constant? */
    183#define DEFAULT_MUPARAMINIT 0.01 /**< initial value of the mu parameter (factor for step length) */
    184#define DEFAULT_MUPARAMLB 0.0 /**< lower bound for the mu parameter (factor for step length) */
    185#define DEFAULT_MUPARAMUB 2.0 /**< upper bound for the mu parameter (factor for step length) */
    186#define DEFAULT_MUBACKTRACKFACTOR 0.5 /**< factor of mu while backtracking the mu parameter (factor for step length) -
    187 * see updateMuSteplengthParam() */
    188#define DEFAULT_MUSLAB1FACTOR 10.0 /**< factor of mu parameter (factor for step length) for larger increment - see
    189 * updateMuSteplengthParam() */
    190#define DEFAULT_MUSLAB2FACTOR 2.0 /**< factor of mu parameter (factor for step length) for smaller increment - see
    191 * updateMuSteplengthParam() */
    192#define DEFAULT_MUSLAB3FACTOR 0.5 /**< factor of mu parameter (factor for step length) for reduction - see
    193 * updateMuSteplengthParam() */
    194#define DEFAULT_DELTASLAB1UB 0.001 /**< factor of delta deciding larger increment of mu parameter (factor for step
    195 * length) - see updateMuSteplengthParam() */
    196#define DEFAULT_DELTASLAB2UB 0.01 /**< factor of delta deciding smaller increment of mu parameter (factor for step
    197 * length) - see updateMuSteplengthParam() */
    198#define DEFAULT_UBPARAMPOSFACTOR 2.0 /**< factor for positive upper bound used as an estimate for the optimal
    199 * Lagrangian dual value */
    200#define DEFAULT_UBPARAMNEGFACTOR 0.5 /**< factor for negative upper bound used as an estimate for the optimal
    201 * Lagrangian dual value */
    202#define DEFAULT_MAXLAGRANGIANVALSFORAVG 2 /**< maximal number of iterations for rolling average of Lagrangian value */
    203#define DEFAULT_MAXCONSECITERSFORMUUPDATE 10 /**< consecutive number of iterations used to determine if mu needs to be backtracked */
    204#define DEFAULT_PERROOTLPITERFACTOR 0.2 /**< factor w.r.t. root node LP iterations for iteration limit of each separating
    205 * LP (negative for no limit) */
    206#define DEFAULT_PERLPITERFACTOR 0.1 /**< factor w.r.t. non-root node LP iterations for iteration limit of each
    207 * separating LP (negative for no limit) */
    208#define DEFAULT_CUTGENFREQ 1 /**< frequency of subgradient iterations for generating cuts */
    209#define DEFAULT_CUTADDFREQ 1 /**< frequency of subgradient iterations for adding cuts to objective function */
    210#define DEFAULT_CUTSFILTERFACTOR 1.0 /**< fraction of generated cuts per explored basis to accept from separator */
    211#define DEFAULT_OPTIMALFACEPRIORITY 2 /**< priority of the optimal face for separator execution (0: low priority, 1:
    212 * medium priority, 2: high priority) */
    213#define DEFAULT_AGGREGATECUTS TRUE /**< aggregate all generated cuts using the Lagrangian multipliers? */
    214
    215/* parameters for stabilization of the Lagrangian multipliers */
    216#define DEFAULT_PROJECTIONTYPE 2 /**< the ball into which the Lagrangian multipliers are projected for
    217 * stabilization (0: no projection, 1: L1-norm ball projection, 2: L2-norm ball
    218 * projection, 3: L_inf-norm ball projection) */
    219#define DEFAULT_STABILITYCENTERTYPE 1 /**< type of stability center for taking weighted average of Lagrangian multipliers for
    220 * stabilization (0: no weighted stabilization, 1: best Lagrangian multipliers) */
    221#define DEFAULT_RADIUSINIT 0.5 /**< initial radius of the ball used in stabilization of Lagrangian multipliers */
    222#define DEFAULT_RADIUSMAX 20.0 /**< maximum radius of the ball used in stabilization of Lagrangian multipliers */
    223#define DEFAULT_RADIUSMIN 1e-6 /**< minimum radius of the ball used in stabilization of Lagrangian multipliers */
    224#define DEFAULT_CONST 2.0 /**< a constant for stablity center based stabilization of Lagrangian multipliers */
    225#define DEFAULT_RADIUSUPDATEWEIGHT 0.98 /**< multiplier to evaluate cut violation score used for updating ball radius */
    226
    227/* macros that are used directly */
    228#define RANDSEED 42 /**< random seed */
    229#define MAKECONTINTEGRAL FALSE /**< convert continuous variable to integral variables in SCIPmakeRowIntegral()? */
    230#define POSTPROCESS TRUE /**< apply postprocessing after MIR calculation? - see SCIPcalcMIR() */
    231#define BOUNDSWITCH 0.9999 /**< threshold for bound switching - see SCIPcalcMIR() */
    232#define VARTYPEUSEVBDS 2 /**< We allow variable bound substitution for variables with continuous vartype only.
    233 * See SCIPcalcMIR() for more information. */
    234#define FIXINTEGRALRHS FALSE /**< try to generate an integral rhs? - see SCIPcalcMIR() */
    235#define MAXAGGRLEN(ncols) (0.1*(ncols)+1000) /**< maximal length of base inequality */
    236
    237/*
    238 * Data structures
    239 */
    240
    241/** separator data */
    242struct SCIP_SepaData
    243{
    244 /* generic variables */
    245 SCIP_Real away; /**< minimal integrality violation of a basis variable to try separation */
    246 SCIP_Bool delayedcuts; /**< should cuts be added to the delayed cut pool? */
    247 SCIP_Bool separaterows; /**< separate rows with integral slack? */
    248 SCIP_Bool sortcutoffsol; /**< sort fractional integer columns based on fractionality? */
    249 SCIP_Bool sidetypebasis; /**< choose side types of row (lhs/rhs) based on basis information? */
    250 SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
    251 SCIP_Bool makeintegral; /**< try to scale all cuts to integral coefficients? */
    252 SCIP_Bool forcecuts; /**< force cuts to be added to the LP? */
    253 SCIP_Bool allowlocal; /**< should locally valid cuts be generated? */
    254 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
    255 SCIP_HEUR* heurtrysol; /**< a pointer to the trysol heuristic, if available */
    256
    257 /* used to define separating LPs */
    258 SCIP_LPI* lpiwithsoftcuts; /**< pointer to the lpi interface of Lagrangian dual with fixed multipliers */
    259 SCIP_LPI* lpiwithhardcuts; /**< pointer to the lpi interface of LP with all generated cuts */
    260 int nrowsinhardcutslp; /**< nrows of \a lpiwithhardcuts */
    261 int nrunsinsoftcutslp; /**< number of branch-and-bound runs on current instance */
    262
    263 /* used for termination checks */
    264 SCIP_Longint ncalls; /**< number of calls to the separator */
    265 int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
    266 int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
    267 SCIP_Real dualdegeneracyratethreshold; /**< minimum dual degeneracy rate for separator execution */
    268 SCIP_Real varconsratiothreshold; /**< minimum variable-constraint ratio on optimal face for separator execution */
    269 int minrestart; /**< minimum restart round for separator execution (0: from beginning of the instance
    270 * solving, >= n with n >= 1: from restart round n) */
    271 int nmaxcutsperlproot; /**< maximal number of cuts separated per Lagromory LP in the root node */
    272 int nmaxcutsperlp; /**< maximal number of cuts separated per Lagromory LP in the non-root node */
    273 SCIP_Real perroundlpiterlimitfactor; /**< factor w.r.t. root node LP iterations for maximal separating LP iterations per
    274 * separation round (negative for no limit) */
    275 SCIP_Real rootlpiterlimitfactor; /**< factor w.r.t. root node LP iterations for maximal separating LP iterations in the
    276 * root node (negative for no limit) */
    277 SCIP_Real totallpiterlimitfactor; /**< factor w.r.t. root node LP iterations for maximal separating LP iterations in the
    278 * tree (negative for no limit) */
    279 int perroundnmaxlpiters; /**< maximal number of separating LP iterations per separation round (-1: unlimited) */
    280 SCIP_Real perroundcutsfactorroot; /**< factor w.r.t. number of integer columns for number of cuts separated per
    281 * separation round in root node */
    282 SCIP_Real perroundcutsfactor; /**< factor w.r.t. number of integer columns for number of cuts separated per
    283 * separation round at a non-root node */
    284 SCIP_Real totalcutsfactor; /**< factor w.r.t. number of integer columns for total number of cuts separated */
    285 int nmaxmainiters; /**< maximal number of main loop iterations of the relax-and-cut algorithm */
    286 int nmaxsubgradientiters; /**< maximal number of subgradient loop iterations of the relax-and-cut algorithm */
    287 int nmaxperroundlpiters; /**< maximal number of separating LP iterations per separation round */
    288 int nmaxrootlpiters; /**< maximal number of separating LP iterations in the root node */
    289 int nrootlpiters; /**< number of separating LP iterations in the root node */
    290 int nmaxtotallpiters; /**< maximal number of separating LP iterations in the tree */
    291 int ntotallpiters; /**< number of separating LP iterations in the tree */
    292 int nmaxperroundcutsroot; /**< maximal number of cuts separated per separation round in root node */
    293 int nmaxperroundcuts; /**< maximal number of cuts separated per separation round */
    294 int nmaxtotalcuts; /**< maximal number of cuts separated in the tree */
    295 int ntotalcuts; /**< number of cuts separated in the tree */
    296
    297 /* used for the relax-and-cut algorithm */
    298 SCIP_Bool muparamconst; /**< is the mu parameter (factor for step length) constant? */
    299 SCIP_Real muparaminit; /**< initial value of the mu parameter (factor for step length) */
    300 SCIP_Real muparamlb; /**< lower bound for the mu parameter (factor for step length) */
    301 SCIP_Real muparamub; /**< upper bound for the mu parameter (factor for step length) */
    302 SCIP_Real mubacktrackfactor; /**< factor of mu while backtracking the mu parameter (factor for step length) - see
    303 * updateMuSteplengthParam() */
    304 SCIP_Real muslab1factor; /**< factor of mu parameter (factor for step length) for larger increment - see
    305 * updateMuSteplengthParam() */
    306 SCIP_Real muslab2factor; /**< factor of mu parameter (factor for step length) for smaller increment - see
    307 * updateMuSteplengthParam() */
    308 SCIP_Real muslab3factor; /**< factor of mu parameter (factor for step length) for reduction - see updateMuSteplengthParam() */
    309 SCIP_Real deltaslab1ub; /**< factor of delta deciding larger increment of mu parameter (factor for step
    310 * length) - see updateMuSteplengthParam() */
    311 SCIP_Real deltaslab2ub; /**< factor of delta deciding smaller increment of mu parameter (factor for step
    312 * length) - see updateMuSteplengthParam() */
    313 SCIP_Real ubparamposfactor; /**< factor for positive upper bound used as an estimate for the optimal Lagrangian
    314 * dual value */
    315 SCIP_Real ubparamnegfactor; /**< factor for negative upper bound used as an estimate for the optimal Lagrangian
    316 * dual value */
    317 int nmaxlagrangianvalsforavg; /**< maximal number of iterations for rolling average of Lagrangian value */
    318 int nmaxconsecitersformuupdate; /**< consecutive number of iterations used to determine if mu needs to be backtracked */
    319 SCIP_Real perrootlpiterfactor; /**< factor w.r.t. root node LP iterations for iteration limit of each separating LP
    320 * (negative for no limit) */
    321 SCIP_Real perlpiterfactor; /**< factor w.r.t. non-root node LP iterations for iteration limit of each separating
    322 * LP (negative for no limit) */
    323 int cutgenfreq; /**< frequency of subgradient iterations for generating cuts */
    324 int cutaddfreq; /**< frequency of subgradient iterations for adding cuts to objective function */
    325 SCIP_Real cutsfilterfactor; /**< fraction of generated cuts per explored basis to accept from separator */
    326 int optimalfacepriority; /**< priority of the optimal face for separator execution (0: low priority, 1: medium
    327 * priority, 2: high priority) */
    328 SCIP_Bool aggregatecuts; /**< aggregate all generated cuts using the Lagrangian multipliers? */
    329
    330 /* for stabilization of Lagrangian multipliers */
    331 int projectiontype; /**< the ball into which the Lagrangian multipliers are projected for stabilization
    332 * (0: no projection, 1: L1-norm ball projection, 2: L2-norm ball projection, 3:
    333 * L_inf-norm ball projection) */
    334 int stabilitycentertype; /**< type of stability center for taking weighted average of Lagrangian multipliers for
    335 * stabilization (0: no weighted stabilization, 1: best Lagrangian multipliers) */
    336 SCIP_Real radiusinit; /**< initial radius of the ball used in stabilization of Lagrangian multipliers */
    337 SCIP_Real radiusmax; /**< maximum radius of the ball used in stabilization of Lagrangian multipliers */
    338 SCIP_Real radiusmin; /**< minimum radius of the ball used in stabilization of Lagrangian multipliers */
    339 SCIP_Real constant; /**< a constant for stablity center based stabilization of Lagrangian multipliers */
    340 SCIP_Real radiusupdateweight; /**< multiplier to evaluate cut violation score used for updating ball radius */
    341};
    342
    343
    344/*
    345 * Local methods
    346 */
    347
    348/** start the diving mode for solving LPs corresponding to the Lagrangian dual with fixed multipliers in the subgradient
    349 * loop of the separator, and update some sepadata values */
    350static
    351SCIP_RETCODE createLPWithSoftCuts(
    352 SCIP* scip, /**< SCIP data structure */
    353 SCIP_SEPADATA* sepadata /**< separator data structure */
    354 )
    355{
    356 SCIP_ROW** rows;
    357 SCIP_COL** cols;
    358 int nruns;
    359 int runnum;
    360 int nrows;
    361 int ncols;
    362 unsigned int nintcols;
    363 SCIP_Longint nrootlpiters;
    364 int i;
    365
    366 assert(scip != NULL);
    367 assert(sepadata != NULL);
    368
    369 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    370 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
    371 runnum = SCIPgetNRuns(scip); /* current run number of SCIP (starts from 1) indicating restarts */
    372 nruns = sepadata->nrunsinsoftcutslp; /* previous run number of SCIP in which the diving LP was created */
    373 nintcols = 0;
    374
    375 /* start diving mode so that the diving LP can be used for all subgradient iterations */
    376 SCIP_CALL( SCIPstartDive(scip) );
    377
    378 /* store LPI pointer to be able to use LPI functions directly (e.g., setting time limit) */
    379 SCIP_CALL( SCIPgetLPI(scip, &(sepadata->lpiwithsoftcuts)) );
    380
    381 /* if called for the first time in a restart (including the initial run), set certain sepadata values */
    382 if( nruns != runnum )
    383 {
    384 /* get number of LP iterations of root node's first LP solving */
    385 nrootlpiters = SCIPgetNRootFirstLPIterations(scip);
    386
    387 /* calculate maximum number of LP iterations allowed for all separation calls in the root node */
    388 if( (sepadata->rootlpiterlimitfactor >= 0.0) && !SCIPisInfinity(scip, sepadata->rootlpiterlimitfactor) )
    389 sepadata->nmaxrootlpiters = (int)(sepadata->rootlpiterlimitfactor * nrootlpiters);
    390 else
    391 sepadata->nmaxrootlpiters = -1; /* no finite limit */
    392
    393 /* calculate maximum number of LP iterations allowed for all separation calls in the entire tree */
    394 if( (sepadata->totallpiterlimitfactor >= 0.0) && !SCIPisInfinity(scip, sepadata->totallpiterlimitfactor) )
    395 sepadata->nmaxtotallpiters = (int)(sepadata->totallpiterlimitfactor * nrootlpiters);
    396 else
    397 sepadata->nmaxtotallpiters = -1; /* no finite limit */
    398
    399 /* calculate maximum number of LP iterations allowed per separation call */
    400 if( (sepadata->perroundlpiterlimitfactor >= 0.0) && !SCIPisInfinity(scip, sepadata->perroundlpiterlimitfactor) )
    401 sepadata->nmaxperroundlpiters = (int)(sepadata->perroundlpiterlimitfactor * nrootlpiters);
    402 else
    403 sepadata->nmaxperroundlpiters = -1; /* no finite limit */
    404
    405 /* update maximum number of LP iterations allowed per separation call using absolute limits */
    406 if( sepadata->perroundnmaxlpiters > 0 )
    407 sepadata->nmaxperroundlpiters = ((sepadata->nmaxperroundlpiters >= 0) ? MIN(sepadata->nmaxperroundlpiters,
    408 sepadata->perroundnmaxlpiters) : sepadata->perroundnmaxlpiters);
    409
    410 /* set maximum number of cuts allowed to generate per round in root and non-root nodes as well as the total tree */
    411 for( i = 0; i < ncols; ++i )
    412 nintcols += SCIPcolIsIntegral(cols[i]);
    413
    414 sepadata->nmaxperroundcutsroot = (int)(sepadata->perroundcutsfactorroot * nintcols);
    415 sepadata->nmaxperroundcuts = (int)(sepadata->perroundcutsfactor * nintcols);
    416
    417 if( sepadata->ncalls == 0 )
    418 {
    419 sepadata->nmaxtotalcuts = (int)(sepadata->totalcutsfactor * nintcols);
    420 sepadata->ntotalcuts = 0;
    421 }
    422
    423 /* update the run number of solving to represent the restart number in which the above limits were set */
    424 sepadata->nrunsinsoftcutslp = runnum;
    425 }
    426
    427 return SCIP_OKAY;
    428}
    429
    430/** end the diving mode that was used for solving LPs corresponding to the Lagrangian dual with fixed multipliers */
    431static
    432SCIP_RETCODE deleteLPWithSoftCuts(
    433 SCIP* scip, /**< SCIP data structure */
    434 SCIP_SEPADATA* sepadata /**< separator data structure */
    435 )
    436{
    437 assert(scip != NULL);
    438 assert(sepadata != NULL);
    439
    440 SCIP_CALL( SCIPendDive(scip) );
    441
    442 return SCIP_OKAY;
    443}
    444
    445/** set up LP interface to solve LPs in the (outer) main loop of the relax-and-cut algorithm; these LPs are built by
    446 * adding all the generated cuts to the node relaxation */
    447/* @todo add lpi iters to global statistics */
    448static
    449SCIP_RETCODE createLPWithHardCuts(
    450 SCIP* scip, /**< SCIP data structure */
    451 SCIP_SEPADATA* sepadata, /**< separator data structure */
    452 SCIP_ROW** cuts, /**< generated cuts to be added to the LP */
    453 int ncuts /**< number of generated cuts to be added to the LP */
    454 )
    455{
    456 SCIP_ROW** rows;
    457 SCIP_COL** cols;
    458 SCIP_Real* collb;
    459 SCIP_Real* colub;
    460 SCIP_Real* colobj;
    461 SCIP_Real* rowlhs;
    462 SCIP_Real* rowrhs;
    463 SCIP_Real rowconst;
    464 SCIP_Real* rowvals;
    465 SCIP_Real* rowval;
    466 SCIP_COL** rowcols;
    467 SCIP_LPI* wslpi;
    468 SCIP_LPISTATE* lpistate;
    469 BMS_BLKMEM* blkmem;
    470 SCIP_Real pinf;
    471 SCIP_Real ninf;
    472 int nrows;
    473 int ncols;
    474 int nrownonz;
    475 int collppos;
    476 int* rowcolinds;
    477 int* rowbegs;
    478 int i;
    479 int j;
    480
    481 assert(scip != NULL);
    482 assert(sepadata != NULL);
    483
    484 SCIP_LPI** lpi = &(sepadata->lpiwithhardcuts);
    485 blkmem = SCIPblkmem(scip);
    486
    487 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    488 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
    489
    490 /* if this function is called for the first time in this separation round, then create an LPI and add cols & rows */
    491 if( ncuts == 0 )
    492 {
    493 if( *lpi != NULL )
    494 {
    495 SCIP_CALL( SCIPlpiFree(lpi) );
    496 *lpi = NULL;
    497 }
    498 assert(*lpi == NULL);
    499
    500 /* create an LPI */
    501 SCIP_CALL( SCIPlpiCreate(lpi, SCIPgetMessagehdlr(scip), "node LP with generated cuts", SCIP_OBJSEN_MINIMIZE) );
    502
    503 /* add cols to the LP interface */
    504 SCIP_CALL( SCIPallocBufferArray(scip, &colobj, ncols) );
    505 SCIP_CALL( SCIPallocBufferArray(scip, &collb, ncols) );
    506 SCIP_CALL( SCIPallocBufferArray(scip, &colub, ncols) );
    507
    508 /* gather required column information */
    509 for( i = 0; i < ncols; ++i )
    510 {
    511 colobj[i] = SCIPcolGetObj(cols[i]);
    512 collb[i] = SCIPcolGetLb(cols[i]);
    513 colub[i] = SCIPcolGetUb(cols[i]);
    514 }
    515 /* add cols */
    516 SCIP_CALL( SCIPlpiAddCols(*lpi, ncols, colobj, collb, colub, NULL, 0, NULL, NULL, NULL) );
    517 SCIPfreeBufferArray(scip, &colub);
    518 SCIPfreeBufferArray(scip, &collb);
    519 SCIPfreeBufferArray(scip, &colobj);
    520
    521 /* add rows to the LP interface */
    522 /* find number of nonzeroes in rows */
    523 nrownonz = 0;
    524 for( i = 0; i < nrows; ++i )
    525 {
    526 assert(!(SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) && SCIPisInfinity(scip, SCIProwGetRhs(rows[i]))));
    527 nrownonz += SCIProwGetNLPNonz(rows[i]);
    528 }
    529 SCIP_CALL( SCIPallocBufferArray(scip, &rowcolinds, nrownonz) );
    530 SCIP_CALL( SCIPallocBufferArray(scip, &rowvals, nrownonz) );
    531 SCIP_CALL( SCIPallocBufferArray(scip, &rowbegs, nrows + 1) );
    532 SCIP_CALL( SCIPallocBufferArray(scip, &rowlhs, nrows) );
    533 SCIP_CALL( SCIPallocBufferArray(scip, &rowrhs, nrows) );
    534
    535 /* gather required row information */
    536 rowbegs[0] = 0;
    537 pinf = SCIPlpiInfinity(*lpi);
    538 ninf = -SCIPlpiInfinity(*lpi);
    539 for( i = 0; i < nrows; ++i )
    540 {
    541 nrownonz = SCIProwGetNLPNonz(rows[i]);
    542 assert(nrownonz <= ncols);
    543 rowval = SCIProwGetVals(rows[i]);
    544 rowcols = SCIProwGetCols(rows[i]);
    545
    546 rowbegs[i + 1] = rowbegs[i] + nrownonz;
    547 rowconst = SCIProwGetConstant(rows[i]);
    548 rowlhs[i] = SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) ? ninf : SCIProwGetLhs(rows[i]) - rowconst;
    549 rowrhs[i] = SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) ? pinf : SCIProwGetRhs(rows[i]) - rowconst;
    550
    551 for( j = 0; j < nrownonz; ++j )
    552 {
    553 collppos = SCIPcolGetLPPos(rowcols[j]);
    554 assert(collppos >= 0);
    555 assert(collppos <= ncols);
    556
    557 rowcolinds[rowbegs[i] + j] = collppos;
    558 rowvals[rowbegs[i] + j] = rowval[j];
    559 }
    560 }
    561
    562 /* add rows */
    563 SCIP_CALL( SCIPlpiAddRows(*lpi, nrows, rowlhs, rowrhs, NULL, rowbegs[nrows], rowbegs, rowcolinds, rowvals) );
    564
    565 /* get warm starting info */
    566 SCIP_CALL( SCIPgetLPI(scip, &wslpi) );
    567 SCIP_CALL( SCIPlpiGetState(wslpi, blkmem, &lpistate) );
    568 }
    569 /* if there are any cuts, then add the cuts that were not added earlier to the LPI */
    570 else
    571 {
    572 assert(nrows + ncuts >= sepadata->nrowsinhardcutslp);
    573
    574 /* get warm starting info */
    575 wslpi = *lpi;
    576 SCIP_CALL( SCIPlpiGetState(wslpi, blkmem, &lpistate) );
    577
    578 /* find number of nonzeros in cuts and allocate memory */
    579 nrownonz = 0;
    580 pinf = SCIPlpiInfinity(*lpi);
    581 ninf = -SCIPlpiInfinity(*lpi);
    582
    583 for( i = sepadata->nrowsinhardcutslp - nrows; i < ncuts; ++i )
    584 {
    585 assert(!(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])) && SCIPisInfinity(scip, SCIProwGetRhs(cuts[i]))));
    586 assert(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])));
    587 assert(!SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])));
    588 nrownonz += SCIProwGetNNonz(cuts[i]);
    589 }
    590 SCIP_CALL( SCIPallocBufferArray(scip, &rowcolinds, nrownonz) );
    591 SCIP_CALL( SCIPallocBufferArray(scip, &rowvals, nrownonz) );
    592 SCIP_CALL( SCIPallocBufferArray(scip, &rowbegs, (ncuts - sepadata->nrowsinhardcutslp + nrows) + 1) );
    593 SCIP_CALL( SCIPallocBufferArray(scip, &rowlhs, (ncuts - sepadata->nrowsinhardcutslp + nrows)) );
    594 SCIP_CALL( SCIPallocBufferArray(scip, &rowrhs, (ncuts - sepadata->nrowsinhardcutslp + nrows)) );
    595
    596 /* gather required cut information */
    597 rowbegs[0] = 0;
    598 for( i = sepadata->nrowsinhardcutslp - nrows; i < ncuts; ++i )
    599 {
    600 nrownonz = SCIProwGetNNonz(cuts[i]);
    601 assert(nrownonz <= ncols);
    602 rowval = SCIProwGetVals(cuts[i]);
    603 rowcols = SCIProwGetCols(cuts[i]);
    604
    605 rowbegs[i - sepadata->nrowsinhardcutslp + nrows + 1] = rowbegs[i - sepadata->nrowsinhardcutslp + nrows] +
    606 nrownonz;
    607 rowconst = SCIProwGetConstant(cuts[i]);
    608 rowlhs[i - sepadata->nrowsinhardcutslp + nrows] = SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])) ? ninf :
    609 SCIProwGetLhs(cuts[i]) - rowconst;
    610 rowrhs[i - sepadata->nrowsinhardcutslp + nrows] = SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])) ? pinf :
    611 SCIProwGetRhs(cuts[i]) - rowconst;
    612
    613 for( j = 0; j < nrownonz; ++j )
    614 {
    615 collppos = SCIPcolGetLPPos(rowcols[j]);
    616 assert(collppos >= 0);
    617 assert(collppos <= ncols);
    618
    619 rowcolinds[rowbegs[i - sepadata->nrowsinhardcutslp + nrows] + j] = collppos;
    620 rowvals[rowbegs[i - sepadata->nrowsinhardcutslp + nrows] + j] = rowval[j];
    621 }
    622 }
    623
    624 /* add cuts */
    625 SCIP_CALL( SCIPlpiAddRows(*lpi, (ncuts - sepadata->nrowsinhardcutslp + nrows), rowlhs, rowrhs, NULL,
    626 rowbegs[(ncuts - sepadata->nrowsinhardcutslp + nrows)], rowbegs, rowcolinds, rowvals) );
    627 }
    628
    629 /* set warm starting basis */
    630 SCIP_CALL( SCIPlpiSetState(*lpi, blkmem, lpistate) );
    631
    632 /* reset remaining sepadata values */
    633 sepadata->nrowsinhardcutslp = nrows + ncuts;
    634
    635 /* free memory */
    636 SCIP_CALL( SCIPlpiFreeState(*lpi, blkmem, &lpistate) );
    637 SCIPfreeBufferArray(scip, &rowrhs);
    638 SCIPfreeBufferArray(scip, &rowlhs);
    639 SCIPfreeBufferArray(scip, &rowbegs);
    640 SCIPfreeBufferArray(scip, &rowvals);
    641 SCIPfreeBufferArray(scip, &rowcolinds);
    642
    643 return SCIP_OKAY;
    644}
    645
    646/** free separator data */
    647static
    648SCIP_RETCODE sepadataFree(
    649 SCIP* scip, /**< SCIP data structure */
    650 SCIP_SEPADATA** sepadata /**< separator data structure */
    651 )
    652{
    653 assert(scip != NULL);
    654 assert(sepadata != NULL);
    655 assert(*sepadata != NULL);
    656
    657 if( (*sepadata)->lpiwithhardcuts != NULL )
    658 {
    659 SCIP_CALL( SCIPlpiFree(&((*sepadata)->lpiwithhardcuts)) );
    660 }
    661
    662 (*sepadata)->nrowsinhardcutslp = 0;
    663 (*sepadata)->nrunsinsoftcutslp = 0;
    664 (*sepadata)->ncalls = 0;
    665 (*sepadata)->nmaxperroundlpiters = 0;
    666 (*sepadata)->nmaxrootlpiters = 0;
    667 (*sepadata)->nrootlpiters = 0;
    668 (*sepadata)->nmaxtotallpiters = 0;
    669 (*sepadata)->ntotallpiters = 0;
    670 (*sepadata)->nmaxperroundcutsroot = 0;
    671 (*sepadata)->nmaxperroundcuts = 0;
    672 (*sepadata)->nmaxtotalcuts = 0;
    673 (*sepadata)->ntotalcuts = 0;
    674
    675 SCIPfreeBlockMemory(scip, sepadata);
    676
    677 return SCIP_OKAY;
    678}
    679
    680/** update mu parameter which is used as a factor in the step length calculation; refer to the top of the file for a
    681 * description of the formula. */
    682/* @todo some adaptive strategy like constant after certain changes? */
    683static
    684SCIP_RETCODE updateMuSteplengthParam(
    685 SCIP* scip, /**< SCIP data structure */
    686 SCIP_SEPADATA* sepadata, /**< separator data structure */
    687 int subgradientiternum, /**< subgradient iteration number */
    688 SCIP_Real ubparam, /**< estimate of the optimal Lagrangian dual value */
    689 SCIP_Real* lagrangianvals, /**< vector of Lagrangian values found so far */
    690 SCIP_Real bestlagrangianval, /**< best Lagrangian value found so far */
    691 SCIP_Real avglagrangianval, /**< rolling average of the Lagrangian values found so far */
    692 SCIP_Real* muparam, /**< mu parameter to be updated */
    693 SCIP_Bool* backtrack /**< whether mu parameter has been backtracked */
    694 )
    695{
    696 SCIP_Real delta;
    697 SCIP_Real deltaslab1ub;
    698 SCIP_Real deltaslab2ub;
    699 SCIP_Real muslab1factor;
    700 SCIP_Real muslab2factor;
    701 SCIP_Real muslab3factor;
    702 int maxiters;
    703 int i;
    704
    705 assert( backtrack != NULL );
    706
    707 *backtrack = FALSE;
    708
    709 /* update the mu parameter only if it is not set to be a constant value */
    710 if( !sepadata->muparamconst )
    711 {
    712 delta = ubparam - bestlagrangianval;
    713 deltaslab1ub = MIN(sepadata->deltaslab1ub, sepadata->deltaslab2ub);
    714 deltaslab2ub = MAX(sepadata->deltaslab1ub, sepadata->deltaslab2ub);
    715
    716 /* ensure that the ordering of different user input parameters is as expected */
    717 if( SCIPisPositive(scip, sepadata->muslab1factor - sepadata->muslab2factor) )
    718 {
    719 if( SCIPisPositive(scip, sepadata->muslab2factor - sepadata->muslab3factor) )
    720 {
    721 muslab1factor = sepadata->muslab1factor;
    722 muslab2factor = sepadata->muslab2factor;
    723 muslab3factor = sepadata->muslab3factor;
    724 }
    725 else
    726 {
    727 if( SCIPisPositive(scip, sepadata->muslab1factor - sepadata->muslab3factor) )
    728 {
    729 muslab1factor = sepadata->muslab1factor;
    730 muslab2factor = sepadata->muslab3factor;
    731 muslab3factor = sepadata->muslab2factor;
    732 }
    733 else
    734 {
    735 muslab1factor = sepadata->muslab3factor;
    736 muslab2factor = sepadata->muslab1factor;
    737 muslab3factor = sepadata->muslab2factor;
    738 }
    739 }
    740 }
    741 else
    742 {
    743 if( SCIPisPositive(scip, sepadata->muslab1factor - sepadata->muslab3factor) )
    744 {
    745 muslab1factor = sepadata->muslab2factor;
    746 muslab2factor = sepadata->muslab1factor;
    747 muslab3factor = sepadata->muslab3factor;
    748 }
    749 else
    750 {
    751 if( SCIPisPositive(scip, sepadata->muslab2factor - sepadata->muslab3factor) )
    752 {
    753 muslab1factor = sepadata->muslab2factor;
    754 muslab2factor = sepadata->muslab3factor;
    755 muslab3factor = sepadata->muslab1factor;
    756 }
    757 else
    758 {
    759 muslab1factor = sepadata->muslab3factor;
    760 muslab2factor = sepadata->muslab2factor;
    761 muslab3factor = sepadata->muslab1factor;
    762 }
    763 }
    764 }
    765
    766 maxiters = MIN(sepadata->nmaxconsecitersformuupdate, sepadata->nmaxlagrangianvalsforavg);
    767 i = -1;
    768
    769 /* if certain number of iterations are done, then check for a possibility of backtracking and apply accordingly */
    770 if( subgradientiternum >= maxiters )
    771 {
    772 for( i = subgradientiternum - maxiters; i < subgradientiternum; i++ )
    773 {
    774 if( SCIPisGE(scip, lagrangianvals[i], bestlagrangianval - delta) )
    775 break;
    776 }
    777
    778 if( i == subgradientiternum )
    779 {
    780 *muparam *= sepadata->mubacktrackfactor;
    781 *backtrack = TRUE;
    782 }
    783 }
    784
    785 /* update mu parameter based on the different between best and average Lagrangian values */
    786 if( (subgradientiternum < maxiters) || (i >= 0 && i < subgradientiternum) )
    787 {
    788 if( bestlagrangianval - avglagrangianval < deltaslab1ub * delta )
    789 *muparam *= muslab1factor;
    790 else if( bestlagrangianval - avglagrangianval < deltaslab2ub * delta )
    791 *muparam *= muslab2factor;
    792 else
    793 *muparam *= muslab3factor;
    794 }
    795
    796 /* reset the mu parameter to within its bounds */
    797 *muparam = MAX(*muparam, sepadata->muparamlb);
    798 *muparam = MIN(*muparam, sepadata->muparamub);
    799 }
    800
    801 return SCIP_OKAY;
    802}
    803
    804/** update subgradient, i.e., residuals of generated cuts
    805 * @note assuming that \f$i^{th}\f$ cut is of the form \f${\alpha^i}^T x \leq {\alpha^i_0}\f$.
    806 */
    807static
    808void updateSubgradient(
    809 SCIP* scip, /**< SCIP data structure */
    810 SCIP_SOL* sol, /**< LP solution used in updating subgradient vector */
    811 SCIP_ROW** cuts, /**< cuts generated so far */
    812 int ncuts, /**< number of cuts generated so far */
    813 SCIP_Real* subgradient, /**< vector of subgradients to be updated */
    814 SCIP_Real* dualvector, /**< Lagrangian multipliers */
    815 SCIP_Bool* subgradientzero, /**< whether the subgradient vector is all zero */
    816 int* ncutviols, /**< number of violations of generated cuts */
    817 SCIP_Real* maxcutviol, /**< maximum violation of generated cuts */
    818 int* nnzsubgradientdualprod, /**< number of nonzero products of subgradient vector and Lagrangian multipliers (i.e.,
    819 * number of complementarity slackness violations) */
    820 SCIP_Real* maxnzsubgradientdualprod /**< maximum value of nonzero products of subgradient vector and Lagrangian multipliers
    821 * (i.e., maximum value of complementarity slackness violations) */
    822 )
    823{
    824 int nzerosubgradient;
    825 SCIP_Real term;
    826 int i;
    827
    828 assert(subgradientzero != NULL);
    829 assert(ncutviols != NULL);
    830 assert(maxcutviol != NULL);
    831 assert(nnzsubgradientdualprod != NULL);
    832 assert(maxnzsubgradientdualprod != NULL);
    833
    834 *ncutviols = 0;
    835 *maxcutviol = 0.0;
    836 *nnzsubgradientdualprod = 0;
    837 *maxnzsubgradientdualprod = 0.0;
    838 nzerosubgradient = 0;
    839 *subgradientzero = FALSE;
    840
    841 /* for each cut, calculate the residual along with various violation metrics */
    842 for( i = 0; i < ncuts; i++ )
    843 {
    844 assert(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])));
    845 assert(!SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])));
    846 subgradient[i] = SCIPgetRowSolActivity(scip, cuts[i], sol) + SCIProwGetConstant(cuts[i]) - SCIProwGetRhs(cuts[i]);
    847
    848 if( SCIPisFeasZero(scip, subgradient[i]) )
    849 {
    850 subgradient[i] = 0.0;
    851 nzerosubgradient++;
    852 }
    853 else
    854 {
    855 /* check for cut violation */
    856 if( SCIPisFeasPositive(scip, subgradient[i]) )
    857 {
    858 (*ncutviols)++;
    859 *maxcutviol = MAX(*maxcutviol, subgradient[i]);
    860 }
    861
    862 /* check for violation of complementarity slackness associated with the cut */
    863 if( !SCIPisZero(scip, subgradient[i] * dualvector[i]) )
    864 {
    865 (*nnzsubgradientdualprod)++;
    866 term = REALABS(subgradient[i] * dualvector[i]);
    867 *maxnzsubgradientdualprod = MAX(*maxnzsubgradientdualprod, term);
    868 }
    869 }
    870 }
    871
    872 /* indicator for all zero subgradient vector */
    873 if( nzerosubgradient == ncuts )
    874 *subgradientzero = TRUE;
    875}
    876
    877/** update Lagrangian value, i.e., optimal value of the Lagrangian dual with fixed multipliers */
    878static
    879void updateLagrangianValue(
    880 SCIP* scip, /**< SCIP data structure */
    881 SCIP_Real objval, /**< objective value of the Lagrangian dual with fixed multipliers */
    882 SCIP_Real* dualvector, /**< Lagrangian multipliers */
    883 SCIP_ROW** cuts, /**< cuts generated so far */
    884 int ncuts, /**< number of cuts generated so far */
    885 SCIP_Real* lagrangianval /**< Lagrangian value to be updated */
    886 )
    887{
    888 int i;
    889
    890 assert(lagrangianval != NULL);
    891
    892 *lagrangianval = objval;
    893
    894 for( i = 0; i < ncuts; i++ )
    895 {
    896 assert(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])));
    897 assert(!SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])));
    898 *lagrangianval += dualvector[i] * (SCIProwGetConstant(cuts[i]) - SCIProwGetRhs(cuts[i]));
    899 }
    900}
    901
    902/** update step length based on various input arguments; refer to the top of the file for an expression */
    903static
    904void updateStepLength(
    905 SCIP* scip, /**< SCIP data structure */
    906 SCIP_Real muparam, /**< mu parameter used as a factor for step length */
    907 SCIP_Real ubparam, /**< estimate of the optimal Lagrangian dual value */
    908 SCIP_Real lagrangianval, /**< Lagrangian value */
    909 SCIP_Real* subgradient, /**< subgradient vector */
    910 int ncuts, /**< number of cuts generated so far */
    911 SCIP_Real* steplength /**< step length to be updated */
    912 )
    913{
    914 SCIP_Real normsquared = 0.0;
    915 int i;
    916
    917 for( i = 0; i < ncuts; i++ )
    918 normsquared += SQR(subgradient[i]);
    919
    920 if( !SCIPisFeasZero(scip, normsquared) )
    921 *steplength = (muparam * (ubparam - lagrangianval))/(normsquared); /*lint !e795*/
    922}
    923
    924/** update the ball radius (based on various violation metrics) that is used for stabilization of Lagrangian multipliers */
    925static
    926void updateBallRadius(
    927 SCIP* scip, /**< SCIP data structure */
    928 SCIP_SEPADATA* sepadata, /**< separator data structure */
    929 SCIP_Real maxviolscore, /**< weighted average of maximum value of generated cut violations and maximum value of
    930 * complementarity slackness violations, in the current iteration */
    931 SCIP_Real maxviolscoreold, /**< weighted average of maximum value of generated cut violations and maximum value of
    932 * complementarity slackness violations, in the previous iteration */
    933 SCIP_Real nviolscore, /**< weighted average of number of generated cut violations and number of complementarity
    934 * slackness violations, in the current iteration */
    935 SCIP_Real nviolscoreold, /**< weighted average of number of generated cut violations and number of complementarity
    936 * slackness violations, in the previous iteration */
    937 int nlpiters, /**< number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in
    938 * current iteration */
    939 SCIP_Real* ballradius /**< norm ball radius to be updated */
    940 )
    941{
    942 SCIP_Bool maxviolscoreimproved;
    943 SCIP_Bool nviolscoreimproved;
    944
    945 assert(ballradius != NULL);
    946
    947 maxviolscoreimproved = !SCIPisNegative(scip, maxviolscoreold - maxviolscore);
    948 nviolscoreimproved = !SCIPisNegative(scip, nviolscoreold - nviolscore);
    949
    950 if( maxviolscoreimproved && nviolscoreimproved )
    951 {
    952 /* both the maximum violation and number of violations scores have become better, so, increase the radius */
    953 if( sepadata->optimalfacepriority <= 1 )
    954 {
    955 *ballradius *= 2.0;
    956 *ballradius = MIN(*ballradius, sepadata->radiusmax);
    957 }
    958 else
    959 {
    960 *ballradius *= 1.5;
    961 *ballradius = MIN(*ballradius, sepadata->radiusmax/2.0);
    962 }
    963 }
    964 else if( !maxviolscoreimproved && !nviolscoreimproved )
    965 {
    966 /* both the maximum violation and number of violations scores have become worse, so, decrease the radius */
    967 *ballradius *= 0.5;
    968 *ballradius = MAX(*ballradius, sepadata->radiusmin);
    969 }
    970 else if( nlpiters == 0 )
    971 {
    972 /* only one among the maximum violation and number of violations scores has become better, and the LP basis did
    973 * not change (i.e., nlpters = 0), so, increase the radius slightly */
    974 if( sepadata->optimalfacepriority <= 1 )
    975 {
    976 *ballradius *= 1.5;
    977 *ballradius = MIN(*ballradius, sepadata->radiusmax);
    978 }
    979 else
    980 {
    981 *ballradius *= 1.2;
    982 *ballradius = MIN(*ballradius, sepadata->radiusmax/2.0);
    983 }
    984 }
    985}
    986
    987/** projection of Lagrangian multipliers onto L1-norm ball. This algorithm is based on the following article
    988 *
    989 * Condat L. (2016).@n
    990 * Fast projection onto the simplex and the \f$l_1\f$ ball.@n
    991 * Mathematical Programming, 158, 1-2, 575-585.
    992 *
    993 */
    994static
    995SCIP_RETCODE l1BallProjection(
    996 SCIP* scip, /**< SCIP data structure */
    997 SCIP_Real* dualvector, /**< Lagrangian multipliers to be projected onto L1-norm vall */
    998 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
    999 SCIP_Real radius /**< radius of the L1-norm ball */
    1000 )
    1001{
    1002 SCIP_Real* temp1vals;
    1003 SCIP_Real* temp2vals;
    1004 SCIP_Real pivotparam;
    1005 SCIP_Real val;
    1006 SCIP_Real term;
    1007 SCIP_Bool temp1changed;
    1008 int ntemp1removed;
    1009 int* temp1inds;
    1010 int* temp2inds;
    1011 int temp1len;
    1012 int temp2len;
    1013 int i;
    1014 int j;
    1015
    1016 assert(!SCIPisNegative(scip, radius));
    1017 val = REALABS(dualvector[0]);
    1018
    1019 /* calculate the L1-norm of the Lagrangian multipliers */
    1020 for( i = 1; i < dualvectorlen; i++ )
    1021 val += REALABS(dualvector[i]);
    1022
    1023 /* if the vector of Lagrangian multipliers lies outside the L1-norm ball, then do the projection */
    1024 if( SCIPisGT(scip, val, radius) )
    1025 {
    1026 SCIP_CALL( SCIPallocCleanBufferArray(scip, &temp1vals, dualvectorlen) );
    1027 SCIP_CALL( SCIPallocCleanBufferArray(scip, &temp2vals, dualvectorlen) );
    1028 SCIP_CALL( SCIPallocBufferArray(scip, &temp1inds, dualvectorlen) );
    1029 SCIP_CALL( SCIPallocBufferArray(scip, &temp2inds, dualvectorlen) );
    1030 for( i = 0; i < dualvectorlen; i++ )
    1031 {
    1032 temp1inds[i] = -1;
    1033 temp2inds[i] = -1;
    1034 }
    1035 temp2len = 0;
    1036
    1037 temp1vals[0] = REALABS(dualvector[0]);
    1038 temp1inds[0] = 0;
    1039 temp1len = 1;
    1040 pivotparam = REALABS(dualvector[0]) - radius;
    1041
    1042 for( i = 1; i < dualvectorlen; i++ )
    1043 {
    1044 if( SCIPisGT(scip, REALABS(dualvector[i]), pivotparam) )
    1045 {
    1046 pivotparam += ((REALABS(dualvector[i]) - pivotparam) / (temp1len + 1));
    1047 if( SCIPisGT(scip, pivotparam, REALABS(dualvector[i]) - radius) )
    1048 {
    1049 temp1vals[temp1len] = REALABS(dualvector[i]);
    1050 temp1inds[temp1len] = i;
    1051 temp1len++;
    1052 }
    1053 else
    1054 {
    1055 for( j = 0; j < temp1len; j++ )
    1056 {
    1057 temp2vals[temp2len + j] = temp1vals[j];
    1058 temp2inds[temp2len + j] = temp1inds[j];
    1059 }
    1060 temp2len += temp1len;
    1061 temp1vals[0] = REALABS(dualvector[i]);
    1062 temp1inds[0] = i;
    1063 temp1len = 1;
    1064 pivotparam = REALABS(dualvector[i]) - radius;
    1065 }
    1066 }
    1067 }
    1068
    1069 for( i = 0; i < temp2len; i++ )
    1070 {
    1071 if( SCIPisGT(scip, temp2vals[i], pivotparam) )
    1072 {
    1073 temp1vals[temp1len] = temp2vals[i];
    1074 temp1inds[temp1len] = temp2inds[i];
    1075 temp1len++;
    1076 pivotparam += ((temp2vals[i] - pivotparam) / temp1len);
    1077 }
    1078 }
    1079
    1080 temp1changed = TRUE;
    1081 ntemp1removed = 0;
    1082 while( temp1changed )
    1083 {
    1084 temp1changed = FALSE;
    1085
    1086 for( i = 0; i < temp1len; i++ )
    1087 {
    1088 /* @note the third condition (temp1len - ntemp1removed > 0) is true as long as the first condition
    1089 * (temp1inds[i] >= 0) is true.
    1090 */
    1091 if( (temp1inds[i] >= 0) && SCIPisLE(scip, temp1vals[i], pivotparam) )
    1092 {
    1093 temp1inds[i] = -1;
    1094 temp1changed = TRUE;
    1095 ntemp1removed++;
    1096 assert(temp1len - ntemp1removed > 0);
    1097 /* coverity[divide_by_zero] */
    1098 pivotparam += ((pivotparam - temp1vals[i]) / (temp1len - ntemp1removed));
    1099 }
    1100 }
    1101 }
    1102
    1103 for( i = 0; i < dualvectorlen; i++ )
    1104 {
    1105 term = REALABS(dualvector[i]);
    1106 val = MAX(term - pivotparam, 0.0);
    1107
    1108 if( SCIPisPositive(scip, dualvector[i]) )
    1109 {
    1110 dualvector[i] = val;
    1111 }
    1112 else if( SCIPisNegative(scip, dualvector[i]) )
    1113 {
    1114 dualvector[i] = -val;
    1115 }
    1116 }
    1117
    1118 /* free memory */
    1119 for( i = 0; i < dualvectorlen; i++ )
    1120 {
    1121 temp2vals[i] = 0.0;
    1122 temp1vals[i] = 0.0;
    1123 }
    1124 SCIPfreeBufferArray(scip, &temp2inds);
    1125 SCIPfreeBufferArray(scip, &temp1inds);
    1126 SCIPfreeCleanBufferArray(scip, &temp2vals);
    1127 SCIPfreeCleanBufferArray(scip, &temp1vals);
    1128 }
    1129
    1130 return SCIP_OKAY;
    1131}
    1132
    1133/** projection of Lagrangian multipliers onto L2-norm ball */
    1134static
    1135void l2BallProjection(
    1136 SCIP* scip, /**< SCIP data structure */
    1137 SCIP_Real* dualvector, /**< Lagrangian multipliers to be projected onto L2-norm vall */
    1138 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
    1139 SCIP_Real radius /**< radius of the L2-norm ball */
    1140 )
    1141{
    1142 SCIP_Real l2norm;
    1143 SCIP_Real factor;
    1144 int i;
    1145
    1146 assert(!SCIPisNegative(scip, radius));
    1147
    1148 l2norm = 0.0;
    1149
    1150 /* calculate the L2-norm of the Lagrangian multipliers */
    1151 for( i = 0; i < dualvectorlen; i++ )
    1152 l2norm += SQR(dualvector[i]);
    1153 l2norm = sqrt(l2norm);
    1154 factor = radius/(1.0 + l2norm);
    1155
    1156 /* if the vector of Lagrangian multipliers is outside the L2-norm ball, then do the projection */
    1157 if( SCIPisGT(scip, l2norm, radius) && SCIPisLT(scip, factor, 1.0) )
    1158 {
    1159 for( i = 0; i < dualvectorlen; i++ )
    1160 dualvector[i] *= factor;
    1161 }
    1162}
    1163
    1164/** projection of Lagrangian multipliers onto L_infinity-norm ball */
    1165static
    1166void linfBallProjection(
    1167 SCIP* scip, /**< SCIP data structure */
    1168 SCIP_Real* dualvector, /**< Lagrangian multipliers to be projected onto L_infinity-norm vall */
    1169 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
    1170 SCIP_Real radius /**< radius of the L_infinity-norm ball */
    1171 )
    1172{
    1173 int i;
    1174
    1175 assert(!SCIPisNegative(scip, radius));
    1176
    1177 /* if the vector of Lagrangian multipliers is outside the L_infinity-norm ball, then do the projection */
    1178 for( i = 0; i < dualvectorlen; i++ )
    1179 {
    1180 if( SCIPisLT(scip, dualvector[i], -radius) )
    1181 dualvector[i] = -radius;
    1182 else if( SCIPisGT(scip, dualvector[i], radius) )
    1183 dualvector[i] = radius;
    1184 }
    1185}
    1186
    1187/** weighted Lagrangian multipliers based on a given vector as stability center */
    1188/* @todo calculate weight outside this function and pass it (so that this function becomes generic and independent of
    1189 * the terminology related to best Lagrangian multipliers)
    1190 */
    1191static
    1192void weightedDualVector(
    1193 SCIP_SEPADATA* sepadata, /**< separator data structure */
    1194 SCIP_Real* dualvector, /**< Lagrangian multipliers */
    1195 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
    1196 SCIP_Real* stabilitycenter, /**< stability center (i.e., core vector of Lagrangian multipliers) */
    1197 int stabilitycenterlen, /**< length of the stability center */
    1198 int nbestdualupdates, /**< number of best Lagrangian values found so far */
    1199 int totaliternum /**< total number of iterations of the relax-and-cut algorithm performed so far */
    1200 )
    1201{
    1202 SCIP_Real constant;
    1203 SCIP_Real weight;
    1204 SCIP_Real alpha;
    1205 int i;
    1206
    1207 constant = MAX(2.0, sepadata->constant);
    1208
    1209 /* weight factor from the literature on Dantzig-Wolfe decomposition stabilization schemes */
    1210 weight = MIN(constant, (totaliternum + 1 + nbestdualupdates) / 2.0);
    1211 alpha = 1.0 / weight;
    1212
    1213 assert(dualvectorlen >= stabilitycenterlen);
    1214
    1215 /* weighted Lagrangian multipliers */
    1216 for( i = 0; i < stabilitycenterlen; i++ )
    1217 dualvector[i] = alpha * dualvector[i] + (1 - alpha) * stabilitycenter[i];
    1218
    1219 for( i = stabilitycenterlen; i < dualvectorlen; i++ )
    1220 dualvector[i] = alpha * dualvector[i];
    1221}
    1222
    1223/** stabilize Lagrangian multipliers */
    1224static
    1225SCIP_RETCODE stabilizeDualVector(
    1226 SCIP* scip, /**< SCIP data structure */
    1227 SCIP_SEPADATA* sepadata, /**< separator data structure */
    1228 SCIP_Real* dualvector, /**< Lagrangian multipliers */
    1229 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
    1230 SCIP_Real* bestdualvector, /**< best Lagrangian multipliers found so far */
    1231 int bestdualvectorlen, /**< length of the best Lagrangian multipliers vector */
    1232 int nbestdualupdates, /**< number of best Lagrangian values found so far */
    1233 int subgradientiternum, /**< iteration number of the subgradient algorithm */
    1234 int totaliternum, /**< total number of iterations of the relax-and-cut algorithm performed so far */
    1235 SCIP_Real maxviolscore, /**< weighted average of maximum value of generated cut violations and maximum value of
    1236 * complementarity slackness violations, in the current iteration */
    1237 SCIP_Real maxviolscoreold, /**< weighted average of maximum value of generated cut violations and maximum value of
    1238 * complementarity slackness violations, in the previous iteration */
    1239 SCIP_Real nviolscore, /**< weighted average of number of generated cut violations and number of complementarity
    1240 * slackness violations, in the current iteration */
    1241 SCIP_Real nviolscoreold, /**< weighted average of number of generated cut violations and number of complementarity
    1242 * slackness violations, in the previous iteration */
    1243 int nlpiters, /**< number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in
    1244 * current iteration */
    1245 SCIP_Real* ballradius /**< norm ball radius */
    1246 )
    1247{
    1248 if( sepadata->projectiontype > 0 )
    1249 {
    1250 if( subgradientiternum >= 1 )
    1251 {
    1252 /* update the ball radius */
    1253 updateBallRadius(scip, sepadata, maxviolscore, maxviolscoreold, nviolscore, nviolscoreold, nlpiters,
    1254 ballradius);
    1255 }
    1256
    1257 if( sepadata->projectiontype == 1 )
    1258 {
    1259 /* projection of Lagrangian multipliers onto L1-norm ball */
    1260 SCIP_CALL( l1BallProjection(scip, dualvector, dualvectorlen, *ballradius) );
    1261 }
    1262 else if( sepadata->projectiontype == 2 )
    1263 {
    1264 /* projection of Lagrangian multipliers onto L2-norm ball */
    1265 l2BallProjection(scip, dualvector, dualvectorlen, *ballradius);
    1266 }
    1267 else if( sepadata->projectiontype == 3 )
    1268 {
    1269 /* projection of Lagrangian multipliers onto L_inf-norm ball */
    1270 linfBallProjection(scip, dualvector, dualvectorlen, *ballradius);
    1271 }
    1272 }
    1273
    1274 if( sepadata->stabilitycentertype == 1 )
    1275 {
    1276 /* weighted Lagrangian multipliers based on best Langrangian multipliers as stability center */
    1277 weightedDualVector(sepadata, dualvector, dualvectorlen, bestdualvector, bestdualvectorlen, nbestdualupdates, totaliternum);
    1278 }
    1279
    1280 return SCIP_OKAY;
    1281}
    1282
    1283/** update Lagrangian multipliers */
    1284static
    1285SCIP_RETCODE updateDualVector(
    1286 SCIP* scip, /**< SCIP data structure */
    1287 SCIP_SEPADATA* sepadata, /**< separator data structure */
    1288 SCIP_Real* dualvector1, /**< Lagrangian multipliers vector to be updated */
    1289 SCIP_Real* dualvector2, /**< Lagrangian multipliers vector used for backtracking */
    1290 int dualvector2len, /**< length of the Lagrangian multipliers vector used for backtracking */
    1291 int ndualvector2updates,/**< number of best Lagrangian values found so far */
    1292 int subgradientiternum, /**< iteration number of the subgradient algorithm */
    1293 int totaliternum, /**< total number of iterations of the relax-and-cut algorithm performed so far */
    1294 SCIP_Real steplength, /**< step length used for updating Lagrangian multipliers */
    1295 SCIP_Real* subgradient, /**< subgradient vector */
    1296 int ncuts, /**< number of generated cuts so far */
    1297 SCIP_Bool backtrack, /**< whether the Lagrangian multipliers need to be backtracked */
    1298 SCIP_Real maxviolscore, /**< weighted average of maximum value of generated cut violations and maximum value of
    1299 * complementarity slackness violations, in the current iteration */
    1300 SCIP_Real maxviolscoreold, /**< weighted average of maximum value of generated cut violations and maximum value of
    1301 * complementarity slackness violations, in the previous iteration */
    1302 SCIP_Real nviolscore, /**< weighted average of number of generated cut violations and number of complementarity
    1303 * slackness violations, in the current iteration */
    1304 SCIP_Real nviolscoreold, /**< weighted average of number of generated cut violations and number of complementarity
    1305 * slackness violations, in the previous iteration */
    1306 int nlpiters, /**< number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in
    1307 * current iteration */
    1308 SCIP_Bool* dualvecsdiffer, /**< whether the updated Lagrangian multipliers differ from the old one */
    1309 SCIP_Real* ballradius /**< norm ball radius */
    1310 )
    1311{
    1312 SCIP_Real* dualvector1copy;
    1313 int i;
    1314
    1315 assert(dualvector2len <= ncuts);
    1316 assert(dualvecsdiffer != NULL);
    1317
    1318 *dualvecsdiffer = FALSE;
    1319
    1320 /* @todo do allocation and free operations outside only once instead of every time this function is called? */
    1321 /* copy of the Lagrangian multipliers to be used to check if the updated vector is different than this */
    1322 SCIP_CALL( SCIPallocCleanBufferArray(scip, &dualvector1copy, ncuts) );
    1323 for( i = 0; i < ncuts; i++ )
    1324 dualvector1copy[i] = dualvector1[i];
    1325
    1326 /* if backtracking was not identified at the time of the mu parameter update, then update the Lagrangian multipliers
    1327 * based on the given subgradient vector
    1328 */
    1329 if( !backtrack )
    1330 {
    1331 assert((subgradient != NULL) || (ncuts == 0));
    1332 assert(subgradientiternum >= 0);
    1333
    1334 /* update Lagrangian multipliers */
    1335 for( i = 0; i < ncuts; i++ )
    1336 {
    1337 assert(subgradient != NULL); /* for lint */
    1338 dualvector1[i] += steplength * subgradient[i];
    1339 }
    1340
    1341 /* projection onto non-negative orthant */
    1342 for( i = 0; i < ncuts; i++ )
    1343 {
    1344 assert(dualvector1 != NULL); /* for lint */
    1345 dualvector1[i] = MAX(dualvector1[i], 0.0);
    1346 }
    1347
    1348 /* stabilization of Lagrangian multipliers */
    1349 SCIP_CALL( stabilizeDualVector(scip, sepadata, dualvector1, ncuts, dualvector2, dualvector2len,
    1350 ndualvector2updates, subgradientiternum, totaliternum, maxviolscore, maxviolscoreold, nviolscore,
    1351 nviolscoreold, nlpiters, ballradius) );
    1352
    1353 /* projection onto non-negative orthant again in case stabilization changed some components negative*/
    1354 for( i = 0; i < ncuts; i++ )
    1355 dualvector1[i] = MAX(dualvector1[i], 0.0);
    1356 }
    1357 /* if backtracking was identified at the time of the mu parameter update, then backtrack the Lagrangian multipliers
    1358 * based on the given backtracking multipliers
    1359 */
    1360 else
    1361 {
    1362 for( i = 0; i < dualvector2len; i++ )
    1363 dualvector1[i] = dualvector2[i];
    1364
    1365 for( i = dualvector2len; i < ncuts; i++ )
    1366 dualvector1[i] = 0.0;
    1367 }
    1368
    1369 /* identify if the vector of Lagrangian multipliers is indeed different after updating */
    1370 for( i = 0; i < ncuts; i++ )
    1371 {
    1372 if( !SCIPisEQ(scip, dualvector1[i], dualvector1copy[i]) )
    1373 {
    1374 *dualvecsdiffer = TRUE;
    1375 break;
    1376 }
    1377 }
    1378
    1379 /* free memory */
    1380 for( i = 0; i < ncuts; i++ )
    1381 dualvector1copy[i] = 0.0;
    1382
    1383 SCIPfreeCleanBufferArray(scip, &dualvector1copy);
    1384
    1385 return SCIP_OKAY;
    1386}
    1387
    1388/** check different termination criteria
    1389 * @note the criterion based on objvecsdiffer assumes deterministic solving process (i.e., we would get same LP solution
    1390 * for "Lagrangian dual with fixed Lagrangian multipliers" when the objective vector remains the same across iterations).
    1391 */
    1392/* @todo nlpssolved criterion? */
    1393static
    1394SCIP_RETCODE checkLagrangianDualTermination(
    1395 SCIP_SEPADATA* sepadata, /**< separator data structure */
    1396 int nnewaddedsoftcuts, /**< number of cuts that were recently penalized and added to the Lagrangian dual's
    1397 * objective function */
    1398 int nyettoaddsoftcuts, /**< number of cuts that are yet to be penalized and added to the Lagrangian dual's
    1399 * objective function */
    1400 SCIP_Bool objvecsdiffer, /**< whether the Lagrangian dual's objective function has changed */
    1401 int ngeneratedcurrroundcuts, /**< number of cuts generated in the current separation round */
    1402 int nmaxgeneratedperroundcuts, /**< maximal number of cuts allowed to generate per separation round */
    1403 int ncurrroundlpiters, /**< number of separating LP iterations in the current separation round */
    1404 int depth, /**< depth of the current node */
    1405 SCIP_Bool* terminate /**< whether to terminate the subgradient algorithm loop */
    1406 )
    1407{
    1408 *terminate = FALSE;
    1409
    1410 /* check if no new cuts were added to the Lagrangian dual, no cuts are remaining to be added, and the objective
    1411 * function of the Lagrangian dual with fixed multipliers had not changed from the previous iteration
    1412 */
    1413 if( (nnewaddedsoftcuts == 0) && (nyettoaddsoftcuts == 0) && !objvecsdiffer )
    1414 *terminate = TRUE;
    1415
    1416 /* check if allowed number of cuts in this separation round have already been generated */
    1417 if( ngeneratedcurrroundcuts >= nmaxgeneratedperroundcuts )
    1418 *terminate = TRUE;
    1419
    1420 /* check if allowed number of cuts in the tree have already been generated */
    1421 if( sepadata->ntotalcuts >= sepadata->nmaxtotalcuts )
    1422 *terminate = TRUE;
    1423
    1424 /* check if allowed number of simplex iterations in this separation round have already been used up */
    1425 if( (sepadata->nmaxperroundlpiters >= 0) && (ncurrroundlpiters >= sepadata->nmaxperroundlpiters) )
    1426 *terminate = TRUE;
    1427
    1428 /* check if allowed number of simplex iterations in the root node have already been used up */
    1429 if( (depth == 0) && (sepadata->nmaxrootlpiters >= 0) && (sepadata->nrootlpiters >= sepadata->nmaxrootlpiters) )
    1430 *terminate = TRUE;
    1431
    1432 /* check if allowed number of simplex iterations in the tree have already been used up */
    1433 if( (sepadata->nmaxtotallpiters >= 0) && (sepadata->ntotallpiters >= sepadata->nmaxtotallpiters) )
    1434 *terminate = TRUE;
    1435
    1436 return SCIP_OKAY;
    1437}
    1438
    1439/** solve the LP corresponding to the Lagrangian dual with fixed Lagrangian multipliers */
    1440static
    1441SCIP_RETCODE solveLagromoryLP(
    1442 SCIP* scip, /**< SCIP data structure */
    1443 SCIP_SEPADATA* sepadata, /**< separator data structure */
    1444 int depth, /**< depth of the current node in the tree */
    1445 SCIP_Real origobjoffset, /**< objective offset in the current node's relaxation */
    1446 SCIP_Bool* solfound, /**< whether an LP optimal solution has been found */
    1447 SCIP_SOL* sol, /**< data structure to store LP optimal solution, if found */
    1448 SCIP_Real* solvals, /**< values of the LP optimal solution, if found */
    1449 SCIP_Real* objval, /**< optimal objective value of the LP optimal solution, if found */
    1450 int* ncurrroundlpiters /**< number of LP iterations taken for solving Lagrangian dual problems with fixed multipliers
    1451 * in the current separator round */
    1452 )
    1453{
    1454 SCIP_Real timelimit;
    1455 SCIP_COL** cols;
    1456 SCIP_COL* col;
    1457 SCIP_VAR* var;
    1458 SCIP_LPI* lpi;
    1459 SCIP_Bool lperror;
    1460 SCIP_Bool cutoff;
    1461 SCIP_LPSOLSTAT stat;
    1462 SCIP_Longint ntotallpiters;
    1463 SCIP_Longint nlpiters;
    1464 int ncols;
    1465 int iterlimit;
    1466
    1467 assert(solfound != NULL);
    1468 assert(sol != NULL);
    1469 assert(solvals != NULL);
    1470 assert(ncurrroundlpiters != NULL);
    1471 assert(objval != NULL);
    1472
    1473 *solfound = FALSE;
    1474 lperror = FALSE;
    1475 cutoff = FALSE;
    1476 iterlimit = -1;
    1477 lpi = sepadata->lpiwithsoftcuts;
    1478
    1479 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    1480
    1481 /* set time limit */
    1482 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
    1483 if( !SCIPisInfinity(scip, timelimit) )
    1484 {
    1485 timelimit -= SCIPgetSolvingTime(scip);
    1486 if( timelimit <= 0.0 )
    1487 {
    1488 SCIPdebugMsg(scip, "skip Lagromory cut generation since no time left\n");
    1489 goto TERMINATE;
    1490 }
    1491
    1492 /* @note the following direct LPI call is being used because of the lack of an equivalent function call in
    1493 * scip_lp.c (lpSetRealpar exists in lp.c though)
    1494 */
    1495 SCIP_CALL( SCIPlpiSetRealpar(lpi, SCIP_LPPAR_LPTILIM, timelimit) );
    1496 }
    1497
    1498 /* find iteration limit */
    1499 if( (depth == 0) &&
    1500 (sepadata->perrootlpiterfactor >= 0.0 && !SCIPisInfinity(scip, sepadata->perrootlpiterfactor)) )
    1501 {
    1502 iterlimit = (int)(sepadata->perrootlpiterfactor * SCIPgetNRootFirstLPIterations(scip));
    1503 }
    1504 else if( (depth > 0) &&
    1505 (sepadata->perlpiterfactor >= 0.0 && !SCIPisInfinity(scip, sepadata->perlpiterfactor)) )
    1506 {
    1507 iterlimit = (int)(sepadata->perlpiterfactor * SCIPgetNNodeInitLPIterations(scip));
    1508 }
    1509 if( sepadata->nmaxperroundlpiters >= 0 )
    1510 {
    1511 if( sepadata->nmaxperroundlpiters - *ncurrroundlpiters >= 0 )
    1512 {
    1513 if( iterlimit >= 0 )
    1514 iterlimit = MIN(iterlimit, sepadata->nmaxperroundlpiters - *ncurrroundlpiters);
    1515 else
    1516 iterlimit = sepadata->nmaxperroundlpiters - *ncurrroundlpiters;
    1517 }
    1518 else
    1519 iterlimit = 0;
    1520 }
    1521 /* @todo impose a finite iteration limit only when the dualvector changes from zero to non-zero for the first time because
    1522 * many simplex pivots are performed in this case even with warm starting (compared to the case when the
    1523 * dualvector changes from non-zero to non-zero)
    1524 */
    1525
    1526 /* solve the LP with an iteration limit and get number of simplex iterations taken */
    1527 ntotallpiters = SCIPgetNLPIterations(scip);
    1528
    1529 SCIP_CALL( SCIPsolveDiveLP(scip, iterlimit, &lperror, &cutoff) );
    1530
    1531 nlpiters = SCIPgetNLPIterations(scip) - ntotallpiters;
    1532
    1533 /* get the solution and objective value if optimal */
    1534 stat = SCIPgetLPSolstat(scip);
    1535
    1536 /* @todo is there any way to accept terminations due to iterlimit and timelimit as well? It is not possible
    1537 * currently because primal sol is not saved in these cases.
    1538 */
    1539 /* @note ideally, only primal feasibility is sufficient. But, there is no such option with SCIPgetLPSolstat. */
    1540 if( stat == SCIP_LPSOLSTAT_OPTIMAL )
    1541 {
    1542 if( SCIPisLPSolBasic(scip) )
    1543 {
    1544 int i;
    1545
    1546 *solfound = TRUE;
    1547
    1548 /* update sol */
    1549 for( i = 0; i < ncols; ++i )
    1550 {
    1551 col = cols[i];
    1552 assert(col != NULL);
    1553
    1554 var = SCIPcolGetVar(col);
    1555
    1556 solvals[i] = SCIPcolGetPrimsol(col);
    1557 SCIP_CALL( SCIPsetSolVal(scip, sol, var, solvals[i]) );
    1558 }
    1559
    1560 *objval = SCIPgetLPObjval(scip);
    1561 *objval = *objval + origobjoffset;
    1562 }
    1563 }
    1564
    1565 /* update some statistics */
    1566 if( depth == 0 )
    1567 sepadata->nrootlpiters += (int)nlpiters;
    1568
    1569 sepadata->ntotallpiters += (int)nlpiters;
    1570 *ncurrroundlpiters += (int)nlpiters;
    1571
    1572TERMINATE:
    1573 return SCIP_OKAY;
    1574}
    1575
    1576/** solve the LP corresponding to the node relaxation upon adding all the generated cuts */
    1577static
    1578SCIP_RETCODE solveLPWithHardCuts(
    1579 SCIP* scip, /**< SCIP data structure */
    1580 SCIP_SEPADATA* sepadata, /**< separator data structure */
    1581 SCIP_Bool* solfound, /**< whether an LP optimal solution has been found */
    1582 SCIP_SOL* sol, /**< data structure to store LP optimal solution, if found */
    1583 SCIP_Real* solvals /**< values of the LP optimal solution, if found */
    1584 )
    1585{
    1586 SCIP_Real timelimit;
    1587 SCIP_COL** cols;
    1588 SCIP_COL* col;
    1589 SCIP_VAR* var;
    1590 int ncols;
    1591
    1592 assert(solfound != NULL);
    1593 assert(sol != NULL);
    1594 assert(solvals != NULL);
    1595
    1596 *solfound = FALSE;
    1597
    1598 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    1599
    1600 /* set time limit */
    1601 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
    1602 if( !SCIPisInfinity(scip, timelimit) )
    1603 {
    1604 timelimit -= SCIPgetSolvingTime(scip);
    1605 if( timelimit <= 0.0 )
    1606 {
    1607 SCIPdebugMsg(scip, "skip Lagromory cut generation since no time left\n");
    1608 goto TERMINATE;
    1609 }
    1610 SCIP_CALL( SCIPlpiSetRealpar(sepadata->lpiwithhardcuts, SCIP_LPPAR_LPTILIM, timelimit) );
    1611 }
    1612
    1613 /* solve the LP */
    1614 SCIP_CALL( SCIPlpiSolvePrimal(sepadata->lpiwithhardcuts) );
    1615
    1616 /* get the solution if primal feasible */
    1617 if( SCIPlpiIsPrimalFeasible(sepadata->lpiwithhardcuts) )
    1618 {
    1619 int i;
    1620
    1621 *solfound = TRUE;
    1622 SCIP_CALL( SCIPlpiGetSol(sepadata->lpiwithhardcuts, NULL, solvals, NULL, NULL, NULL) );
    1623
    1624 /* update sol */
    1625 for( i = 0; i < ncols; ++i )
    1626 {
    1627 col = cols[i];
    1628 assert(col != NULL);
    1629
    1630 var = SCIPcolGetVar(col);
    1631
    1632 SCIP_CALL( SCIPsetSolVal(scip, sol, var, solvals[i]) );
    1633 }
    1634 }
    1635
    1636TERMINATE:
    1637 return SCIP_OKAY;
    1638}
    1639
    1640/** construct a cut based on the input cut coefficients, sides, etc */
    1641static
    1642SCIP_RETCODE constructCutRow(
    1643 SCIP* scip, /**< SCIP data structure */
    1644 SCIP_SEPA* sepa, /**< pointer to the separator */
    1645 SCIP_SEPADATA* sepadata, /**< separator data structure */
    1646 int mainiternum, /**< iteration number of the outer loop of the relax-and-cut algorithm */
    1647 int subgradientiternum, /**< iteration number of the subgradient algorithm */
    1648 int cutnnz, /**< number of nonzeros in cut */
    1649 int* cutinds, /**< column indices in cut */
    1650 SCIP_Real* cutcoefs, /**< cut cofficients */
    1651 SCIP_Real cutefficacy, /**< cut efficacy */
    1652 SCIP_Real cutrhs, /**< RHS of cut */
    1653 SCIP_Bool cutislocal, /**< whether cut is local */
    1654 int cutrank, /**< rank of cut */
    1655 SCIP_ROW** generatedcuts, /**< array of generated cuts */
    1656 SCIP_Real* generatedcutefficacies, /**< array of generated cut efficacies w.r.t. the respective LP bases used for cut
    1657 * generations */
    1658 int ngeneratedcurrroundcuts, /**< number of cuts generated until the previous basis in the current separation round */
    1659 int* ngeneratednewcuts, /**< number of new cuts generated using the current basis */
    1660 SCIP_Bool* cutoff /**< should the current node be cutoff? */
    1661 )
    1662{
    1663 SCIP_COL** cols;
    1664 SCIP_Real minactivity;
    1665 SCIP_Real maxactivity;
    1666 SCIP_Real lhs;
    1667 SCIP_Real rhs;
    1668
    1669 assert(scip != NULL);
    1670 assert(mainiternum >= 0);
    1671 assert(ngeneratednewcuts != NULL);
    1672 assert(cutoff != NULL);
    1673
    1674 *cutoff = FALSE;
    1675
    1676 if( cutnnz == 0 && SCIPisFeasNegative(scip, cutrhs) ) /*lint !e644*/
    1677 {
    1678 SCIPdebugMsg(scip, " -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", cutrhs);
    1679 *cutoff = TRUE;
    1680 return SCIP_OKAY;
    1681 }
    1682
    1683 /* only take efficient cuts */
    1684 if( SCIPisEfficacious(scip, cutefficacy) )
    1685 {
    1686 SCIP_ROW* cut;
    1687 SCIP_VAR* var;
    1688 char cutname[SCIP_MAXSTRLEN];
    1689 int v;
    1690
    1691 /* construct cut name */
    1692 if( subgradientiternum >= 0 )
    1693 {
    1694 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_%" SCIP_LONGINT_FORMAT "_%d" "_%d" "_%d", SCIPsepaGetName(sepa),
    1695 sepadata->ncalls, mainiternum, subgradientiternum, ngeneratedcurrroundcuts + *ngeneratednewcuts);
    1696 }
    1697 else
    1698 {
    1699 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_%" SCIP_LONGINT_FORMAT "_%d" "_%d", SCIPsepaGetName(sepa),
    1700 sepadata->ncalls, mainiternum, ngeneratedcurrroundcuts + *ngeneratednewcuts);
    1701 }
    1702
    1703 /* create empty cut */
    1704 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE,
    1705 sepadata->dynamiccuts) );
    1706
    1707 /* set cut rank */
    1708 SCIProwChgRank(cut, cutrank); /*lint !e644*/
    1709
    1710 /* cache the row extension and only flush them if the cut gets added */
    1711 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
    1712
    1713 cols = SCIPgetLPCols(scip);
    1714
    1715 /* collect all non-zero coefficients */
    1716 for( v = 0; v < cutnnz; ++v )
    1717 {
    1718 var = SCIPcolGetVar(cols[cutinds[v]]);
    1719 SCIP_CALL( SCIPaddVarToRow(scip, cut, var, cutcoefs[v]) );
    1720 }
    1721
    1722 /* flush all changes before adding the cut */
    1723 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
    1724
    1725 if( SCIProwGetNNonz(cut) == 0 )
    1726 {
    1727 assert( SCIPisFeasNegative(scip, cutrhs) );
    1728 SCIPdebugMsg(scip, " -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", cutrhs);
    1729 *cutoff = TRUE;
    1730 return SCIP_OKAY;
    1731 }
    1732 else
    1733 {
    1734 /* gathering lhs and rhs again in case the separator is extended later to add other cuts/constraints that may
    1735 * have non-inf lhs or inf rhs */
    1736 lhs = SCIProwGetLhs(cut);
    1737 rhs = SCIProwGetRhs(cut);
    1738 assert(SCIPisInfinity(scip, -lhs));
    1739 assert(!SCIPisInfinity(scip, rhs));
    1740
    1741 SCIPdebugMsg(scip, " -> %s cut <%s>: rhs=%f, eff=%f\n", "lagromory", cutname, cutrhs, cutefficacy);
    1742
    1743 /* check if the cut leads to infeasibility (i.e., *cutoff = TRUE) */
    1744 {
    1745 /* modifiable cuts cannot be declared infeasible, since we don't know all coefficients */
    1746 if( SCIProwIsModifiable(cut) )
    1747 *cutoff = FALSE;
    1748
    1749 /* check for activity infeasibility */
    1750 minactivity = SCIPgetRowMinActivity(scip, cut);
    1751 maxactivity = SCIPgetRowMaxActivity(scip, cut);
    1752
    1753 if( (!SCIPisInfinity(scip, rhs) && SCIPisFeasPositive(scip, minactivity - rhs)) ||
    1754 (!SCIPisInfinity(scip, -lhs) && SCIPisFeasNegative(scip, maxactivity - lhs)) )
    1755 {
    1756 SCIPdebugMsg(scip, "cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
    1757 SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
    1758 *cutoff = TRUE;
    1759 }
    1760 }
    1761
    1762 /* store the newly generated cut in an array and update some statistics */
    1763 generatedcuts[ngeneratedcurrroundcuts + *ngeneratednewcuts] = cut;
    1764 generatedcutefficacies[ngeneratedcurrroundcuts + *ngeneratednewcuts] = cutefficacy;
    1765 ++(*ngeneratednewcuts);
    1766 }
    1767 }
    1768
    1769 return SCIP_OKAY;
    1770}
    1771
    1772/** aggregated generated cuts based on the best Lagrangian multipliers */
    1773static
    1774SCIP_RETCODE aggregateGeneratedCuts(
    1775 SCIP* scip, /**< SCIP data structure */
    1776 SCIP_SEPA* sepa, /**< pointer to the separator */
    1777 SCIP_SEPADATA* sepadata, /**< separator data structure */
    1778 SCIP_ROW** generatedcuts, /**< cuts generated in the current separation round */
    1779 SCIP_Real* bestdualvector, /**< best Lagrangian multipliers vector */
    1780 int bestdualvectorlen, /**< length of the best Lagrangian multipliers vector */
    1781 SCIP_ROW** aggrcuts, /**< aggregated cuts generated so far in the current separation round */
    1782 int* naggrcuts, /**< number of aggregated cuts generated so far in the current separation round */
    1783 SCIP_Bool* cutoff /**< should the current node be cutoff? */
    1784 )
    1785{
    1786 SCIP_Real* cutvals; /* cut cofficients */
    1787 SCIP_COL** cutcols;
    1788 SCIP_COL** cols;
    1789 SCIP_VAR* var;
    1790 SCIP_ROW* cut;
    1791 SCIP_ROW* aggrcut;
    1792 SCIP_Real minactivity;
    1793 SCIP_Real maxactivity;
    1794 SCIP_Real cutlhs;
    1795 SCIP_Real cutrhs;
    1796 SCIP_Real cutconst;
    1797 SCIP_Real aggrcutlhs;
    1798 SCIP_Real aggrcutrhs;
    1799 SCIP_Real aggrcutconst;
    1800 SCIP_Real* aggrcutvals;
    1801 SCIP_Real* aggrcutcoefs;
    1802 SCIP_Real multiplier;
    1803 SCIP_Bool aggrcutislocal;
    1804 SCIP_Bool aggrindicator;
    1805 SCIP_Real* tmpcutvals;
    1806 SCIP_Real QUAD(quadterm);
    1807 SCIP_Real QUAD(tmpcutconst);
    1808 SCIP_Real QUAD(tmpcutrhs);
    1809 SCIP_Real QUAD(quadprod);
    1810 char aggrcutname[SCIP_MAXSTRLEN];
    1811 int cutnnz; /* number of nonzeros in cut */
    1812 int aggrcutnnz;
    1813 int* aggrcutinds; /* column indices in cut */
    1814 int aggrcutrank; /* rank of cut */
    1815 int cutrank;
    1816 int ncols;
    1817 int collppos;
    1818 int nlocalcuts;
    1819 int i;
    1820 int j;
    1821
    1822 assert(scip != NULL);
    1823 assert(naggrcuts != NULL);
    1824 assert(cutoff != NULL);
    1825
    1826 *cutoff = FALSE;
    1827 aggrcutlhs = -SCIPinfinity(scip);
    1828 aggrcutnnz = 0;
    1829 aggrcutrank = -1;
    1830 nlocalcuts = 0;
    1831 aggrindicator = FALSE;
    1832
    1833 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    1834
    1835 /* allocate memory */
    1836 SCIP_CALL( SCIPallocCleanBufferArray(scip, &tmpcutvals, QUAD_ARRAY_SIZE(ncols)) );
    1837 QUAD_ASSIGN(tmpcutconst, 0.0);
    1838 QUAD_ASSIGN(tmpcutrhs, 0.0);
    1839 SCIP_CALL( SCIPallocCleanBufferArray(scip, &aggrcutvals, ncols) );
    1840 SCIP_CALL( SCIPallocBufferArray(scip, &aggrcutcoefs, ncols) );
    1841 SCIP_CALL( SCIPallocBufferArray(scip, &aggrcutinds, ncols) );
    1842
    1843 /* aggregate cuts based on the input Lagrangian multipliers */
    1844 for( i = 0; i < bestdualvectorlen; i++ )
    1845 {
    1846 multiplier = bestdualvector[i];
    1847 if( SCIPisGE(scip, multiplier, 1e-4) )
    1848 {
    1849 cut = generatedcuts[i];
    1850 cutnnz = SCIProwGetNNonz(cut);
    1851 cutlhs = SCIProwGetLhs(cut);
    1852 cutrhs = SCIProwGetRhs(cut);
    1853 assert(SCIPisInfinity(scip, -cutlhs));
    1854 assert(!SCIPisInfinity(scip, cutrhs));
    1855 cutvals = SCIProwGetVals(cut);
    1856 cutcols = SCIProwGetCols(cut);
    1857 cutconst = SCIProwGetConstant(cut);
    1858
    1859 for( j = 0; j < cutnnz; j++ )
    1860 {
    1861 collppos = SCIPcolGetLPPos(cutcols[j]);
    1862 assert(collppos >= 0);
    1863 assert(collppos <= ncols);
    1864
    1865 QUAD_ARRAY_LOAD(quadterm, tmpcutvals, collppos);
    1866 SCIPquadprecProdDD(quadprod, multiplier, cutvals[j]);
    1867 SCIPquadprecSumQQ(quadterm, quadterm, quadprod);
    1868 QUAD_ARRAY_STORE(tmpcutvals, collppos, quadterm);
    1869 }
    1870
    1871 SCIPquadprecProdDD(quadprod, multiplier, cutconst);
    1872 SCIPquadprecSumQQ(tmpcutconst, tmpcutconst, quadprod);
    1873 SCIPquadprecProdDD(quadprod, multiplier, cutrhs);
    1874 SCIPquadprecSumQQ(tmpcutrhs, tmpcutrhs, quadprod);
    1875
    1876 cutrank = SCIProwGetRank(cut);
    1877 aggrcutrank = MAX(aggrcutrank, cutrank);
    1878 nlocalcuts += (SCIProwIsLocal(cut) ? 1 : 0);
    1879 aggrindicator = TRUE;
    1880 }
    1881 }
    1882 /* if at least one cut is local, then the aggregated cut is local */
    1883 aggrcutislocal = (nlocalcuts > 0 ? TRUE : FALSE);
    1884
    1885 /* if the aggregation was successful, then create an empty row and build a cut */
    1886 if( aggrindicator )
    1887 {
    1888 aggrcutconst = QUAD_TO_DBL(tmpcutconst);
    1889 aggrcutrhs = QUAD_TO_DBL(tmpcutrhs);
    1890
    1891 /* build sparse representation of the aggregated cut */
    1892 for( i = 0; i < ncols; i++ )
    1893 {
    1894 QUAD_ARRAY_LOAD(quadterm, tmpcutvals, i);
    1895 aggrcutvals[i] = QUAD_TO_DBL(quadterm);
    1896 if( !SCIPisZero(scip, aggrcutvals[i]) )
    1897 {
    1898 aggrcutcoefs[aggrcutnnz] = aggrcutvals[i];
    1899 aggrcutinds[aggrcutnnz] = i;
    1900 aggrcutnnz++;
    1901 }
    1902 }
    1903
    1904 if( aggrcutnnz == 0 && SCIPisFeasNegative(scip, aggrcutrhs) ) /*lint !e644*/
    1905 {
    1906 SCIPdebugMsg(scip, " -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", aggrcutrhs);
    1907 *cutoff = TRUE;
    1908 goto TERMINATE;
    1909 }
    1910
    1911 /* construct aggregated cut name */
    1912 (void) SCIPsnprintf(aggrcutname, SCIP_MAXSTRLEN, "%s_%" SCIP_LONGINT_FORMAT "_aggregated", SCIPsepaGetName(sepa),
    1913 sepadata->ncalls);
    1914
    1915 /* create empty cut */
    1916 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &aggrcut, sepa, aggrcutname, aggrcutlhs - aggrcutconst, aggrcutrhs -
    1917 aggrcutconst, aggrcutislocal, FALSE, sepadata->dynamiccuts) );
    1918
    1919 /* set cut rank */
    1920 SCIProwChgRank(aggrcut, aggrcutrank); /*lint !e644*/
    1921
    1922 /* cache the row extension and only flush them if the cut gets added */
    1923 SCIP_CALL( SCIPcacheRowExtensions(scip, aggrcut) );
    1924
    1925 /* collect all non-zero coefficients */
    1926 for( i = 0; i < aggrcutnnz; i++ )
    1927 {
    1928 var = SCIPcolGetVar(cols[aggrcutinds[i]]);
    1929 SCIP_CALL( SCIPaddVarToRow(scip, aggrcut, var, aggrcutcoefs[i]) );
    1930 }
    1931
    1932 /* flush all changes before adding the cut */
    1933 SCIP_CALL( SCIPflushRowExtensions(scip, aggrcut) );
    1934
    1935 if( SCIProwGetNNonz(aggrcut) == 0 )
    1936 {
    1937 assert( SCIPisFeasNegative(scip, aggrcutrhs) );
    1938 SCIPdebugMsg(scip, " -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", aggrcutrhs);
    1939 *cutoff = TRUE;
    1940 goto TERMINATE;
    1941 }
    1942 else
    1943 {
    1944 /* gathering lhs and rhs again in case the separator is extended later to add other cuts/constraints that may
    1945 * have non-inf lhs or inf rhs */
    1946 cutlhs = SCIProwGetLhs(aggrcut);
    1947 cutrhs = SCIProwGetRhs(aggrcut);
    1948 assert(SCIPisInfinity(scip, -cutlhs));
    1949 assert(!SCIPisInfinity(scip, cutrhs));
    1950
    1951 SCIPdebugMsg(scip, " -> %s cut <%s>: rhs=%f\n", "lagromory", aggrcutname, aggrcutrhs);
    1952
    1953 /* check if the cut leads to infeasibility (i.e., *cutoff = TRUE) */
    1954 {
    1955 /* modifiable cuts cannot be declared infeasible, since we don't know all coefficients */
    1956 if( SCIProwIsModifiable(aggrcut) )
    1957 *cutoff = FALSE;
    1958
    1959 /* check for activity infeasibility */
    1960 minactivity = SCIPgetRowMinActivity(scip, aggrcut);
    1961 maxactivity = SCIPgetRowMaxActivity(scip, aggrcut);
    1962
    1963 if( (!SCIPisInfinity(scip, cutrhs) && SCIPisFeasPositive(scip, minactivity - cutrhs)) ||
    1964 (!SCIPisInfinity(scip, -cutlhs) && SCIPisFeasNegative(scip, maxactivity - cutlhs)) )
    1965 {
    1966 SCIPdebugMsg(scip, "cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
    1967 SCIProwGetName(aggrcut), cutlhs, cutrhs, minactivity, maxactivity);
    1968 *cutoff = TRUE;
    1969 }
    1970 }
    1971
    1972 /* add the aggregated cut to a separate data structure */
    1973 aggrcuts[*naggrcuts] = aggrcut;
    1974 (*naggrcuts)++;
    1975 }
    1976
    1977 QUAD_ASSIGN(quadterm, 0.0);
    1978 for( i = 0; i < ncols; i++ )
    1979 {
    1980 aggrcutvals[i] = 0.0;
    1981 QUAD_ARRAY_STORE(tmpcutvals, i, quadterm);
    1982 }
    1983 }
    1984
    1985TERMINATE:
    1986 /* free memory */
    1987 SCIPfreeBufferArray(scip, &aggrcutinds);
    1988 SCIPfreeBufferArray(scip, &aggrcutcoefs);
    1989 SCIPfreeCleanBufferArray(scip, &aggrcutvals);
    1990 SCIPfreeCleanBufferArray(scip, &tmpcutvals);
    1991
    1992 return SCIP_OKAY;
    1993}
    1994
    1995/** main method: LP solution separation method of separator */
    1996static
    1997SCIP_RETCODE generateGMICuts(
    1998 SCIP* scip, /**< SCIP data structure */
    1999 SCIP_SEPA* sepa, /**< pointer to the separator */
    2000 SCIP_SEPADATA* sepadata, /**< separator data structure */
    2001 int mainiternum, /**< iteration number of the outer loop of the relax-and-cut algorithm */
    2002 int subgradientiternum, /**< iteration number of the subgradient algorithm */
    2003 SCIP_SOL* sol, /**< LP solution to be used for cut generation */
    2004 SCIP_Real* solvals, /**< values of the LP solution to be used for cut generation */
    2005 int nmaxgeneratedperroundcuts, /**< maximal number of cuts allowed to generate per separation round */
    2006 SCIP_Bool allowlocal, /**< should locally valid cuts be generated? */
    2007 SCIP_ROW** generatedcurrroundcuts, /**< cuts generated in the current separation round */
    2008 SCIP_Real* generatedcutefficacies, /**< array of generated cut efficacies w.r.t. the respective LP bases used for cut
    2009 * generations */
    2010 int ngeneratedcurrroundcuts, /**< number of cuts generated until the previous basis in the current separation round */
    2011 int* ngeneratednewcuts, /**< number of new cuts generated using the current basis */
    2012 int depth, /**< depth of the current node in the tree */
    2013 SCIP_Bool* cutoff /**< should the current node be cutoff? */
    2014 )
    2015{
    2016 SCIP_Real minfrac;
    2017 SCIP_Real maxfrac;
    2018 SCIP_Real frac;
    2019 SCIP_Real* basisfrac;
    2020 SCIP_Real* binvrow;
    2021 SCIP_AGGRROW* aggrrow;
    2022 SCIP_Bool success;
    2023 SCIP_Real* cutcoefs;
    2024 SCIP_Real cutrhs;
    2025 SCIP_Real cutefficacy;
    2026 SCIP_Bool cutislocal;
    2027 SCIP_ROW** rows;
    2028 SCIP_COL** cols;
    2029 SCIP_VAR* var;
    2030 SCIP_ROW* row;
    2031 int cutrank;
    2032 int cutnnz;
    2033 int* cutinds;
    2034 int* basisind;
    2035 int* inds;
    2036 int nrows;
    2037 int ncols;
    2038 int* basisperm;
    2039 int k;
    2040 int c;
    2041 int ninds;
    2042 int nmaxcutsperlp;
    2043 int i;
    2044
    2045 assert(ngeneratednewcuts != NULL);
    2046
    2047 minfrac = sepadata->away;
    2048 maxfrac = 1.0 - sepadata->away;
    2049 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
    2050 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    2051 *ngeneratednewcuts = 0;
    2052 nmaxcutsperlp = ((depth == 0) ? sepadata->nmaxcutsperlproot : sepadata->nmaxcutsperlp);
    2053
    2054 /* allocate memory */
    2055 SCIP_CALL( SCIPallocBufferArray(scip, &basisperm, nrows) );
    2056 SCIP_CALL( SCIPallocBufferArray(scip, &basisfrac, nrows) );
    2057 SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
    2058 SCIP_CALL( SCIPallocBufferArray(scip, &inds, nrows) );
    2059 SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
    2060 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
    2061 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, ncols) );
    2062 SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
    2063
    2064 SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
    2065
    2066 /* check if the rows of the simplex tableau are suitable for cut generation and build an array of fractions */
    2067 for( i = 0; i < nrows; ++i )
    2068 {
    2069 frac = 0.0;
    2070
    2071 c = basisind[i];
    2072
    2073 basisperm[i] = i;
    2074
    2075 /* if the simplex tableau row corresponds to an LP column */
    2076 if( c >= 0 )
    2077 {
    2078 assert(c < ncols);
    2079
    2080 var = SCIPcolGetVar(cols[c]);
    2081 /* if the column is non-continuous one */
    2082 if( SCIPvarIsIntegral(var) )
    2083 {
    2084 frac = SCIPfeasFrac(scip, solvals[c]);
    2085 frac = MIN(frac, 1.0 - frac);
    2086 }
    2087 }
    2088 /* if the simplex tableau row corresponds to an LP row and separation on rows is allowed */
    2089 else if( sepadata->separaterows )
    2090 {
    2091 assert(0 <= -c-1);
    2092 assert(-c-1 < nrows);
    2093
    2094 row = rows[-c-1];
    2095 /* if the row is suitable for cut generation */
    2096 if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
    2097 {
    2098 frac = SCIPfeasFrac(scip, SCIPgetRowActivity(scip, row));
    2099 frac = MIN(frac, 1.0 - frac);
    2100 }
    2101 }
    2102
    2103 if( frac >= minfrac )
    2104 {
    2105 /* slightly change fractionality to have random order for equal fractions */
    2106 basisfrac[i] = frac + SCIPrandomGetReal(sepadata->randnumgen, -1e-6, 1e-6);
    2107 }
    2108 else
    2109 {
    2110 basisfrac[i] = 0.0;
    2111 }
    2112 }
    2113
    2114 /* if there is a need to sort the fractionalities */
    2115 if( sepadata->sortcutoffsol )
    2116 {
    2117 /* sort basis indices by fractionality */
    2118 SCIPsortDownRealInt(basisfrac, basisperm, nrows);
    2119 }
    2120
    2121 /* for all basic columns belonging to integer variables, try to generate a GMI cut */
    2122 for( i = 0; i < nrows && !SCIPisStopped(scip) && !*cutoff; ++i )
    2123 {
    2124 if( (ngeneratedcurrroundcuts + *ngeneratednewcuts >= nmaxgeneratedperroundcuts) ||
    2125 (sepadata->ntotalcuts + *ngeneratednewcuts >= sepadata->nmaxtotalcuts) ||
    2126 (*ngeneratednewcuts >= nmaxcutsperlp) )
    2127 break;
    2128
    2129 ninds = -1;
    2130 cutefficacy = 0.0;
    2131
    2132 /* either break the loop or proceed to the next iteration if the fractionality is zero */
    2133 if( basisfrac[i] == 0.0 )
    2134 {
    2135 if( sepadata->sortcutoffsol )
    2136 break;
    2137 else
    2138 continue;
    2139 }
    2140
    2141 k = basisperm[i];
    2142
    2143 /* get the row of B^-1 for this basic integer variable with fractional solution value and call aggregate function */
    2144 SCIP_CALL( SCIPgetLPBInvRow(scip, k, binvrow, inds, &ninds) );
    2145
    2146 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, binvrow, inds, ninds, sepadata->sidetypebasis, allowlocal, 2,
    2147 (int) MAXAGGRLEN(ncols), &success) );
    2148
    2149 if( !success )
    2150 continue;
    2151
    2152 /* @todo Currently we are using the SCIPcalcMIR() function to compute the coefficients of the Gomory
    2153 * cut. Alternatively, we could use the direct version (see thesis of Achterberg formula (8.4)) which
    2154 * leads to cut a of the form \sum a_i x_i \geq 1. Rumor has it that these cuts are better.
    2155 */
    2156
    2157 /* try to create GMI cut out of the aggregation row */
    2158 SCIP_CALL( SCIPcalcMIR(scip, sol, POSTPROCESS, BOUNDSWITCH, VARTYPEUSEVBDS, allowlocal, FIXINTEGRALRHS, NULL,
    2159 NULL, minfrac, maxfrac, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank,
    2160 &cutislocal, &success) );
    2161
    2162 if( success )
    2163 {
    2164 assert(allowlocal || !cutislocal); /*lint !e644*/
    2165
    2166 SCIP_CALL( constructCutRow(scip, sepa, sepadata, mainiternum, subgradientiternum, cutnnz, cutinds, cutcoefs,
    2167 cutefficacy, cutrhs, cutislocal, cutrank, generatedcurrroundcuts, generatedcutefficacies,
    2168 ngeneratedcurrroundcuts, ngeneratednewcuts, cutoff));
    2169 }
    2170 }
    2171
    2172 /* free temporary memory */
    2173 SCIPfreeBufferArray(scip, &cutinds);
    2174 SCIPfreeBufferArray(scip, &cutcoefs);
    2175 SCIPfreeBufferArray(scip, &basisind);
    2176 SCIPfreeBufferArray(scip, &inds);
    2177 SCIPfreeBufferArray(scip, &binvrow);
    2178 SCIPfreeBufferArray(scip, &basisfrac);
    2179 SCIPfreeBufferArray(scip, &basisperm);
    2180 SCIPaggrRowFree(scip, &aggrrow);
    2181
    2182 return SCIP_OKAY;
    2183}
    2184
    2185/** update objective vector w.r.t. the fixed Lagrangian multipliers */
    2186static
    2187SCIP_RETCODE updateObjectiveVector(
    2188 SCIP* scip, /**< SCIP data structure */
    2189 SCIP_Real* dualvector, /**< Lagrangian multipliers vector */
    2190 SCIP_ROW** cuts, /**< cuts generated so far in the current separation round */
    2191 int ncuts, /**< number of cuts generated so far in the current separation round */
    2192 SCIP_Real* origobjcoefs, /**< original objective function coefficients of the node linear relaxation */
    2193 SCIP_Bool* objvecsdiffer /**< whether the updated objective function coefficients differ from the old ones */
    2194 )
    2195{
    2196 SCIP_Real* objvals;
    2197 SCIP_Real* prod;
    2198 SCIP_Real* oldobjvals;
    2199 SCIP_Real* cutvals;
    2200 SCIP_COL** cutcols;
    2201 SCIP_COL** cols;
    2202 SCIP_VAR* var;
    2203 int cutnnz;
    2204 int collppos;
    2205 int ncols;
    2206 int i;
    2207 int j;
    2208
    2209 assert(objvecsdiffer != NULL);
    2210 assert(ncuts > 0);
    2211
    2212 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    2213
    2214 /* allocate memory */
    2215 SCIP_CALL( SCIPallocBufferArray(scip, &objvals, ncols) );
    2216 SCIP_CALL( SCIPallocBufferArray(scip, &oldobjvals, ncols) );
    2217 SCIP_CALL( SCIPallocCleanBufferArray(scip, &prod, ncols) );
    2218 *objvecsdiffer = FALSE;
    2219
    2220 /* find the product of Lagrangian multipliers and cut coefficients */
    2221 for( i = 0; i < ncuts; i++ )
    2222 {
    2223 if( !SCIPisZero(scip, dualvector[i]) )
    2224 {
    2225 assert(!(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])) && SCIPisInfinity(scip, SCIProwGetRhs(cuts[i]))));
    2226 assert(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])));
    2227 assert(!SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])));
    2228
    2229 cutnnz = SCIProwGetNNonz(cuts[i]);
    2230 assert(cutnnz <= ncols);
    2231 cutvals = SCIProwGetVals(cuts[i]);
    2232 cutcols = SCIProwGetCols(cuts[i]);
    2233
    2234 for( j = 0; j < cutnnz; ++j )
    2235 {
    2236 collppos = SCIPcolGetLPPos(cutcols[j]);
    2237 assert(collppos >= 0);
    2238 assert(collppos <= ncols);
    2239
    2240 prod[collppos] += dualvector[i] * cutvals[j];
    2241 }
    2242 }
    2243 }
    2244
    2245 /* change objective coefficients */
    2246 for( i = 0; i < ncols; i++ )
    2247 {
    2248 var = SCIPcolGetVar(cols[i]);
    2249 oldobjvals[i] = SCIPgetVarObjDive(scip, var);
    2250 objvals[i] = origobjcoefs[i] + prod[i];
    2251
    2252 SCIP_CALL( SCIPchgVarObjDive(scip, var, objvals[i]) );
    2253
    2254 /* identify if the updated objective vector is indeed different from the previous one */
    2255 if( !(*objvecsdiffer) && !SCIPisEQ(scip, oldobjvals[i], objvals[i]) )
    2256 *objvecsdiffer = TRUE;
    2257 }
    2258
    2259 for( i = 0; i < ncols; i++)
    2260 prod[i] = 0.0;
    2261
    2262 /* free memory */
    2263 SCIPfreeCleanBufferArray(scip, &prod);
    2264 SCIPfreeBufferArray(scip, &oldobjvals);
    2265 SCIPfreeBufferArray(scip, &objvals);
    2266
    2267 return SCIP_OKAY;
    2268}
    2269
    2270/** add GMI cuts to the objective function of the Lagrangian dual problem by introducing new Lagrangian multipliers */
    2271static
    2272SCIP_RETCODE addGMICutsAsSoftConss(
    2273 SCIP_Real* dualvector, /**< Lagrangian multipliers vector */
    2274 int ngeneratedcuts, /**< number of cuts generated so far in the current separation round */
    2275 int* naddedcuts, /**< number of cuts added so far in the current separation round to the Lagrangian dual problem
    2276 * upon penalization */
    2277 int* nnewaddedsoftcuts /**< number of cuts added newly to the Lagrangian dual problem upon penalization */
    2278 )
    2279{
    2280 int i;
    2281
    2282 assert(*naddedcuts <= ngeneratedcuts);
    2283
    2284 /* set the initial penalty of the newly penalized cuts as zero */
    2285 for( i = *naddedcuts; i < ngeneratedcuts; i++ )
    2286 dualvector[i] = 0.0;
    2287
    2288 *nnewaddedsoftcuts = ngeneratedcuts - *naddedcuts;
    2289 *naddedcuts = ngeneratedcuts;
    2290
    2291 return SCIP_OKAY;
    2292}
    2293
    2294/** solve the Lagrangian dual problem */
    2295static
    2296SCIP_RETCODE solveLagrangianDual(
    2297 SCIP* scip, /**< SCIP data structure */
    2298 SCIP_SEPA* sepa, /**< pointer to the separator */
    2299 SCIP_SEPADATA* sepadata, /**< separator data structure */
    2300 SCIP_SOL* sol, /**< data structure to store an LP solution upon solving a Lagrangian dual problem with
    2301 * fixed Lagrangian multipliers */
    2302 SCIP_Real* solvals, /**< values of the LP solution obtained upon solving a Lagrangian dual problem with fixed
    2303 * Lagrangian multipliers */
    2304 int mainiternum, /**< iteration number of the outer loop of the relax-and-cut algorithm */
    2305 SCIP_Real ubparam, /**< estimate of the optimal Lagrangian dual value */
    2306 int depth, /**< depth of the current node in the tree */
    2307 SCIP_Bool allowlocal, /**< should locally valid cuts be generated? */
    2308 int nmaxgeneratedperroundcuts,/**< maximal number of cuts allowed to generate per separation round */
    2309 SCIP_Real* origobjcoefs, /**< original objective function coefficients of the node linear relaxation */
    2310 SCIP_Real origobjoffset, /**< original objective function offset of the node linear relaxation */
    2311 SCIP_Real* dualvector, /**< Lagrangian multipliers vector */
    2312 int* nsoftcuts, /**< number of generated cuts that were penalized and added to the Lagrangian dual problem */
    2313 SCIP_ROW** generatedcurrroundcuts, /**< cuts generated in the current separation round */
    2314 SCIP_Real* generatedcutefficacies, /**< array of generated cut efficacies w.r.t. the respective LP bases used for cut
    2315 * generations */
    2316 int* ngeneratedcutsperiter, /**< number of cuts generated per subgradient iteration in the current separation round */
    2317 int* ngeneratedcurrroundcuts, /**< number of cuts generated so far in the current separation round */
    2318 int* ncurrroundlpiters, /**< number of LP iterations taken for solving Lagrangian dual problems with fixed
    2319 * multipliers in the current separator round */
    2320 SCIP_Bool* cutoff, /**< should the current node be cutoff? */
    2321 SCIP_Real* bestlagrangianval, /**< best Lagrangian value found so far */
    2322 SCIP_Real* bestdualvector, /**< Lagrangian multipliers corresponding to the best Lagrangian value found so far */
    2323 int* bestdualvectorlen, /**< length of the Lagrangian multipliers corresponding to the best Lagrangian value
    2324 * found so far */
    2325 int* nbestdualupdates, /**< number of best Lagrangian values found so far */
    2326 int* totaliternum /**< total number of iterations of the relax-and-cut algorithm performed so far */
    2327 )
    2328{
    2329 SCIP_Real* subgradient;
    2330 SCIP_Real muparam;
    2331 SCIP_Real steplength;
    2332 SCIP_Real objval;
    2333 SCIP_Real lagrangianval;
    2334 SCIP_Real* lagrangianvals;
    2335 SCIP_Real avglagrangianval;
    2336 SCIP_Real maxsoftcutviol;
    2337 SCIP_Real maxnzsubgradientdualprod;
    2338 SCIP_Real maxviolscore;
    2339 SCIP_Real maxviolscoreold;
    2340 SCIP_Real nviolscore;
    2341 SCIP_Real nviolscoreold;
    2342 SCIP_Real scoreweight;
    2343 SCIP_Real ballradius;
    2344 SCIP_Bool solfound;
    2345 SCIP_Bool backtrack;
    2346 SCIP_Bool terminate;
    2347 SCIP_Bool subgradientzero;
    2348 SCIP_Bool objvecsdiffer;
    2349 SCIP_Bool dualvecsdiffer;
    2350 SCIP_Bool solvelp;
    2351 int ncurrroundlpiterslast;
    2352 int nlpiters;
    2353 int nnewaddedsoftcuts;
    2354 int nsoftcutviols;
    2355 int nnzsubgradientdualprod;
    2356 int i;
    2357 int j;
    2358
    2359 SCIP_CALL( SCIPallocBufferArray(scip, &lagrangianvals, sepadata->nmaxsubgradientiters) );
    2360 SCIP_CALL( SCIPallocCleanBufferArray(scip, &subgradient, nmaxgeneratedperroundcuts) );
    2361
    2362 muparam = sepadata->muparaminit;
    2363 steplength = 0.0;
    2364 objval = 0.0;
    2365 avglagrangianval = 0.0;
    2366 maxsoftcutviol = 0.0;
    2367 maxnzsubgradientdualprod = 0.0;
    2368 maxviolscore = 0.0;
    2369 nviolscore = 0.0;
    2370 scoreweight = 1.0;
    2371 ballradius = sepadata->radiusinit;
    2372 nsoftcutviols = 0;
    2373 nnzsubgradientdualprod = 0;
    2374 terminate = FALSE;
    2375 objvecsdiffer = FALSE;
    2376 solvelp = TRUE;
    2377
    2378 /* update objective vector based on input Lagrangian multipliers */
    2379 if( *nsoftcuts > 0 )
    2380 {
    2381 SCIP_CALL( updateObjectiveVector(scip, dualvector, generatedcurrroundcuts, *nsoftcuts, origobjcoefs, &objvecsdiffer) );
    2382 }
    2383
    2384 /* termination check */
    2385 SCIP_CALL( checkLagrangianDualTermination(sepadata, -1, -1, FALSE, *ngeneratedcurrroundcuts,
    2386 nmaxgeneratedperroundcuts, *ncurrroundlpiters, depth, &terminate) );
    2387
    2388 /* the subgradient algorithm loop */
    2389 for( i = 0; i < sepadata->nmaxsubgradientiters && !SCIPisStopped(scip) && !terminate; i++ )
    2390 {
    2391 solfound = FALSE;
    2392 subgradientzero = FALSE;
    2393 objvecsdiffer = FALSE;
    2394 dualvecsdiffer = FALSE;
    2395 nnewaddedsoftcuts = 0;
    2396 scoreweight *= sepadata->radiusupdateweight;
    2397
    2398 ncurrroundlpiterslast = *ncurrroundlpiters;
    2399 if( solvelp )
    2400 {
    2401 /* solve Lagrangian dual for fixed Lagrangian multipliers */
    2402 SCIP_CALL( solveLagromoryLP(scip, sepadata, depth, origobjoffset, &solfound, sol, solvals, &objval,
    2403 ncurrroundlpiters) );
    2404 }
    2405 nlpiters = *ncurrroundlpiters - ncurrroundlpiterslast;
    2406
    2407 /* if an optimal solution has been found, then generate cuts and do other operations */
    2408 if( solfound )
    2409 {
    2410 /* generate GMI cuts if a new basis solution is found */
    2411 if( (nlpiters >= 1) && (i % sepadata->cutgenfreq == 0) )
    2412 {
    2413 int ngeneratednewcuts = 0;
    2414 SCIP_CALL( generateGMICuts(scip, sepa, sepadata, mainiternum, i, sol, solvals,
    2415 nmaxgeneratedperroundcuts, allowlocal, generatedcurrroundcuts, generatedcutefficacies,
    2416 *ngeneratedcurrroundcuts, &ngeneratednewcuts, depth, cutoff));
    2417 sepadata->ntotalcuts += ngeneratednewcuts;
    2418 *ngeneratedcurrroundcuts += ngeneratednewcuts;
    2419 ngeneratedcutsperiter[mainiternum * sepadata->nmaxsubgradientiters + i + 1] = ngeneratednewcuts;
    2420 }
    2421
    2422 /* update subgradient, i.e., find the residuals of the penalized cuts, and determine various violations */
    2423 updateSubgradient(scip, sol, generatedcurrroundcuts, *nsoftcuts, subgradient, dualvector, &subgradientzero,
    2424 &nsoftcutviols, &maxsoftcutviol, &nnzsubgradientdualprod, &maxnzsubgradientdualprod);
    2425
    2426 /* calculate Lagrangian value for the fixed Lagrangian multipliers, and update best and avg values */
    2427 updateLagrangianValue(scip, objval, dualvector, generatedcurrroundcuts, *nsoftcuts, &lagrangianval);
    2428 if( SCIPisPositive(scip, lagrangianval - *bestlagrangianval) )
    2429 {
    2430 *bestlagrangianval = lagrangianval;
    2431
    2432 for( j = 0; j < *nsoftcuts; j++ )
    2433 bestdualvector[j] = dualvector[j];
    2434
    2435 *bestdualvectorlen = *nsoftcuts;
    2436 (*nbestdualupdates)++;
    2437 }
    2438 lagrangianvals[i] = lagrangianval;
    2439 if( i < sepadata->nmaxlagrangianvalsforavg )
    2440 avglagrangianval = (avglagrangianval * i + lagrangianval)/(i+1);
    2441 else
    2442 {
    2443 avglagrangianval = (avglagrangianval * sepadata->nmaxlagrangianvalsforavg -
    2444 lagrangianvals[i - sepadata->nmaxlagrangianvalsforavg] +
    2445 lagrangianval)/(sepadata->nmaxlagrangianvalsforavg);
    2446 }
    2447
    2448 /* if the subgradient vector is non-zero, then update the mu parameter and the Lagrangian multipliers */
    2449 if( !subgradientzero )
    2450 {
    2451 /* update mu param */
    2452 SCIP_CALL( updateMuSteplengthParam(scip, sepadata, i, ubparam, lagrangianvals, *bestlagrangianval, avglagrangianval,
    2453 &muparam, &backtrack) );
    2454
    2455 /* update step length */
    2456 updateStepLength(scip, muparam, ubparam, lagrangianval, subgradient, *nsoftcuts, &steplength);
    2457
    2458 /* update scores to determine how to update the stabilization ball radius */
    2459 maxviolscoreold = maxviolscore;
    2460 nviolscoreold = nviolscore;
    2461 maxviolscore = (1.0 - scoreweight) * maxsoftcutviol + scoreweight * maxnzsubgradientdualprod;
    2462 nviolscore = (1.0 - scoreweight) * nsoftcutviols + scoreweight * nnzsubgradientdualprod;
    2463
    2464 /* update Lagrangian multipliers */
    2465 SCIP_CALL( updateDualVector(scip, sepadata, dualvector, bestdualvector, *bestdualvectorlen,
    2466 *nbestdualupdates, i, *totaliternum, steplength, subgradient, *nsoftcuts, backtrack, maxviolscore,
    2467 maxviolscoreold, nviolscore, nviolscoreold, nlpiters, &dualvecsdiffer, &ballradius) );
    2468
    2469 /* update objective vector based on updated Lagrangian multipliers */
    2470 if( dualvecsdiffer )
    2471 {
    2472 SCIP_CALL( updateObjectiveVector(scip, dualvector, generatedcurrroundcuts, *nsoftcuts, origobjcoefs, &objvecsdiffer) );
    2473 }
    2474 }
    2475 /* if the subgradient vector if zero, then simply mark that the Lagrangian multipliers and the objective
    2476 * function of the Lagrangian dual did not change */
    2477 else
    2478 {
    2479 dualvecsdiffer = FALSE;
    2480 objvecsdiffer = FALSE;
    2481 }
    2482
    2483 /* add generated GMI cuts to the objective function of the Lagrangian dual problem by introducing new
    2484 * Lagrangian multipliers */
    2485 if( (i % sepadata->cutaddfreq == 0) || (!dualvecsdiffer && !objvecsdiffer &&
    2486 (*ngeneratedcurrroundcuts - *nsoftcuts > 0)) )
    2487 {
    2488 SCIP_CALL( addGMICutsAsSoftConss(dualvector, *ngeneratedcurrroundcuts, nsoftcuts, &nnewaddedsoftcuts) );
    2489 }
    2490 }
    2491 else
    2492 {
    2493 /* add any remaining generated GMI cuts to the objective function of the Lagrangian dual problem by introducing
    2494 * new Lagrangian multipliers */
    2495 if( (*ngeneratedcurrroundcuts - *nsoftcuts) > 0 )
    2496 {
    2497 SCIP_CALL( addGMICutsAsSoftConss(dualvector, *ngeneratedcurrroundcuts, nsoftcuts, &nnewaddedsoftcuts) );
    2498 }
    2499
    2500 solvelp = FALSE;
    2501 }
    2502
    2503 /* termination check */
    2504 SCIP_CALL( checkLagrangianDualTermination(sepadata, nnewaddedsoftcuts, *ngeneratedcurrroundcuts - *nsoftcuts,
    2505 objvecsdiffer, *ngeneratedcurrroundcuts, nmaxgeneratedperroundcuts, *ncurrroundlpiters, depth,
    2506 &terminate) );
    2507
    2508 (*totaliternum)++;
    2509 }
    2510
    2511 /* add any remaining generated GMI cuts to the objective function of the Lagrangian dual problem by introducing new
    2512 * Lagrangian multipliers */
    2513 if( (*ngeneratedcurrroundcuts - *nsoftcuts) > 0 )
    2514 {
    2515 SCIP_CALL( addGMICutsAsSoftConss(dualvector, *ngeneratedcurrroundcuts, nsoftcuts, &nnewaddedsoftcuts) );
    2516 }
    2517
    2518 /* free memory */
    2519 for( i = 0; i < nmaxgeneratedperroundcuts; i++)
    2520 subgradient[i] = 0.0;
    2521
    2522 SCIPfreeCleanBufferArray(scip, &subgradient);
    2523 SCIPfreeBufferArray(scip, &lagrangianvals);
    2524
    2525 return SCIP_OKAY;
    2526}
    2527
    2528/** generates initial cut pool before solving the Lagrangian dual */
    2529static
    2530SCIP_RETCODE generateInitCutPool(
    2531 SCIP* scip, /**< SCIP data structure */
    2532 SCIP_SEPA* sepa, /**< separator */
    2533 SCIP_SEPADATA* sepadata, /**< separator data structure */
    2534 int mainiternum, /**< iteration number of the outer loop of the relax-and-cut algorithm */
    2535 SCIP_SOL* sol, /**< LP solution to be used for cut generation */
    2536 SCIP_Real* solvals, /**< values of the LP solution to be used for cut generation */
    2537 int nmaxgeneratedperroundcuts,/**< maximal number of cuts allowed to generate per separation round */
    2538 SCIP_Bool allowlocal, /**< should locally valid cuts be generated? */
    2539 SCIP_ROW** generatedcurrroundcuts, /**< cuts generated in the current separation round */
    2540 SCIP_Real* generatedcutefficacies, /**< array of generated cut efficacies w.r.t. the respective LP bases used for cut
    2541 * generations */
    2542 int* ngeneratedcutsperiter, /**< number of cuts generated per subgradient iteration in the current separation round */
    2543 int* ngeneratedcurrroundcuts, /**< number of cuts generated so far in the current separation round */
    2544 int depth, /**< depth of the current node in the tree */
    2545 SCIP_Bool* cutoff /**< should the current node be cutoff? */
    2546 )
    2547{
    2548 int ngeneratednewcuts;
    2549
    2550 ngeneratednewcuts = 0;
    2551
    2552 /* generate initial set of cuts */
    2553 SCIP_CALL( generateGMICuts(scip, sepa, sepadata, mainiternum, -1, sol, solvals, nmaxgeneratedperroundcuts,
    2554 allowlocal, generatedcurrroundcuts, generatedcutefficacies, *ngeneratedcurrroundcuts, &ngeneratednewcuts,
    2555 depth, cutoff) );
    2556
    2557 /* update certain statistics */
    2558 sepadata->ntotalcuts += ngeneratednewcuts;
    2559 *ngeneratedcurrroundcuts += ngeneratednewcuts;
    2560 ngeneratedcutsperiter[sepadata->nmaxsubgradientiters * mainiternum] = ngeneratednewcuts;
    2561
    2562 return SCIP_OKAY;
    2563}
    2564
    2565/** add cuts to SCIP */
    2566static
    2567SCIP_RETCODE addCuts(
    2568 SCIP* scip, /**< SCIP data structure */
    2569 SCIP_SEPADATA* sepadata, /**< separator data structure */
    2570 SCIP_ROW** cuts, /**< cuts generated so far in the current separation round */
    2571 int ncuts, /**< number of cuts generated so far in the current separation round */
    2572 SCIP_Longint maxdnom, /**< maximum denominator in the rational representation of cuts */
    2573 SCIP_Real maxscale, /**< maximal scale factor to scale the cuts to integral values */
    2574 int* naddedcuts, /**< number of cuts added to either global cutpool or sepastore */
    2575 SCIP_Bool* cutoff /**< should the current node be cutoff? */
    2576 )
    2577{
    2578 SCIP_ROW* cut;
    2579 SCIP_Bool madeintegral;
    2580 int i;
    2581
    2582 assert(scip != NULL);
    2583 assert(sepadata != NULL);
    2584 assert(naddedcuts != NULL);
    2585 assert(cutoff != NULL);
    2586
    2587 *cutoff = FALSE;
    2588 madeintegral = FALSE;
    2589
    2590 for( i = 0; i < ncuts && !*cutoff; i++ )
    2591 {
    2592 cut = cuts[i];
    2593
    2594 if( SCIProwGetNNonz(cut) == 1 )
    2595 {
    2596 /* Add the bound change as cut to avoid that the LP gets modified. This would mean that the LP is not flushed
    2597 * and the method SCIPgetLPBInvRow() fails; SCIP internally will apply this bound change automatically. */
    2598 SCIP_CALL( SCIPaddRow(scip, cut, TRUE, cutoff) );
    2599 ++(*naddedcuts);
    2600 }
    2601 else
    2602 {
    2603 if( sepadata->makeintegral && SCIPgetRowNumIntCols(scip, cut) == SCIProwGetNNonz(cut) )
    2604 {
    2605 /* try to scale the cut to integral values */
    2606 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
    2607 maxdnom, maxscale, MAKECONTINTEGRAL, &madeintegral) );
    2608
    2609 /* if RHS = plus infinity (due to scaling), the cut is useless, so we are not adding it */
    2610 if( madeintegral && SCIPisInfinity(scip, SCIProwGetRhs(cut)) )
    2611 return SCIP_OKAY;
    2612 }
    2613
    2614 if( SCIPisCutNew(scip, cut) )
    2615 {
    2616 /* add global cuts which are not implicit bound changes to the cut pool */
    2617 if( !SCIProwIsLocal(cut) )
    2618 {
    2619 if( sepadata->delayedcuts )
    2620 {
    2621 SCIP_CALL( SCIPaddDelayedPoolCut(scip, cut) );
    2622 }
    2623 else
    2624 {
    2625 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
    2626 }
    2627 }
    2628 else
    2629 {
    2630 /* local cuts we add to the sepastore */
    2631 SCIP_CALL( SCIPaddRow(scip, cut, sepadata->forcecuts, cutoff) );
    2632 }
    2633 ++(*naddedcuts);
    2634 }
    2635 }
    2636 }
    2637
    2638 return SCIP_OKAY;
    2639}
    2640
    2641/** check different termination criteria */
    2642/* @todo nlpssolved criterion? */
    2643static
    2644SCIP_RETCODE checkMainLoopTermination(
    2645 SCIP_SEPADATA* sepadata, /**< separator data structure */
    2646 SCIP_Bool cutoff, /**< should the current node be cutoff? */
    2647 SCIP_Bool dualvecsdiffer, /**< whether the updated Lagrangian multipliers differ from the old one */
    2648 int ngeneratedcurrroundcuts, /**< number of cuts generated in the current separation round */
    2649 int nsoftcuts, /**< number of generated cuts that were penalized and added to the Lagrangian dual problem */
    2650 int nmaxgeneratedperroundcuts, /**< maximal number of cuts allowed to generate per separation round */
    2651 int ncurrroundlpiters, /**< number of LP iterations taken for solving Lagrangian dual problems with fixed
    2652 * multipliers in the current separator round */
    2653 int depth, /**< depth of the current node in the tree */
    2654 SCIP_Bool* terminate /**< whether to terminate the relax-and-cut algorithm */
    2655 )
    2656{
    2657 *terminate = FALSE;
    2658
    2659 /* check if the node has been identified to be cutoff */
    2660 if( cutoff )
    2661 *terminate = TRUE;
    2662
    2663 /* check if the Lagrangian multipliers do not differ from the previous iteration and no new cuts exist for penalizing */
    2664 if( !dualvecsdiffer && (ngeneratedcurrroundcuts == nsoftcuts) )
    2665 *terminate = TRUE;
    2666
    2667 /* check if allowed number of cuts in this separation round have already been generated */
    2668 if( ngeneratedcurrroundcuts >= nmaxgeneratedperroundcuts )
    2669 *terminate = TRUE;
    2670
    2671 /* check if allowed number of cuts in the tree have already been generated */
    2672 if( sepadata->ntotalcuts >= sepadata->nmaxtotalcuts )
    2673 *terminate = TRUE;
    2674
    2675 /* check if allowed number of simplex iterations in this separation round have already been used up */
    2676 if( (sepadata->nmaxperroundlpiters >= 0) && (ncurrroundlpiters >= sepadata->nmaxperroundlpiters) )
    2677 *terminate = TRUE;
    2678
    2679 /* check if allowed number of simplex iterations in the root node have already been used up */
    2680 if( (depth == 0) && (sepadata->nmaxrootlpiters >= 0) && (sepadata->nrootlpiters >= sepadata->nmaxrootlpiters) )
    2681 *terminate = TRUE;
    2682
    2683 /* check if allowed number of simplex iterations in the tree have already been used up */
    2684 if( (sepadata->nmaxtotallpiters >= 0) && (sepadata->ntotallpiters >= sepadata->nmaxtotallpiters) )
    2685 *terminate = TRUE;
    2686
    2687 return SCIP_OKAY;
    2688}
    2689
    2690/** searches and tries to add Lagromory cuts */
    2691static
    2692SCIP_RETCODE separateCuts(
    2693 SCIP* scip, /**< SCIP data structure */
    2694 SCIP_SEPA* sepa, /**< separator */
    2695 SCIP_SEPADATA* sepadata, /**< separator data structure */
    2696 SCIP_Real ubparam, /**< estimate of the optimal Lagrangian dual value */
    2697 int depth, /**< depth of the current node in the tree */
    2698 SCIP_Bool allowlocal, /**< should locally valid cuts be generated? */
    2699 SCIP_RESULT* result /**< final result of the separation round */
    2700 )
    2701{
    2702 SCIP_ROW** generatedcurrroundcuts;
    2703 SCIP_ROW** aggregatedcurrroundcuts;
    2704 SCIP_Real* generatedcutefficacies;
    2705 SCIP_Bool solfound;
    2706 SCIP_SOL* softcutslpsol;
    2707 SCIP_Real* softcutslpsolvals;
    2708 SCIP_SOL* hardcutslpsol;
    2709 SCIP_Real* hardcutslpsolvals;
    2710 SCIP_Real* dualsol;
    2711 SCIP_Real* dualvector;
    2712 SCIP_Real* bestdualvector;
    2713 SCIP_Real bestlagrangianval;
    2714 SCIP_Real* origobjcoefs;
    2715 SCIP_Real origobjoffset;
    2716 SCIP_Real objval;
    2717 SCIP_Real maxscale;
    2718 SCIP_Longint maxdnom;
    2719 SCIP_Bool cutoff;
    2720 SCIP_Bool cutoff2;
    2721 SCIP_Bool dualvecsdiffer;
    2722 SCIP_Bool terminate;
    2723 SCIP_COL** cols;
    2724
    2725 int* ngeneratedcutsperiter;
    2726 int bestdualvectorlen;
    2727 int nbestdualupdates;
    2728 int totaliternum;
    2729 int* cutindsperm;
    2730 int nprocessedcuts;
    2731 int ncols;
    2732 int nrows;
    2733 int ngeneratedcurrroundcuts;
    2734 int nselectedcurrroundcuts;
    2735 int nselectedcuts;
    2736 int naddedcurrroundcuts;
    2737 int naggregatedcurrroundcuts;
    2738 int nmaxgeneratedperroundcuts;
    2739 int ncurrroundlpiters;
    2740 int nsoftcuts;
    2741 int nsoftcutsold;
    2742 int maxdepth;
    2743 int i;
    2744 int j;
    2745
    2746 assert(*result == SCIP_DIDNOTRUN);
    2747 assert(sepadata != NULL);
    2748 sepadata->ncalls = SCIPsepaGetNCalls(sepa);
    2749 objval = SCIPinfinity(scip);
    2750 bestlagrangianval = -SCIPinfinity(scip);
    2751 bestdualvectorlen = 0;
    2752 nbestdualupdates = 0;
    2753 totaliternum = 0;
    2754 ngeneratedcurrroundcuts = 0;
    2755 naddedcurrroundcuts = 0;
    2756 naggregatedcurrroundcuts = 0;
    2757 ncurrroundlpiters = 0;
    2758 nsoftcuts = 0;
    2759 solfound = FALSE;
    2760 cutoff = FALSE;
    2761 cutoff2 = FALSE;
    2762 terminate = FALSE;
    2763
    2764 SCIPdebugMsg(scip, "Separating cuts...\n");
    2765
    2766 /* initialize the LP that will be used to solve the Lagrangian dual with fixed Lagrangian multipliers */
    2767 SCIP_CALL( createLPWithSoftCuts(scip, sepadata) );
    2768 /* create the LP that represents the node relaxation including all the generated cuts in this separator */
    2769 SCIP_CALL( createLPWithHardCuts(scip, sepadata, NULL, 0) );
    2770
    2771 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    2772 nrows = SCIPgetNLPRows(scip);
    2773
    2774 /* get the maximal number of cuts allowed in a separation round */
    2775 nmaxgeneratedperroundcuts = ((depth == 0) ? sepadata->nmaxperroundcutsroot : sepadata->nmaxperroundcuts);
    2776
    2777 /* allocate memory */
    2778 SCIP_CALL( SCIPallocBufferArray(scip, &generatedcurrroundcuts, nmaxgeneratedperroundcuts) );
    2779 SCIP_CALL( SCIPallocBufferArray(scip, &aggregatedcurrroundcuts, nmaxgeneratedperroundcuts) );
    2780 SCIP_CALL( SCIPallocBufferArray(scip, &generatedcutefficacies, nmaxgeneratedperroundcuts) );
    2781 SCIP_CALL( SCIPallocBufferArray(scip, &cutindsperm, nmaxgeneratedperroundcuts) );
    2782 SCIP_CALL( SCIPallocCleanBufferArray(scip, &ngeneratedcutsperiter, sepadata->nmaxmainiters *
    2783 (sepadata->nmaxsubgradientiters + 1)) );
    2784 SCIP_CALL( SCIPallocCleanBufferArray(scip, &dualsol, nrows + nmaxgeneratedperroundcuts) );
    2785 SCIP_CALL( SCIPallocCleanBufferArray(scip, &dualvector, nmaxgeneratedperroundcuts) );
    2786 SCIP_CALL( SCIPallocCleanBufferArray(scip, &bestdualvector, nmaxgeneratedperroundcuts) );
    2787 SCIP_CALL( SCIPallocBufferArray(scip, &softcutslpsolvals, ncols) );
    2788 SCIP_CALL( SCIPcreateSol(scip, &softcutslpsol, NULL) );
    2789 SCIP_CALL( SCIPallocBufferArray(scip, &hardcutslpsolvals, ncols) );
    2790 SCIP_CALL( SCIPcreateSol(scip, &hardcutslpsol, NULL) );
    2791 SCIP_CALL( SCIPallocBufferArray(scip, &origobjcoefs, ncols) );
    2792
    2793 /* store current objective function */
    2794 for( i = 0; i < ncols; i++ )
    2795 origobjcoefs[i] = SCIPcolGetObj(cols[i]);
    2796
    2797 origobjoffset = SCIPgetTransObjoffset(scip);
    2798
    2799 /* solve node LP relaxation to have an initial simplex tableau */
    2800 SCIP_CALL( solveLagromoryLP(scip, sepadata, depth, origobjoffset, &solfound, softcutslpsol, softcutslpsolvals, &objval,
    2801 &ncurrroundlpiters));
    2802
    2803 /* generate initial cut pool */
    2804 SCIP_CALL( generateInitCutPool(scip, sepa, sepadata, 0, softcutslpsol, softcutslpsolvals, nmaxgeneratedperroundcuts, allowlocal,
    2805 generatedcurrroundcuts, generatedcutefficacies, ngeneratedcutsperiter, &ngeneratedcurrroundcuts, depth,
    2806 &cutoff) );
    2807
    2808 /* termination check */
    2809 SCIP_CALL( checkMainLoopTermination(sepadata, cutoff, TRUE, ngeneratedcurrroundcuts, nsoftcuts,
    2810 nmaxgeneratedperroundcuts, ncurrroundlpiters, depth, &terminate) );
    2811
    2812 /* compute cuts for each integer col with fractional val */
    2813 for( i = 0; i < sepadata->nmaxmainiters && !SCIPisStopped(scip) && !terminate; ++i )
    2814 {
    2815 nsoftcutsold = nsoftcuts;
    2816 nsoftcuts = ngeneratedcurrroundcuts;
    2817 dualvecsdiffer = FALSE;
    2818
    2819 /* solve Lagrangain dual */
    2820 SCIP_CALL( solveLagrangianDual(scip, sepa, sepadata, softcutslpsol, softcutslpsolvals, i, ubparam, depth, allowlocal,
    2821 nmaxgeneratedperroundcuts, origobjcoefs, origobjoffset, dualvector, &nsoftcuts, generatedcurrroundcuts,
    2822 generatedcutefficacies, ngeneratedcutsperiter, &ngeneratedcurrroundcuts, &ncurrroundlpiters, &cutoff,
    2823 &bestlagrangianval, bestdualvector, &bestdualvectorlen, &nbestdualupdates, &totaliternum) );
    2824
    2825 /* @todo filter cuts before adding them to the new LP that was created based on the node relaxation? */
    2826
    2827 /* update the LP representing the node relaxation by adding newly generated cuts */
    2828 if( !cutoff && (ngeneratedcurrroundcuts - nsoftcutsold > 0) )
    2829 {
    2830 SCIP_CALL( createLPWithHardCuts(scip, sepadata, generatedcurrroundcuts, ngeneratedcurrroundcuts) );
    2831
    2832 /* solve the LP and get relevant information */
    2833 SCIP_CALL( solveLPWithHardCuts(scip, sepadata, &solfound, hardcutslpsol, hardcutslpsolvals) );
    2834
    2835 /* if primal solution is found, then pass it to trysol heuristic */
    2836 /* @note if trysol heuristic is was not present, then the solution found above, which can potentially be a MIP
    2837 * primal feasible solution, will go to waste.
    2838 */
    2839 if( solfound && sepadata->heurtrysol != NULL )
    2840 {
    2841 SCIP_CALL( SCIPheurPassSolTrySol(scip, sepadata->heurtrysol, hardcutslpsol) );
    2842 }
    2843
    2844 /* if dual feasible, then fetch dual solution and reset Lagrangian multipliers based on it. otherwise, retain the
    2845 * Lagrangian multipliers and simply initialize the new multipliers to zeroes. */
    2846 if( SCIPlpiWasSolved(sepadata->lpiwithhardcuts) && SCIPlpiIsDualFeasible(sepadata->lpiwithhardcuts) )
    2847 {
    2848 SCIP_CALL( SCIPlpiGetSol(sepadata->lpiwithhardcuts, NULL, NULL, dualsol, NULL, NULL) );
    2849 SCIP_CALL( updateDualVector(scip, sepadata, dualvector, &(dualsol[nrows]),
    2850 ngeneratedcurrroundcuts, 0, -1, -1, 0.0, NULL, ngeneratedcurrroundcuts, TRUE, 0.0, 0.0, 0.0, 0.0, -1,
    2851 &dualvecsdiffer, NULL) );
    2852 }
    2853 else
    2854 {
    2855 SCIP_CALL( updateDualVector(scip, sepadata, dualvector, dualvector, nsoftcuts, 0, -1, -1, 0.0, NULL,
    2856 ngeneratedcurrroundcuts, TRUE, 0.0, 0.0, 0.0, 0.0, -1, &dualvecsdiffer, NULL) );
    2857 }
    2858 }
    2859
    2860 /* termination check */
    2861 SCIP_CALL( checkMainLoopTermination(sepadata, cutoff, dualvecsdiffer, ngeneratedcurrroundcuts, nsoftcuts,
    2862 nmaxgeneratedperroundcuts, ncurrroundlpiters, depth, &terminate) );
    2863 }
    2864
    2865 /* set the maximal denominator in rational representation of gomory cut and the maximal scale factor to
    2866 * scale resulting cut to integral values to avoid numerical instabilities
    2867 */
    2868 /* @todo find better but still stable gomory cut settings: look at dcmulti, gesa3, khb0525, misc06, p2756 */
    2869 /* @note above todo was copied from sepa_gomory.c. So, if gomory code is changed, same changes can be done here. */
    2870 maxdepth = SCIPgetMaxDepth(scip);
    2871 if( depth == 0 )
    2872 {
    2873 maxdnom = 1000;
    2874 maxscale = 1000.0;
    2875 }
    2876 else if( depth <= maxdepth/4 )
    2877 {
    2878 maxdnom = 1000;
    2879 maxscale = 1000.0;
    2880 }
    2881 else if( depth <= maxdepth/2 )
    2882 {
    2883 maxdnom = 100;
    2884 maxscale = 100.0;
    2885 }
    2886 else
    2887 {
    2888 maxdnom = 10;
    2889 maxscale = 10.0;
    2890 }
    2891
    2892 /* filter cuts by calling cut selection algorithms and add cuts accordingly */
    2893 /* @todo an idea is to filter cuts after every main iter */
    2894 /* @todo we can remove !cutoff criterion by adding forcedcuts */
    2895 if( !cutoff && (ngeneratedcurrroundcuts > 0) )
    2896 {
    2897 if( SCIPisGE(scip, sepadata->cutsfilterfactor, 1.0) )
    2898 {
    2899 nselectedcurrroundcuts = ngeneratedcurrroundcuts;
    2900 SCIP_CALL( addCuts(scip, sepadata, generatedcurrroundcuts, nselectedcurrroundcuts, maxdnom, maxscale,
    2901 &naddedcurrroundcuts, &cutoff2) );
    2902 cutoff = cutoff2;
    2903 }
    2904 else if( SCIPisPositive(scip, sepadata->cutsfilterfactor) )
    2905 {
    2906 nprocessedcuts = 0;
    2907 for( i = 0; i < sepadata->nmaxmainiters * (sepadata->nmaxsubgradientiters + 1); i++ )
    2908 {
    2909 if( ngeneratedcutsperiter[i] != 0 )
    2910 {
    2911 for( j = 0; j < ngeneratedcutsperiter[i]; j++ )
    2912 cutindsperm[j] = j + nprocessedcuts;
    2913
    2914 /* sort cut efficacies by fractionality */
    2915 SCIPsortDownRealInt(&generatedcutefficacies[nprocessedcuts], cutindsperm, ngeneratedcutsperiter[i]);
    2916
    2917 nselectedcuts = (int)SCIPceil(scip, sepadata->cutsfilterfactor * ngeneratedcutsperiter[i]);
    2918
    2919 SCIP_CALL( addCuts(scip, sepadata, &generatedcurrroundcuts[nprocessedcuts], nselectedcuts, maxdnom,
    2920 maxscale, &naddedcurrroundcuts, &cutoff2) );
    2921 cutoff = cutoff2;
    2922
    2923 nprocessedcuts += ngeneratedcutsperiter[i];
    2924 }
    2925 }
    2926 }
    2927 }
    2928 else if( ngeneratedcurrroundcuts > 0 )
    2929 {
    2930 nselectedcurrroundcuts = ngeneratedcurrroundcuts;
    2931 SCIP_CALL( addCuts(scip, sepadata, generatedcurrroundcuts, nselectedcurrroundcuts, maxdnom, maxscale,
    2932 &naddedcurrroundcuts, &cutoff2) );
    2933 }
    2934
    2935 /* add an aggregated cut based on best Lagrangian multipliers */
    2936 if( sepadata->aggregatecuts && (ngeneratedcurrroundcuts > 0) && (bestdualvectorlen > 0) )
    2937 {
    2938 assert(bestdualvectorlen <= ngeneratedcurrroundcuts);
    2939 SCIP_CALL( aggregateGeneratedCuts(scip, sepa, sepadata, generatedcurrroundcuts, bestdualvector, bestdualvectorlen,
    2940 aggregatedcurrroundcuts, &naggregatedcurrroundcuts, &cutoff2) );
    2941 cutoff = (!cutoff ? cutoff2 : cutoff);
    2942 if( naggregatedcurrroundcuts > 0 )
    2943 {
    2944 SCIP_CALL( addCuts(scip, sepadata, aggregatedcurrroundcuts, naggregatedcurrroundcuts, maxdnom, maxscale,
    2945 &naddedcurrroundcuts, &cutoff2) );
    2946 cutoff = (!cutoff ? cutoff2 : cutoff);
    2947 }
    2948 }
    2949
    2950 if( cutoff )
    2951 {
    2952 *result = SCIP_CUTOFF;
    2953 }
    2954 else if( naddedcurrroundcuts > 0 )
    2955 {
    2956 *result = SCIP_SEPARATED;
    2957 }
    2958 else
    2959 {
    2960 *result = SCIP_DIDNOTFIND;
    2961 }
    2962
    2963 /* delete the LP representing the Lagrangian dual problem with fixed Lagrangian multipliers */
    2964 SCIP_CALL( deleteLPWithSoftCuts(scip, sepadata) );
    2965
    2966 /* release the rows in aggregatedcurrroundcuts */
    2967 for( i = 0; i < naggregatedcurrroundcuts; ++i )
    2968 {
    2969 SCIP_CALL( SCIPreleaseRow(scip, &(aggregatedcurrroundcuts[i])) );
    2970 }
    2971
    2972 /* release the rows in generatedcurrroundcuts */
    2973 for( i = 0; i < ngeneratedcurrroundcuts; ++i )
    2974 {
    2975 SCIP_CALL( SCIPreleaseRow(scip, &(generatedcurrroundcuts[i])) );
    2976 }
    2977
    2978 for( i = 0; i < sepadata->nmaxmainiters * (sepadata->nmaxsubgradientiters + 1); i++ )
    2979 ngeneratedcutsperiter[i] = 0;
    2980
    2981 for( i = 0; i < nrows; i++ )
    2982 dualsol[i] = 0.0;
    2983
    2984 for( i = 0; i < nmaxgeneratedperroundcuts; i++ )
    2985 {
    2986 dualsol[nrows + i] = 0.0;
    2987 dualvector[i] = 0.0;
    2988 bestdualvector[i] = 0.0;
    2989 }
    2990
    2991 /* free memory */
    2992 SCIPfreeBufferArray(scip, &origobjcoefs);
    2993 SCIPfreeBufferArray(scip, &hardcutslpsolvals);
    2994 SCIP_CALL( SCIPfreeSol(scip, &hardcutslpsol) );
    2995 SCIPfreeBufferArray(scip, &softcutslpsolvals);
    2996 SCIP_CALL( SCIPfreeSol(scip, &softcutslpsol) );
    2997 SCIPfreeCleanBufferArray(scip, &ngeneratedcutsperiter);
    2998 SCIPfreeBufferArray(scip, &cutindsperm);
    2999 SCIPfreeBufferArray(scip, &generatedcutefficacies);
    3000 SCIPfreeBufferArray(scip, &aggregatedcurrroundcuts);
    3001 SCIPfreeBufferArray(scip, &generatedcurrroundcuts);
    3002 SCIPfreeCleanBufferArray(scip, &dualvector);
    3003 SCIPfreeCleanBufferArray(scip, &bestdualvector);
    3004 SCIPfreeCleanBufferArray(scip, &dualsol);
    3005
    3006 return SCIP_OKAY;
    3007}
    3008
    3009/** creates separator data */
    3010static
    3011SCIP_RETCODE sepadataCreate(
    3012 SCIP* scip, /**< SCIP data structure */
    3013 SCIP_SEPADATA** sepadata /**< separator data structure */
    3014 )
    3015{
    3016 assert(scip != NULL);
    3017 assert(sepadata != NULL);
    3018
    3019 SCIP_CALL( SCIPallocBlockMemory(scip, sepadata) );
    3020 BMSclearMemory(*sepadata);
    3021
    3022 return SCIP_OKAY;
    3023}
    3024
    3025
    3026/*
    3027 * Callback methods of separator
    3028 */
    3029
    3030/** copy method for separator plugins (called when SCIP copies plugins) */
    3031static
    3032SCIP_DECL_SEPACOPY(sepaCopyLagromory)
    3033{ /*lint --e{715}*/
    3034 assert(scip != NULL);
    3035 assert(sepa != NULL);
    3036 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
    3037
    3038 /* call inclusion method of constraint handler */
    3039 SCIP_CALL( SCIPincludeSepaLagromory(scip) );
    3040
    3041 return SCIP_OKAY;
    3042}
    3043
    3044
    3045/** destructor of separator to free user data (called when SCIP is exiting) */
    3046static
    3047SCIP_DECL_SEPAFREE(sepaFreeLagromory)
    3048{
    3049 SCIP_SEPADATA* sepadata;
    3050
    3051 sepadata = SCIPsepaGetData(sepa);
    3052 assert(sepadata != NULL);
    3053
    3054 SCIP_CALL( sepadataFree(scip, &sepadata) );
    3055 SCIPsepaSetData(sepa, NULL);
    3056
    3057 return SCIP_OKAY;
    3058}
    3059
    3060
    3061/** initialization method of separator (called after problem was transformed) */
    3062static
    3063SCIP_DECL_SEPAINIT(sepaInitLagromory)
    3064{
    3065 SCIP_SEPADATA* sepadata;
    3066
    3067 sepadata = SCIPsepaGetData(sepa);
    3068 assert(scip != NULL);
    3069 assert(sepadata != NULL);
    3070
    3071 /* create and initialize random number generator */
    3072 SCIP_CALL( SCIPcreateRandom(scip, &(sepadata->randnumgen), RANDSEED, TRUE) );
    3073
    3074 /* find trysol heuristic */
    3075 if ( sepadata->heurtrysol == NULL )
    3076 sepadata->heurtrysol = SCIPfindHeur(scip, "trysol");
    3077
    3078 return SCIP_OKAY;
    3079}
    3080
    3081/** deinitialization method of separator (called before transformed problem is freed) */
    3082static
    3083SCIP_DECL_SEPAEXIT(sepaExitLagromory)
    3084{ /*lint --e{715}*/
    3085 SCIP_SEPADATA* sepadata;
    3086
    3087 sepadata = SCIPsepaGetData(sepa);
    3088 assert(sepadata != NULL);
    3089
    3090 SCIPfreeRandom(scip, &(sepadata->randnumgen));
    3091
    3092 return SCIP_OKAY;
    3093}
    3094
    3095/** LP solution separation method of separator */
    3096static
    3097SCIP_DECL_SEPAEXECLP(sepaExeclpLagromory)
    3098{
    3099 /*lint --e{715}*/
    3100
    3101 SCIP_SEPADATA* sepadata;
    3102 SCIP_SOL* bestsol;
    3103 SCIP_COL** cols;
    3104 SCIP_COL* col;
    3105 SCIP_VAR* var;
    3106 SCIP_Real ubparam;
    3107 SCIP_Real dualdegeneracyrate;
    3108 SCIP_Real varconsratio;
    3109 SCIP_Real threshold1;
    3110 SCIP_Real threshold2;
    3111 int nrows;
    3112 int ncols;
    3113 int ncalls;
    3114 int runnum;
    3115 int i;
    3116
    3117 assert(sepa != NULL);
    3118 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
    3119 sepadata = SCIPsepaGetData(sepa);
    3120 assert(sepadata != NULL);
    3121
    3122 assert(result != NULL);
    3123 *result = SCIP_DIDNOTRUN;
    3124
    3125 assert(scip != NULL);
    3126
    3127 ncalls = SCIPsepaGetNCallsAtNode(sepa);
    3128 runnum = SCIPgetNRuns(scip);
    3129 dualdegeneracyrate = 0.0;
    3130 varconsratio = 0.0;
    3131
    3132 /* only generate Lagromory cuts if we are not close to terminating */
    3133 if( SCIPisStopped(scip) )
    3134 return SCIP_OKAY;
    3135
    3136 /* only call the separator starting sepadata->minrestart runs */
    3137 if( (sepadata->minrestart >= 1) && (runnum < sepadata->minrestart + 1) )
    3138 return SCIP_OKAY;
    3139
    3140 /* only call the separator a given number of times at each node */
    3141 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
    3142 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
    3143 return SCIP_OKAY;
    3144
    3145 /* only generate cuts if an optimal LP solution is at hand */
    3146 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
    3147 return SCIP_OKAY;
    3148
    3149 /* only generate cuts if the LP solution is basic */
    3150 if( ! SCIPisLPSolBasic(scip) )
    3151 return SCIP_OKAY;
    3152
    3153 /* get LP data */
    3154 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
    3155 assert(cols != NULL);
    3156
    3157 nrows = SCIPgetNLPRows(scip);
    3158
    3159 /* return if LP has no columns or no rows */
    3160 if( ncols == 0 || nrows == 0 )
    3161 return SCIP_OKAY;
    3162
    3163 /* return if dual degeneracy metrics are below threshold values */
    3164 threshold1 = sepadata->dualdegeneracyratethreshold;
    3165 threshold2 = sepadata->varconsratiothreshold;
    3166 SCIP_CALL( SCIPgetLPDualDegeneracy(scip, &dualdegeneracyrate, &varconsratio) );
    3167 if( (dualdegeneracyrate < threshold1) && (varconsratio < threshold2) )
    3168 return SCIP_OKAY;
    3169
    3170 bestsol = SCIPgetBestSol(scip);
    3171 ubparam = 0.0;
    3172
    3173 /* if a MIP primal solution exists, use it to estimate the optimal value of the Lagrangian dual problem */
    3174 if( bestsol != NULL )
    3175 {
    3176 for( i = 0; i < ncols; ++i )
    3177 {
    3178 col = cols[i];
    3179 assert(col != NULL);
    3180
    3181 var = SCIPcolGetVar(col);
    3182
    3183 ubparam += SCIPgetSolVal(scip, bestsol, var) * SCIPcolGetObj(col);
    3184 }
    3185
    3186 ubparam += SCIPgetTransObjoffset(scip);
    3187 }
    3188 /* if a MIP primal solution does not exist, then use the node relaxation's LP solutin to estimate the optimal value
    3189 * of the Lagrangian dual problem
    3190 */
    3191 else
    3192 {
    3193 for( i = 0; i < ncols; ++i )
    3194 {
    3195 col = cols[i];
    3196 assert(col != NULL);
    3197
    3198 ubparam += SCIPcolGetPrimsol(col) * SCIPcolGetObj(col);
    3199 }
    3200
    3201 ubparam += SCIPgetTransObjoffset(scip);
    3202 ubparam *= SCIPisPositive(scip, ubparam) ? sepadata->ubparamposfactor : sepadata->ubparamnegfactor;
    3203 }
    3204
    3205 /* the main separation function of the separator */
    3206 SCIP_CALL( separateCuts(scip, sepa, sepadata, ubparam, depth, (allowlocal && sepadata->allowlocal), result) );
    3207
    3208 return SCIP_OKAY;
    3209}
    3210
    3211
    3212/*
    3213 * separator specific interface methods
    3214 */
    3215
    3216/** creates the Lagromory separator and includes it in SCIP */
    3217SCIP_RETCODE SCIPincludeSepaLagromory(
    3218 SCIP* scip /**< SCIP data structure */
    3219 )
    3220{
    3221 SCIP_SEPADATA* sepadata;
    3222 SCIP_SEPA* sepa;
    3223
    3224 /* create separator data */
    3225 SCIP_CALL( sepadataCreate(scip, &sepadata) );
    3226
    3227 sepadata->heurtrysol = NULL;
    3228
    3229 /* include separator */
    3230 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
    3231 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpLagromory, NULL, sepadata) );
    3232
    3233 assert(sepa != NULL);
    3234
    3235 /* set non fundamental callbacks via setter functions */
    3236 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyLagromory) );
    3237 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeLagromory) );
    3238 SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitLagromory) );
    3239 SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitLagromory) );
    3240
    3241 /* add separator parameters */
    3242 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/away", "minimal integrality violation of a basis "
    3243 "variable to try separation", &sepadata->away, FALSE, DEFAULT_AWAY, 0.0, 1.0, NULL, NULL) );
    3244
    3245 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/rootlpiterlimitfactor", "factor w.r.t. root node LP "
    3246 "iterations for maximal separating LP iterations in the root node (negative for no limit)",
    3247 &sepadata->rootlpiterlimitfactor, TRUE, DEFAULT_ROOTLPITERLIMITFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) );
    3248
    3249 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/totallpiterlimitfactor", "factor w.r.t. root node LP "
    3250 "iterations for maximal separating LP iterations in the tree (negative for no limit)",
    3251 &sepadata->totallpiterlimitfactor, TRUE, DEFAULT_TOTALLPITERLIMITFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) );
    3252
    3253 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perroundlpiterlimitfactor", "factor w.r.t. root node LP "
    3254 "iterations for maximal separating LP iterations per separation round (negative for no limit)",
    3255 &sepadata->perroundlpiterlimitfactor, TRUE, DEFAULT_PERROUNDLPITERLIMITFACTOR, -1.0, SCIP_REAL_MAX, NULL,
    3256 NULL) );
    3257
    3258 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perroundcutsfactorroot", "factor w.r.t. number of integer "
    3259 "columns for number of cuts separated per separation round in root node", &sepadata->perroundcutsfactorroot,
    3260 TRUE, DEFAULT_PERROUNDCUTSFACTORROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
    3261
    3262 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perroundcutsfactor", "factor w.r.t. number of integer "
    3263 "columns for number of cuts separated per separation round at a non-root node",
    3264 &sepadata->perroundcutsfactor, TRUE, DEFAULT_PERROUNDCUTSFACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
    3265
    3266 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/totalcutsfactor", "factor w.r.t. number of integer "
    3267 "columns for total number of cuts separated", &sepadata->totalcutsfactor, TRUE, DEFAULT_TOTALCUTSFACTOR, 0.0,
    3268 SCIP_REAL_MAX, NULL, NULL) );
    3269
    3270 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muparaminit", "initial value of the mu parameter (factor "
    3271 "for step length)", &sepadata->muparaminit, TRUE, DEFAULT_MUPARAMINIT, 0.0, 100.0, NULL, NULL) );
    3272
    3273 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muparamlb", "lower bound of the mu parameter (factor for "
    3274 "step length)", &sepadata->muparamlb, TRUE, DEFAULT_MUPARAMLB, 0.0, 1.0, NULL, NULL) );
    3275
    3276 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muparamub", "upper bound of the mu parameter (factor for "
    3277 "step length)", &sepadata->muparamub, TRUE, DEFAULT_MUPARAMUB, 1.0, 10.0, NULL, NULL) );
    3278
    3279 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/mubacktrackfactor", "factor of mu while backtracking the "
    3280 "mu parameter (factor for step length)", &sepadata->mubacktrackfactor, TRUE, DEFAULT_MUBACKTRACKFACTOR,
    3281 0.0, 1.0, NULL, NULL) );
    3282
    3283 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muslab1factor", "factor of mu parameter (factor for step "
    3284 "length) for larger increment" , &sepadata->muslab1factor, TRUE, DEFAULT_MUSLAB1FACTOR, 0.0, SCIP_REAL_MAX, NULL,
    3285 NULL));
    3286
    3287 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muslab2factor", "factor of mu parameter (factor for step "
    3288 "length) for smaller increment", &sepadata->muslab2factor, TRUE, DEFAULT_MUSLAB2FACTOR, 0.0, SCIP_REAL_MAX, NULL,
    3289 NULL) );
    3290
    3291 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muslab3factor", "factor of mu parameter (factor for step "
    3292 "length) for reduction", &sepadata->muslab3factor, TRUE, DEFAULT_MUSLAB3FACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
    3293
    3294 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/deltaslab1ub", "factor of delta deciding larger increment "
    3295 "of mu parameter (factor for step length)", &sepadata->deltaslab1ub, TRUE, DEFAULT_DELTASLAB1UB, 0.0, 1.0,
    3296 NULL, NULL) );
    3297
    3298 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/deltaslab2ub", "factor of delta deciding smaller "
    3299 "increment of mu parameter (factor for step length)", &sepadata->deltaslab2ub, TRUE, DEFAULT_DELTASLAB2UB,
    3300 0.0, 1.0, NULL, NULL) );
    3301
    3302 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/ubparamposfactor", "factor for positive upper bound used "
    3303 "as an estimate for the optimal Lagrangian dual value", &sepadata->ubparamposfactor, TRUE, DEFAULT_UBPARAMPOSFACTOR,
    3304 1.0, 100.0, NULL, NULL) );
    3305
    3306 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/ubparamnegfactor", "factor for negative upper bound used "
    3307 "as an estimate for the optimal Lagrangian dual value", &sepadata->ubparamnegfactor, TRUE, DEFAULT_UBPARAMNEGFACTOR,
    3308 0.0, 1.0, NULL, NULL) );
    3309
    3310 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perrootlpiterfactor", "factor w.r.t. root node LP "
    3311 "iterations for iteration limit of each separating LP (negative for no limit)",
    3312 &sepadata->perrootlpiterfactor, TRUE, DEFAULT_PERROOTLPITERFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) );
    3313
    3314 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perlpiterfactor", "factor w.r.t. non-root node LP "
    3315 "iterations for iteration limit of each separating LP (negative for no limit)", &sepadata->perlpiterfactor, TRUE,
    3316 DEFAULT_PERLPITERFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) );
    3317
    3318 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/cutsfilterfactor", "fraction of generated cuts per "
    3319 "explored basis to accept from separator", &sepadata->cutsfilterfactor, TRUE, DEFAULT_CUTSFILTERFACTOR, 0.0,
    3320 1.0, NULL, NULL) );
    3321
    3322 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/radiusinit", "initial radius of the ball used in "
    3323 "stabilization of Lagrangian multipliers", &sepadata->radiusinit, TRUE, DEFAULT_RADIUSINIT, 0.0, 1.0, NULL,
    3324 NULL) );
    3325
    3326 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/radiusmax", "maximum radius of the ball used in "
    3327 "stabilization of Lagrangian multipliers", &sepadata->radiusmax, TRUE, DEFAULT_RADIUSMAX, 0.0, SCIP_REAL_MAX,
    3328 NULL, NULL) );
    3329
    3330 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/radiusmin", "minimum radius of the ball used in "
    3331 "stabilization of Lagrangian multipliers", &sepadata->radiusmin, TRUE, DEFAULT_RADIUSMIN, 0.0, SCIP_REAL_MAX,
    3332 NULL, NULL) );
    3333
    3334 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/constant", "a constant for stablity center based "
    3335 "stabilization of Lagrangian multipliers", &sepadata->constant, TRUE, DEFAULT_CONST, 2.0, SCIP_REAL_MAX,
    3336 NULL, NULL) );
    3337
    3338 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/radiusupdateweight", "multiplier to evaluate cut "
    3339 "violation score used for updating ball radius", &sepadata->radiusupdateweight, TRUE,
    3340 DEFAULT_RADIUSUPDATEWEIGHT, 0.0, 1.0, NULL, NULL) );
    3341
    3342 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/dualdegeneracyratethreshold", "minimum dual degeneracy "
    3343 "rate for separator execution", &sepadata->dualdegeneracyratethreshold, FALSE,
    3344 DEFAULT_DUALDEGENERACYRATETHRESHOLD, 0.0, 1.0, NULL, NULL) );
    3345
    3346 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/varconsratiothreshold", "minimum variable-constraint "
    3347 "ratio on optimal face for separator execution", &sepadata->varconsratiothreshold, FALSE,
    3348 DEFAULT_VARCONSRATIOTHRESHOLD, 1.0, SCIP_REAL_MAX, NULL, NULL) );
    3349
    3350 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/muparamconst", "is the mu parameter (factor for step "
    3351 "length) constant?" , &sepadata->muparamconst, TRUE, DEFAULT_MUPARAMCONST, NULL, NULL) );
    3352
    3353 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/separaterows", "separate rows with integral slack?",
    3354 &sepadata->separaterows, TRUE, DEFAULT_SEPARATEROWS, NULL, NULL) );
    3355
    3356 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/sortcutoffsol", "sort fractional integer columns"
    3357 "based on fractionality?" , &sepadata->sortcutoffsol, TRUE, DEFAULT_SORTCUTOFFSOL, NULL, NULL) );
    3358
    3359 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/sidetypebasis", "choose side types of row (lhs/rhs) "
    3360 "based on basis information?", &sepadata->sidetypebasis, TRUE, DEFAULT_SIDETYPEBASIS, NULL, NULL) );
    3361
    3362 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/dynamiccuts", "should generated cuts be removed from "
    3363 "LP if they are no longer tight?", &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
    3364
    3365 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/makeintegral", "try to scale all cuts to integral "
    3366 "coefficients?", &sepadata->makeintegral, TRUE, DEFAULT_MAKEINTEGRAL, NULL, NULL) );
    3367
    3368 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/forcecuts", "force cuts to be added to the LP?",
    3369 &sepadata->forcecuts, TRUE, DEFAULT_FORCECUTS, NULL, NULL) );
    3370
    3371 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/delayedcuts", "should cuts be added to the delayed cut "
    3372 "pool", &sepadata->delayedcuts, TRUE, DEFAULT_DELAYEDCUTS, NULL, NULL) );
    3373
    3374 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/allowlocal", "should locally valid cuts be generated?",
    3375 &sepadata->allowlocal, TRUE, DEFAULT_ALLOWLOCAL, NULL, NULL) );
    3376
    3377 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/aggregatecuts", "aggregate all generated cuts using the "
    3378 "Lagrangian multipliers?", &sepadata->aggregatecuts, TRUE, DEFAULT_AGGREGATECUTS, NULL, NULL) );
    3379
    3380 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrounds", "maximal number of separation rounds per node "
    3381 "(-1: unlimited)", &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
    3382
    3383 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxroundsroot", "maximal number of separation rounds in "
    3384 "the root node (-1: unlimited)", &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL,
    3385 NULL) );
    3386
    3387 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/perroundnmaxlpiters", "maximal number of separating LP "
    3388 "iterations per separation round (-1: unlimited)", &sepadata->perroundnmaxlpiters, FALSE,
    3389 DEFAULT_PERROUNDMAXLPITERS, -1, INT_MAX, NULL, NULL) );
    3390
    3391 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxcutsperlp", "maximal number of cuts separated per "
    3392 "Lagromory LP in the non-root node", &sepadata->nmaxcutsperlp, FALSE, DEFAULT_PERLPMAXCUTS, 0, INT_MAX, NULL,
    3393 NULL) );
    3394
    3395 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxcutsperlproot", "maximal number of cuts separated per "
    3396 "Lagromory LP in the root node", &sepadata->nmaxcutsperlproot, FALSE, DEFAULT_PERLPMAXCUTSROOT, 0, INT_MAX,
    3397 NULL, NULL) );
    3398
    3399 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxmainiters", "maximal number of main loop iterations of "
    3400 "the relax-and-cut algorithm", &sepadata->nmaxmainiters, TRUE, DEFAULT_MAXMAINITERS, 0, INT_MAX, NULL, NULL) );
    3401
    3402 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxsubgradientiters", "maximal number of subgradient loop "
    3403 "iterations of the relax-and-cut algorithm", &sepadata->nmaxsubgradientiters, TRUE,
    3404 DEFAULT_MAXSUBGRADIENTITERS, 0, INT_MAX, NULL, NULL) );
    3405
    3406 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/cutgenfreq", "frequency of subgradient iterations for "
    3407 "generating cuts", &sepadata->cutgenfreq, TRUE, DEFAULT_CUTGENFREQ, 0, INT_MAX, NULL, NULL) );
    3408
    3409 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/cutaddfreq", "frequency of subgradient iterations for "
    3410 "adding cuts to objective function", &sepadata->cutaddfreq, TRUE, DEFAULT_CUTADDFREQ, 0, INT_MAX, NULL, NULL) );
    3411
    3412 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxlagrangianvalsforavg", "maximal number of iterations "
    3413 "for rolling average of Lagrangian value", &sepadata->nmaxlagrangianvalsforavg, TRUE,
    3414 DEFAULT_MAXLAGRANGIANVALSFORAVG, 0, INT_MAX, NULL, NULL) );
    3415
    3416 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxconsecitersformuupdate", "consecutive number of "
    3417 "iterations used to determine if mu needs to be backtracked", &sepadata->nmaxconsecitersformuupdate, TRUE,
    3418 DEFAULT_MAXCONSECITERSFORMUUPDATE, 0, INT_MAX, NULL, NULL) );
    3419
    3420 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/projectiontype", "the ball into which the Lagrangian multipliers "
    3421 "are projected for stabilization (0: no projection, 1: L1-norm ball projection, 2: L2-norm ball projection, 3: "
    3422 "L_inf-norm ball projection)", &sepadata->projectiontype, TRUE, DEFAULT_PROJECTIONTYPE, 0, 3, NULL, NULL));
    3423
    3424 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/stabilitycentertype", "type of stability center for "
    3425 "taking weighted average of Lagrangian multipliers for stabilization (0: no weighted stabilization, 1: best "
    3426 "Lagrangian multipliers)", &sepadata->stabilitycentertype, TRUE, DEFAULT_STABILITYCENTERTYPE, 0, 1, NULL,
    3427 NULL) );
    3428
    3429 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/optimalfacepriority", "priority of the optimal face for "
    3430 "separator execution (0: low priority, 1: medium priority, 2: high priority)",
    3431 &sepadata->optimalfacepriority, TRUE, DEFAULT_OPTIMALFACEPRIORITY, 0, 2, NULL, NULL) );
    3432
    3433 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/minrestart", "minimum restart round for separator "
    3434 "execution (0: from beginning of the instance solving, >= n with n >= 1: from restart round n)",
    3435 &sepadata->minrestart, TRUE, DEFAULT_MINRESTART, 0, INT_MAX, NULL, NULL) );
    3436
    3437 return SCIP_OKAY;
    3438}
    QUAD_ARRAY_STORE
    #define QUAD_ARRAY_STORE(a, idx, x)
    Definition: dbldblarith.h:55
    SCIPquadprecProdDD
    #define SCIPquadprecProdDD(r, a, b)
    Definition: dbldblarith.h:58
    QUAD_ARRAY_SIZE
    #define QUAD_ARRAY_SIZE(size)
    Definition: dbldblarith.h:53
    QUAD_ASSIGN
    #define QUAD_ASSIGN(a, constant)
    Definition: dbldblarith.h:51
    QUAD
    #define QUAD(x)
    Definition: dbldblarith.h:47
    SCIPquadprecSumQQ
    #define SCIPquadprecSumQQ(r, a, b)
    Definition: dbldblarith.h:67
    QUAD_ARRAY_LOAD
    #define QUAD_ARRAY_LOAD(r, a, idx)
    Definition: dbldblarith.h:54
    QUAD_TO_DBL
    #define QUAD_TO_DBL(x)
    Definition: dbldblarith.h:49
    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_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
    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_CALL
    #define SCIP_CALL(x)
    Definition: def.h:355
    SCIPisStopped
    SCIP_Bool SCIPisStopped(SCIP *scip)
    Definition: scip_general.c:759
    SCIPgetTransObjoffset
    SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
    Definition: scip_prob.c:1606
    SCIPlpiSetState
    SCIP_RETCODE SCIPlpiSetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPISTATE *lpistate)
    Definition: lpi_clp.cpp:3457
    SCIPlpiInfinity
    SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
    Definition: lpi_clp.cpp:3947
    SCIPlpiAddRows
    SCIP_RETCODE SCIPlpiAddRows(SCIP_LPI *lpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
    Definition: lpi_clp.cpp:920
    SCIPlpiSetRealpar
    SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
    Definition: lpi_clp.cpp:3861
    SCIPlpiFree
    SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
    Definition: lpi_clp.cpp:643
    SCIPlpiIsPrimalFeasible
    SCIP_Bool SCIPlpiIsPrimalFeasible(SCIP_LPI *lpi)
    Definition: lpi_clp.cpp:2549
    SCIPlpiIsDualFeasible
    SCIP_Bool SCIPlpiIsDualFeasible(SCIP_LPI *lpi)
    Definition: lpi_clp.cpp:2637
    SCIPlpiWasSolved
    SCIP_Bool SCIPlpiWasSolved(SCIP_LPI *lpi)
    Definition: lpi_clp.cpp:2414
    SCIPlpiGetSol
    SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
    Definition: lpi_clp.cpp:2816
    SCIPlpiFreeState
    SCIP_RETCODE SCIPlpiFreeState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
    Definition: lpi_clp.cpp:3531
    SCIPlpiAddCols
    SCIP_RETCODE SCIPlpiAddCols(SCIP_LPI *lpi, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
    Definition: lpi_clp.cpp:758
    SCIPlpiSolvePrimal
    SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
    Definition: lpi_clp.cpp:1833
    SCIPlpiCreate
    SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
    Definition: lpi_clp.cpp:531
    SCIPlpiGetState
    SCIP_RETCODE SCIPlpiGetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
    Definition: lpi_clp.cpp:3417
    SCIPgetMessagehdlr
    SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
    Definition: scip_message.c:88
    SCIPdebugMsg
    #define SCIPdebugMsg
    Definition: scip_message.h:78
    SCIPheurPassSolTrySol
    SCIP_RETCODE SCIPheurPassSolTrySol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
    Definition: heur_trysol.c:255
    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
    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
    SCIPgetRealParam
    SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
    Definition: scip_param.c:307
    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
    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
    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
    SCIPaddPoolCut
    SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
    Definition: scip_cut.c:336
    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
    SCIPisCutNew
    SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
    Definition: scip_cut.c:318
    SCIPisEfficacious
    SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
    Definition: scip_cut.c:135
    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
    SCIPaddDelayedPoolCut
    SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
    Definition: scip_cut.c:616
    SCIPfindHeur
    SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
    Definition: scip_heur.c:263
    SCIPgetVarObjDive
    SCIP_Real SCIPgetVarObjDive(SCIP *scip, SCIP_VAR *var)
    Definition: scip_lp.c:2552
    SCIPstartDive
    SCIP_RETCODE SCIPstartDive(SCIP *scip)
    Definition: scip_lp.c:2206
    SCIPgetLPDualDegeneracy
    SCIP_RETCODE SCIPgetLPDualDegeneracy(SCIP *scip, SCIP_Real *degeneracy, SCIP_Real *varconsratio)
    Definition: scip_lp.c:2757
    SCIPchgVarObjDive
    SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
    Definition: scip_lp.c:2343
    SCIPsolveDiveLP
    SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
    Definition: scip_lp.c:2643
    SCIPendDive
    SCIP_RETCODE SCIPendDive(SCIP *scip)
    Definition: scip_lp.c:2255
    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
    SCIPgetLPI
    SCIP_RETCODE SCIPgetLPI(SCIP *scip, SCIP_LPI **lpi)
    Definition: scip_lp.c:994
    SCIPgetLPSolstat
    SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
    Definition: scip_lp.c:174
    SCIPgetLPCols
    SCIP_COL ** SCIPgetLPCols(SCIP *scip)
    Definition: scip_lp.c:512
    SCIPgetLPObjval
    SCIP_Real SCIPgetLPObjval(SCIP *scip)
    Definition: scip_lp.c:253
    SCIPisLPSolBasic
    SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
    Definition: scip_lp.c:673
    SCIPgetLPBInvRow
    SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
    Definition: scip_lp.c:720
    SCIPfreeCleanBufferArray
    #define SCIPfreeCleanBufferArray(scip, ptr)
    Definition: scip_mem.h:146
    SCIPallocCleanBufferArray
    #define SCIPallocCleanBufferArray(scip, ptr, num)
    Definition: scip_mem.h:142
    SCIPblkmem
    BMS_BLKMEM * SCIPblkmem(SCIP *scip)
    Definition: scip_mem.c:57
    SCIPallocBufferArray
    #define SCIPallocBufferArray(scip, ptr, num)
    Definition: scip_mem.h:124
    SCIPfreeBufferArray
    #define SCIPfreeBufferArray(scip, ptr)
    Definition: scip_mem.h:136
    SCIPfreeBlockMemory
    #define SCIPfreeBlockMemory(scip, ptr)
    Definition: scip_mem.h:108
    SCIPallocBlockMemory
    #define SCIPallocBlockMemory(scip, ptr)
    Definition: scip_mem.h:89
    SCIProwIsIntegral
    SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
    Definition: lp.c:17785
    SCIProwGetLhs
    SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
    Definition: lp.c:17686
    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
    SCIPgetRowMinActivity
    SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:1903
    SCIProwGetNNonz
    int SCIProwGetNNonz(SCIP_ROW *row)
    Definition: lp.c:17607
    SCIProwGetCols
    SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
    Definition: lp.c:17632
    SCIProwGetRhs
    SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
    Definition: lp.c:17696
    SCIPgetRowMaxActivity
    SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:1920
    SCIProwGetNLPNonz
    int SCIProwGetNLPNonz(SCIP_ROW *row)
    Definition: lp.c:17621
    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
    SCIProwGetName
    const char * SCIProwGetName(SCIP_ROW *row)
    Definition: lp.c:17745
    SCIPgetRowActivity
    SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:2068
    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
    SCIPgetRowNumIntCols
    int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
    Definition: scip_lp.c:1832
    SCIProwGetVals
    SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
    Definition: lp.c:17642
    SCIPgetRowSolActivity
    SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
    Definition: scip_lp.c:2108
    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
    SCIPsepaGetNCalls
    SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
    Definition: sepa.c:873
    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
    SCIPfreeSol
    SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
    Definition: scip_sol.c:1252
    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
    SCIPgetMaxDepth
    int SCIPgetMaxDepth(SCIP *scip)
    Definition: scip_solvingstats.c:1282
    SCIPgetNRuns
    int SCIPgetNRuns(SCIP *scip)
    Definition: scip_solvingstats.c:133
    SCIPgetNRootFirstLPIterations
    SCIP_Longint SCIPgetNRootFirstLPIterations(SCIP *scip)
    Definition: scip_solvingstats.c:566
    SCIPgetNNodeInitLPIterations
    SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip)
    Definition: scip_solvingstats.c:878
    SCIPgetNLPIterations
    SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
    Definition: scip_solvingstats.c:503
    SCIPgetSolvingTime
    SCIP_Real SCIPgetSolvingTime(SCIP *scip)
    Definition: scip_timing.c:378
    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
    SCIPfeasFrac
    SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:932
    SCIPisPositive
    SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:561
    SCIPisLE
    SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:462
    SCIPisFeasZero
    SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:836
    SCIPisInfinity
    SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:512
    SCIPisFeasNegative
    SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:860
    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
    SCIPceil
    SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:634
    SCIPisEQ
    SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:436
    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
    SCIPvarIsIntegral
    SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
    Definition: var.c:23490
    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
    SCIPincludeSepaLagromory
    SCIP_RETCODE SCIPincludeSepaLagromory(SCIP *scip)
    Definition: sepa_lagromory.c:3217
    SCIPsortDownRealInt
    void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
    SCIPsnprintf
    int SCIPsnprintf(char *t, int len, const char *s,...)
    Definition: misc.c:10827
    heur_trysol.h
    primal heuristic that tries a given solution
    BMSclearMemory
    #define BMSclearMemory(ptr)
    Definition: memory.h:129
    BMS_BLKMEM
    struct BMS_BlkMem BMS_BLKMEM
    Definition: memory.h:437
    DEFAULT_MAXLAGRANGIANVALSFORAVG
    #define DEFAULT_MAXLAGRANGIANVALSFORAVG
    Definition: sepa_lagromory.c:202
    DEFAULT_DELTASLAB1UB
    #define DEFAULT_DELTASLAB1UB
    Definition: sepa_lagromory.c:194
    DEFAULT_UBPARAMNEGFACTOR
    #define DEFAULT_UBPARAMNEGFACTOR
    Definition: sepa_lagromory.c:200
    SEPA_PRIORITY
    #define SEPA_PRIORITY
    Definition: sepa_lagromory.c:140
    DEFAULT_VARCONSRATIOTHRESHOLD
    #define DEFAULT_VARCONSRATIOTHRESHOLD
    Definition: sepa_lagromory.c:161
    DEFAULT_DUALDEGENERACYRATETHRESHOLD
    #define DEFAULT_DUALDEGENERACYRATETHRESHOLD
    Definition: sepa_lagromory.c:160
    DEFAULT_MUPARAMINIT
    #define DEFAULT_MUPARAMINIT
    Definition: sepa_lagromory.c:183
    SCIP_DECL_SEPAEXECLP
    static SCIP_DECL_SEPAEXECLP(sepaExeclpLagromory)
    Definition: sepa_lagromory.c:3097
    sepadataCreate
    static SCIP_RETCODE sepadataCreate(SCIP *scip, SCIP_SEPADATA **sepadata)
    Definition: sepa_lagromory.c:3011
    BOUNDSWITCH
    #define BOUNDSWITCH
    Definition: sepa_lagromory.c:231
    DEFAULT_MUPARAMUB
    #define DEFAULT_MUPARAMUB
    Definition: sepa_lagromory.c:185
    SEPA_DELAY
    #define SEPA_DELAY
    Definition: sepa_lagromory.c:144
    RANDSEED
    #define RANDSEED
    Definition: sepa_lagromory.c:228
    updateMuSteplengthParam
    static SCIP_RETCODE updateMuSteplengthParam(SCIP *scip, SCIP_SEPADATA *sepadata, int subgradientiternum, SCIP_Real ubparam, SCIP_Real *lagrangianvals, SCIP_Real bestlagrangianval, SCIP_Real avglagrangianval, SCIP_Real *muparam, SCIP_Bool *backtrack)
    Definition: sepa_lagromory.c:684
    DEFAULT_CONST
    #define DEFAULT_CONST
    Definition: sepa_lagromory.c:224
    DEFAULT_ALLOWLOCAL
    #define DEFAULT_ALLOWLOCAL
    Definition: sepa_lagromory.c:155
    deleteLPWithSoftCuts
    static SCIP_RETCODE deleteLPWithSoftCuts(SCIP *scip, SCIP_SEPADATA *sepadata)
    Definition: sepa_lagromory.c:432
    DEFAULT_DYNAMICCUTS
    #define DEFAULT_DYNAMICCUTS
    Definition: sepa_lagromory.c:152
    DEFAULT_UBPARAMPOSFACTOR
    #define DEFAULT_UBPARAMPOSFACTOR
    Definition: sepa_lagromory.c:198
    linfBallProjection
    static void linfBallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
    Definition: sepa_lagromory.c:1166
    DEFAULT_MAKEINTEGRAL
    #define DEFAULT_MAKEINTEGRAL
    Definition: sepa_lagromory.c:153
    POSTPROCESS
    #define POSTPROCESS
    Definition: sepa_lagromory.c:230
    DEFAULT_MAXSUBGRADIENTITERS
    #define DEFAULT_MAXSUBGRADIENTITERS
    Definition: sepa_lagromory.c:179
    generateGMICuts
    static SCIP_RETCODE generateGMICuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, int subgradientiternum, SCIP_SOL *sol, SCIP_Real *solvals, int nmaxgeneratedperroundcuts, SCIP_Bool allowlocal, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int ngeneratedcurrroundcuts, int *ngeneratednewcuts, int depth, SCIP_Bool *cutoff)
    Definition: sepa_lagromory.c:1997
    SEPA_DESC
    #define SEPA_DESC
    Definition: sepa_lagromory.c:139
    solveLagromoryLP
    static SCIP_RETCODE solveLagromoryLP(SCIP *scip, SCIP_SEPADATA *sepadata, int depth, SCIP_Real origobjoffset, SCIP_Bool *solfound, SCIP_SOL *sol, SCIP_Real *solvals, SCIP_Real *objval, int *ncurrroundlpiters)
    Definition: sepa_lagromory.c:1441
    aggregateGeneratedCuts
    static SCIP_RETCODE aggregateGeneratedCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_ROW **generatedcuts, SCIP_Real *bestdualvector, int bestdualvectorlen, SCIP_ROW **aggrcuts, int *naggrcuts, SCIP_Bool *cutoff)
    Definition: sepa_lagromory.c:1774
    DEFAULT_MUPARAMLB
    #define DEFAULT_MUPARAMLB
    Definition: sepa_lagromory.c:184
    DEFAULT_RADIUSMAX
    #define DEFAULT_RADIUSMAX
    Definition: sepa_lagromory.c:222
    MAKECONTINTEGRAL
    #define MAKECONTINTEGRAL
    Definition: sepa_lagromory.c:229
    updateDualVector
    static SCIP_RETCODE updateDualVector(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *dualvector1, SCIP_Real *dualvector2, int dualvector2len, int ndualvector2updates, int subgradientiternum, int totaliternum, SCIP_Real steplength, SCIP_Real *subgradient, int ncuts, SCIP_Bool backtrack, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Bool *dualvecsdiffer, SCIP_Real *ballradius)
    Definition: sepa_lagromory.c:1285
    DEFAULT_PERLPMAXCUTSROOT
    #define DEFAULT_PERLPMAXCUTSROOT
    Definition: sepa_lagromory.c:164
    DEFAULT_MAXROUNDSROOT
    #define DEFAULT_MAXROUNDSROOT
    Definition: sepa_lagromory.c:158
    DEFAULT_PROJECTIONTYPE
    #define DEFAULT_PROJECTIONTYPE
    Definition: sepa_lagromory.c:216
    SEPA_USESSUBSCIP
    #define SEPA_USESSUBSCIP
    Definition: sepa_lagromory.c:143
    DEFAULT_CUTADDFREQ
    #define DEFAULT_CUTADDFREQ
    Definition: sepa_lagromory.c:209
    checkMainLoopTermination
    static SCIP_RETCODE checkMainLoopTermination(SCIP_SEPADATA *sepadata, SCIP_Bool cutoff, SCIP_Bool dualvecsdiffer, int ngeneratedcurrroundcuts, int nsoftcuts, int nmaxgeneratedperroundcuts, int ncurrroundlpiters, int depth, SCIP_Bool *terminate)
    Definition: sepa_lagromory.c:2644
    DEFAULT_MUSLAB2FACTOR
    #define DEFAULT_MUSLAB2FACTOR
    Definition: sepa_lagromory.c:190
    DEFAULT_RADIUSINIT
    #define DEFAULT_RADIUSINIT
    Definition: sepa_lagromory.c:221
    DEFAULT_DELAYEDCUTS
    #define DEFAULT_DELAYEDCUTS
    Definition: sepa_lagromory.c:148
    VARTYPEUSEVBDS
    #define VARTYPEUSEVBDS
    Definition: sepa_lagromory.c:232
    DEFAULT_SIDETYPEBASIS
    #define DEFAULT_SIDETYPEBASIS
    Definition: sepa_lagromory.c:151
    DEFAULT_TOTALCUTSFACTOR
    #define DEFAULT_TOTALCUTSFACTOR
    Definition: sepa_lagromory.c:177
    generateInitCutPool
    static SCIP_RETCODE generateInitCutPool(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, SCIP_SOL *sol, SCIP_Real *solvals, int nmaxgeneratedperroundcuts, SCIP_Bool allowlocal, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int *ngeneratedcutsperiter, int *ngeneratedcurrroundcuts, int depth, SCIP_Bool *cutoff)
    Definition: sepa_lagromory.c:2530
    DEFAULT_PERROUNDMAXLPITERS
    #define DEFAULT_PERROUNDMAXLPITERS
    Definition: sepa_lagromory.c:172
    DEFAULT_PERROUNDCUTSFACTOR
    #define DEFAULT_PERROUNDCUTSFACTOR
    Definition: sepa_lagromory.c:175
    FIXINTEGRALRHS
    #define FIXINTEGRALRHS
    Definition: sepa_lagromory.c:234
    DEFAULT_MAXMAINITERS
    #define DEFAULT_MAXMAINITERS
    Definition: sepa_lagromory.c:178
    DEFAULT_PERROUNDCUTSFACTORROOT
    #define DEFAULT_PERROUNDCUTSFACTORROOT
    Definition: sepa_lagromory.c:173
    updateSubgradient
    static void updateSubgradient(SCIP *scip, SCIP_SOL *sol, SCIP_ROW **cuts, int ncuts, SCIP_Real *subgradient, SCIP_Real *dualvector, SCIP_Bool *subgradientzero, int *ncutviols, SCIP_Real *maxcutviol, int *nnzsubgradientdualprod, SCIP_Real *maxnzsubgradientdualprod)
    Definition: sepa_lagromory.c:808
    l1BallProjection
    static SCIP_RETCODE l1BallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
    Definition: sepa_lagromory.c:995
    DEFAULT_OPTIMALFACEPRIORITY
    #define DEFAULT_OPTIMALFACEPRIORITY
    Definition: sepa_lagromory.c:211
    DEFAULT_SORTCUTOFFSOL
    #define DEFAULT_SORTCUTOFFSOL
    Definition: sepa_lagromory.c:150
    MAXAGGRLEN
    #define MAXAGGRLEN(ncols)
    Definition: sepa_lagromory.c:235
    separateCuts
    static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, SCIP_RESULT *result)
    Definition: sepa_lagromory.c:2692
    SCIP_DECL_SEPAEXIT
    static SCIP_DECL_SEPAEXIT(sepaExitLagromory)
    Definition: sepa_lagromory.c:3083
    DEFAULT_MUSLAB1FACTOR
    #define DEFAULT_MUSLAB1FACTOR
    Definition: sepa_lagromory.c:188
    DEFAULT_PERROUNDLPITERLIMITFACTOR
    #define DEFAULT_PERROUNDLPITERLIMITFACTOR
    Definition: sepa_lagromory.c:166
    DEFAULT_CUTSFILTERFACTOR
    #define DEFAULT_CUTSFILTERFACTOR
    Definition: sepa_lagromory.c:210
    SCIP_DECL_SEPAFREE
    static SCIP_DECL_SEPAFREE(sepaFreeLagromory)
    Definition: sepa_lagromory.c:3047
    sepadataFree
    static SCIP_RETCODE sepadataFree(SCIP *scip, SCIP_SEPADATA **sepadata)
    Definition: sepa_lagromory.c:648
    createLPWithSoftCuts
    static SCIP_RETCODE createLPWithSoftCuts(SCIP *scip, SCIP_SEPADATA *sepadata)
    Definition: sepa_lagromory.c:351
    updateObjectiveVector
    static SCIP_RETCODE updateObjectiveVector(SCIP *scip, SCIP_Real *dualvector, SCIP_ROW **cuts, int ncuts, SCIP_Real *origobjcoefs, SCIP_Bool *objvecsdiffer)
    Definition: sepa_lagromory.c:2187
    SEPA_MAXBOUNDDIST
    #define SEPA_MAXBOUNDDIST
    Definition: sepa_lagromory.c:142
    addGMICutsAsSoftConss
    static SCIP_RETCODE addGMICutsAsSoftConss(SCIP_Real *dualvector, int ngeneratedcuts, int *naddedcuts, int *nnewaddedsoftcuts)
    Definition: sepa_lagromory.c:2272
    addCuts
    static SCIP_RETCODE addCuts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **cuts, int ncuts, SCIP_Longint maxdnom, SCIP_Real maxscale, int *naddedcuts, SCIP_Bool *cutoff)
    Definition: sepa_lagromory.c:2567
    SCIP_DECL_SEPAINIT
    static SCIP_DECL_SEPAINIT(sepaInitLagromory)
    Definition: sepa_lagromory.c:3063
    DEFAULT_AWAY
    #define DEFAULT_AWAY
    Definition: sepa_lagromory.c:147
    solveLPWithHardCuts
    static SCIP_RETCODE solveLPWithHardCuts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Bool *solfound, SCIP_SOL *sol, SCIP_Real *solvals)
    Definition: sepa_lagromory.c:1578
    DEFAULT_FORCECUTS
    #define DEFAULT_FORCECUTS
    Definition: sepa_lagromory.c:154
    SEPA_FREQ
    #define SEPA_FREQ
    Definition: sepa_lagromory.c:141
    DEFAULT_PERLPITERFACTOR
    #define DEFAULT_PERLPITERFACTOR
    Definition: sepa_lagromory.c:206
    checkLagrangianDualTermination
    static SCIP_RETCODE checkLagrangianDualTermination(SCIP_SEPADATA *sepadata, int nnewaddedsoftcuts, int nyettoaddsoftcuts, SCIP_Bool objvecsdiffer, int ngeneratedcurrroundcuts, int nmaxgeneratedperroundcuts, int ncurrroundlpiters, int depth, SCIP_Bool *terminate)
    Definition: sepa_lagromory.c:1394
    createLPWithHardCuts
    static SCIP_RETCODE createLPWithHardCuts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **cuts, int ncuts)
    Definition: sepa_lagromory.c:449
    DEFAULT_STABILITYCENTERTYPE
    #define DEFAULT_STABILITYCENTERTYPE
    Definition: sepa_lagromory.c:219
    DEFAULT_RADIUSMIN
    #define DEFAULT_RADIUSMIN
    Definition: sepa_lagromory.c:223
    SEPA_NAME
    #define SEPA_NAME
    Definition: sepa_lagromory.c:138
    solveLagrangianDual
    static SCIP_RETCODE solveLagrangianDual(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *solvals, int mainiternum, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, int nmaxgeneratedperroundcuts, SCIP_Real *origobjcoefs, SCIP_Real origobjoffset, SCIP_Real *dualvector, int *nsoftcuts, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int *ngeneratedcutsperiter, int *ngeneratedcurrroundcuts, int *ncurrroundlpiters, SCIP_Bool *cutoff, SCIP_Real *bestlagrangianval, SCIP_Real *bestdualvector, int *bestdualvectorlen, int *nbestdualupdates, int *totaliternum)
    Definition: sepa_lagromory.c:2296
    DEFAULT_PERROOTLPITERFACTOR
    #define DEFAULT_PERROOTLPITERFACTOR
    Definition: sepa_lagromory.c:204
    constructCutRow
    static SCIP_RETCODE constructCutRow(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, int subgradientiternum, int cutnnz, int *cutinds, SCIP_Real *cutcoefs, SCIP_Real cutefficacy, SCIP_Real cutrhs, SCIP_Bool cutislocal, int cutrank, SCIP_ROW **generatedcuts, SCIP_Real *generatedcutefficacies, int ngeneratedcurrroundcuts, int *ngeneratednewcuts, SCIP_Bool *cutoff)
    Definition: sepa_lagromory.c:1642
    DEFAULT_ROOTLPITERLIMITFACTOR
    #define DEFAULT_ROOTLPITERLIMITFACTOR
    Definition: sepa_lagromory.c:168
    DEFAULT_AGGREGATECUTS
    #define DEFAULT_AGGREGATECUTS
    Definition: sepa_lagromory.c:213
    DEFAULT_MAXROUNDS
    #define DEFAULT_MAXROUNDS
    Definition: sepa_lagromory.c:159
    DEFAULT_MUBACKTRACKFACTOR
    #define DEFAULT_MUBACKTRACKFACTOR
    Definition: sepa_lagromory.c:186
    updateLagrangianValue
    static void updateLagrangianValue(SCIP *scip, SCIP_Real objval, SCIP_Real *dualvector, SCIP_ROW **cuts, int ncuts, SCIP_Real *lagrangianval)
    Definition: sepa_lagromory.c:879
    DEFAULT_MINRESTART
    #define DEFAULT_MINRESTART
    Definition: sepa_lagromory.c:162
    SCIP_DECL_SEPACOPY
    static SCIP_DECL_SEPACOPY(sepaCopyLagromory)
    Definition: sepa_lagromory.c:3032
    DEFAULT_CUTGENFREQ
    #define DEFAULT_CUTGENFREQ
    Definition: sepa_lagromory.c:208
    updateStepLength
    static void updateStepLength(SCIP *scip, SCIP_Real muparam, SCIP_Real ubparam, SCIP_Real lagrangianval, SCIP_Real *subgradient, int ncuts, SCIP_Real *steplength)
    Definition: sepa_lagromory.c:904
    DEFAULT_RADIUSUPDATEWEIGHT
    #define DEFAULT_RADIUSUPDATEWEIGHT
    Definition: sepa_lagromory.c:225
    updateBallRadius
    static void updateBallRadius(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Real *ballradius)
    Definition: sepa_lagromory.c:926
    DEFAULT_SEPARATEROWS
    #define DEFAULT_SEPARATEROWS
    Definition: sepa_lagromory.c:149
    l2BallProjection
    static void l2BallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
    Definition: sepa_lagromory.c:1135
    DEFAULT_DELTASLAB2UB
    #define DEFAULT_DELTASLAB2UB
    Definition: sepa_lagromory.c:196
    DEFAULT_MUPARAMCONST
    #define DEFAULT_MUPARAMCONST
    Definition: sepa_lagromory.c:182
    stabilizeDualVector
    static SCIP_RETCODE stabilizeDualVector(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real *bestdualvector, int bestdualvectorlen, int nbestdualupdates, int subgradientiternum, int totaliternum, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Real *ballradius)
    Definition: sepa_lagromory.c:1225
    DEFAULT_TOTALLPITERLIMITFACTOR
    #define DEFAULT_TOTALLPITERLIMITFACTOR
    Definition: sepa_lagromory.c:170
    DEFAULT_PERLPMAXCUTS
    #define DEFAULT_PERLPMAXCUTS
    Definition: sepa_lagromory.c:165
    weightedDualVector
    static void weightedDualVector(SCIP_SEPADATA *sepadata, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real *stabilitycenter, int stabilitycenterlen, int nbestdualupdates, int totaliternum)
    Definition: sepa_lagromory.c:1192
    DEFAULT_MUSLAB3FACTOR
    #define DEFAULT_MUSLAB3FACTOR
    Definition: sepa_lagromory.c:192
    DEFAULT_MAXCONSECITERSFORMUUPDATE
    #define DEFAULT_MAXCONSECITERSFORMUUPDATE
    Definition: sepa_lagromory.c:203
    sepa_lagromory.h
    lagromory separator
    SCIP_AggrRow
    Definition: struct_cuts.h:41
    SCIP_Col
    Definition: struct_lp.h:138
    SCIP_Heur
    Definition: struct_heur.h:98
    SCIP_LPiState
    Definition: lpi_clp.cpp:133
    SCIP_LPi
    Definition: lpi_clp.cpp:105
    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_LPSOLSTAT
    enum SCIP_LPSolStat SCIP_LPSOLSTAT
    Definition: type_lp.h:52
    SCIP_LPSOLSTAT_OPTIMAL
    @ SCIP_LPSOLSTAT_OPTIMAL
    Definition: type_lp.h:44
    SCIP_LPPAR_LPTILIM
    @ SCIP_LPPAR_LPTILIM
    Definition: type_lpi.h:61
    SCIP_OBJSEN_MINIMIZE
    @ SCIP_OBJSEN_MINIMIZE
    Definition: type_lpi.h:43
    SCIP_DIDNOTRUN
    @ SCIP_DIDNOTRUN
    Definition: type_result.h:42
    SCIP_CUTOFF
    @ SCIP_CUTOFF
    Definition: type_result.h:48
    SCIP_DIDNOTFIND
    @ SCIP_DIDNOTFIND
    Definition: type_result.h:44
    SCIP_SEPARATED
    @ SCIP_SEPARATED
    Definition: type_result.h:49
    SCIP_RESULT
    enum SCIP_Result SCIP_RESULT
    Definition: type_result.h:61
    SCIP_OKAY
    @ SCIP_OKAY
    Definition: type_retcode.h:42
    SCIP_RETCODE
    enum SCIP_Retcode SCIP_RETCODE
    Definition: type_retcode.h:63
    SCIP_SEPADATA
    struct SCIP_SepaData SCIP_SEPADATA
    Definition: type_sepa.h:52