relax_gcg.c
Go to the documentation of this file.
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
87 #define DEFAULT_MODE DEC_DECMODE_DANTZIGWOLFE /**< the decomposition mode that GCG will use. (0: Dantzig-Wolfe (default),
108 int* blockrepresentative;/**< number of the pricing problem, that represents the i-th problem */
113 int nvarlinkconss; /**< number of constraints that ensure that copies of linking variables have the same value */
114 SCIP_Real pricingprobsmemused; /**< sum of memory used after problem creation stage of all pricing problems */
121 SCIP_CONS** origmasterconss; /**< array of constraints in the original problem that belong to the
131 SCIP_Bool origsolfeasible; /**< is the current lp solution primal feasible in the original space? */
132 SCIP_Longint lastmasterlpiters; /**< number of lp iterations when currentorigsol was updated the last time */
133 SCIP_SOL* lastmastersol; /**< last feasible master solution that was added to the original problem */
135 int nmarkedmasterconss; /**< number of elements in array of conss that are marked to be in the master */
137 SCIP_Longint lastsolvednodenr; /**< node number of the node that was solved at the last call of the relaxator */
144 SCIP_Bool discretization; /**< TRUE: use discretization approach; FALSE: use convexification approach */
145 SCIP_Bool mipdiscretization; /**< TRUE: use discretization approach in MIPs; FALSE: use convexification approach in MIPs*/
146 SCIP_Bool aggregation; /**< should identical blocks be aggregated (only for discretization approach)? */
150 DEC_DECMODE mode; /**< the decomposition mode for GCG. 0: Dantzig-Wolfe (default), 1: Benders' decomposition, 2: automatic */
192 assert(newblock >= 0 || (GCGgetDecompositionMode(scip) == DEC_DECMODE_BENDERS && newblock == -2));
194 assert(SCIPvarIsOriginal(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
213 SCIP_CALL( GCGoriginalVarAddBlock(scip, var, newblock, relaxdata->npricingprobs, relaxdata->mode) );
242 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->markedmasterconss), relaxdata->maxmarkedmasterconss) );
261 /** converts the structure to the GCG format by setting the appropriate blocks and master constraints */
316 SCIPdebugMessage("Copying structure with %d blocks, %d linking vars and %d linking constraints.\n", nblocks, nlinkingvars, nlinkingconss);
322 /* SCIPdebugMessage("\tProcessing linking constraint %s.\n", SCIPconsGetName(linkingconss[i])); */
342 /* SCIPdebugMessage("\tProcessing block %d (%d conss, %d vars).\n", i, nsubscipconss[i], nsubscipvars[i]); */
359 SCIPdebugMessage("\t\tOriginal var %s (%p) in block %d\n", SCIPvarGetName(subscipvars[i][j]), (void*) subscipvars[i][j], i);
367 SCIPdebugMessage("\t\tTransformed var %s (%p) in block %d\n", SCIPvarGetName(relevantvar), (void*) relevantvar, i);
380 SCIPdebugMessage("\tDetecting constraint blocks of linking var %s\n", SCIPvarGetName(linkingvars[i]));
422 /* if the linking variable is only in one block, then it would not have been flagged as a linking variable. In
423 * the Benders' decomposition case, then linking variable needs to be flagged as linking so that it is added to
451 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(relaxdata->masterconss), relaxdata->maxmasterconss, newsize) );
452 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(relaxdata->origmasterconss), relaxdata->maxmasterconss, newsize) );
478 SCIP_CALL( SCIPreallocMemoryArray(scip, &(relaxdata->branchrules), (size_t)relaxdata->nbranchrules+1) );
577 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Master problem is a set covering problem.\n");
582 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Master problem is a set partitioning problem.\n");
672 SCIPdebugMessage("--> obj differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
675 if( !SCIPisEQ(relaxdata->masterprob, SCIPvarGetLbOriginal(vars1[i]), SCIPvarGetLbOriginal(vars2[i])) )
677 SCIPdebugMessage("--> lb differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
680 if( !SCIPisEQ(relaxdata->masterprob, SCIPvarGetUbOriginal(vars1[i]), SCIPvarGetUbOriginal(vars2[i])) )
682 SCIPdebugMessage("--> ub differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
687 SCIPdebugMessage("--> type differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
699 SCIPdebugMessage("--> orig obj differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
753 SCIPdebugMessage("--> nvars differs for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
756 if( !SCIPisEQ(relaxdata->masterprob, SCIPgetLhsLinear(scip1, conss1[i]), SCIPgetLhsLinear(scip2, conss2[i])) )
758 SCIPdebugMessage("--> lhs differs for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
761 if( !SCIPisEQ(relaxdata->masterprob, SCIPgetRhsLinear(scip1, conss1[i]), SCIPgetRhsLinear(scip2, conss2[i])) )
763 SCIPdebugMessage("--> rhs differs for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
766 if( !realArraysAreEqual(scip, SCIPgetValsLinear(scip1, conss1[i]), SCIPgetNVarsLinear(scip1, conss1[i]),
769 SCIPdebugMessage("--> coefs differ for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
778 SCIPdebugMessage("--> vars differ for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
827 SCIP_CALL(GCGconshdlrDecompArePricingprobsIdenticalForPartialdecid(scip, partialdecid, probnr2, probnr1, identical) );
832 SCIP_CALL(GCGconshdlrDecompCreateVarmapForPartialdecId(scip, hashorig2pricingvar, partialdecid, probnr2, probnr1, scip2, scip1, varmap) );
953 assert( SCIPgetNConss(scip) == GCGconshdlrDecompGetNFormerDetectionConssForID(scip, DECdecompGetPartialdecID(relaxdata->decomp)) );
954 SCIPdebugMessage( "nconss: %d; ndetectionconss: %d -> using partialdec information for identity test \n", SCIPgetNConss(scip), GCGconshdlrDecompGetNFormerDetectionConssForID(scip, DECdecompGetPartialdecID(relaxdata->decomp) ) );
955 SCIP_CALL( pricingprobsAreIdenticalFromDetectionInfo( scip, relaxdata, hashorig2pricingvar, i, j, varmap, &identical ) );
961 * 3) translate varmap when transforming partialdec to decomp (store varmap in decomp or partialdec?)
1028 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Matrix has %d blocks, using %d%s pricing problem%s.\n",
1029 relaxdata->npricingprobs, nrelevant, (relaxdata->npricingprobs == nrelevant ? "" : " aggregated"), (nrelevant == 1 ? "" : "s"));
1041 SCIP_Real infinity, /**< values larger than this are considered infinity in the pricing problem */
1042 SCIP_Real epsilon, /**< absolute values smaller than this are considered zero in the pricing problem */
1043 SCIP_Real sumepsilon, /**< absolute values of sums smaller than this are considered zero in the pricing problem */
1045 SCIP_Real lpfeastolfactor, /**< primal feasibility tolerance factor of LP solver in the pricing problem */
1046 SCIP_Real dualfeastol, /**< feasibility tolerance for reduced costs in LP solution in the pricing problem */
1073 /* disable dual fixing presolver for the moment, because we want to avoid variables fixed to infinity */
1132 /** creates a variable in a pricing problem corresponding to the given original variable (belonging to exactly one block) */
1148 SCIP_CALL( GCGoriginalVarCreatePricingVar(relaxdata->pricingprobs[pricingprobnr], origvar, &var) );
1229 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &relaxdata->varlinkconss, relaxdata->nvarlinkconss, (size_t)relaxdata->nvarlinkconss+1) );
1230 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &relaxdata->varlinkconsblock, relaxdata->nvarlinkconss, (size_t)relaxdata->nvarlinkconss+1) );
1278 SCIP_HASHMAP** hashorig2pricingvar /**< hashmap mapping original variables to pricing variables */
1308 tempblock = (int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(relaxdata->decomp), probvar)-1; /*lint !e507*/
1315 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " changed block number to %d \n", tempblock );
1320 SCIPdebugMessage("Creating map for (%p, %p) var %s:", (void*)(vars[v]), (void*)(probvar), SCIPvarGetName(probvar));
1322 SCIP_CALL( SCIPhashmapInsert(relaxdata->hashorig2origvar, (void*)(probvar), (void*)(probvar)) );
1341 assert(GCGvarIsPricing((SCIP_VAR*) SCIPhashmapGetImage(hashorig2pricingvar[blocknr], probvar)));
1343 /* variable is a linking variable --> create corresponding pricing variable in all linked blocks
1412 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "pricing problem %d: %d conss, %d vars (%d bins, %d ints, %d impls and %d cont)\n", i,
1438 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->masterconss), relaxdata->maxmasterconss) );
1439 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->origmasterconss), relaxdata->maxmasterconss) );
1443 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->pricingprobs), relaxdata->npricingprobs) );
1444 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->blockrepresentative), relaxdata->npricingprobs) );
1445 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->nblocksidentical), relaxdata->npricingprobs) );
1448 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->convconss), relaxdata->npricingprobs) );
1451 SCIP_CALL( SCIPhashmapCreate(&(relaxdata->hashorig2origvar), SCIPblkmem(scip), 10*SCIPgetNVars(scip)+1) );
1463 SCIP_Real infinity, /**< values larger than this are considered infinity in the master problem */
1464 SCIP_Real epsilon, /**< absolute values smaller than this are considered zero in the master problem */
1465 SCIP_Real sumepsilon, /**< absolute values of sums smaller than this are considered zero in the master problem */
1467 SCIP_Real lpfeastolfactor, /**< primal feasibility tolerance factor of LP solver in the master problem */
1468 SCIP_Real dualfeastol, /**< feasibility tolerance for reduced costs in LP solution in the master problem */
1488 /* disable aggregation and multiaggregation of variables, as this might lead to issues with copied original variables */
1492 /* the following settings are for decomposition, so if the original problem is solved directly, then these settings
1506 /* disable aggregation and multiaggregation of variables, as this might lead to issues with copied original variables */
1510 /* for Benders' decomposition, some additional parameter settings are required for the master problem. */
1524 /* the trysol heuristic must have a high priority to ensure the solutions found by the relaxator are added to the
1540 SCIP_Real infinity, /**< values larger than this are considered infinity in the pricing problem */
1541 SCIP_Real epsilon, /**< absolute values smaller than this are considered zero in the pricing problem */
1542 SCIP_Real sumepsilon, /**< absolute values of sums smaller than this are considered zero in the pricing problem */
1544 SCIP_Real lpfeastolfactor, /**< primal feasibility tolerance factor of LP solver in the pricing problem */
1545 SCIP_Real dualfeastol, /**< feasibility tolerance for reduced costs in LP solution in the pricing problem */
1554 SCIP_CALL( setPricingProblemParameters(*pricingscip, clocktype, infinity, epsilon, sumepsilon, feastol, lpfeastolfactor, dualfeastol, enableppcuts) );
1644 /* in the Benders' decomposition mode, all variables from the linking constraints need to be added to the master
1645 * problem. Additionally, if the original problem is solved directly, then we must ensure that all variables are
1648 if( GCGgetDecompositionMode(scip) == DEC_DECMODE_BENDERS || GCGgetDecompositionMode(scip) == DEC_DECMODE_ORIGINAL )
1664 /* if the variable is a linking variable or is directly transferred to the master problem, then it is not
1665 * added to the constraint. This is because the linking variables and the transferred variables are added
1668 while( i < nconsvars && (GCGoriginalVarIsLinking(consvars[i]) || GCGoriginalVarIsTransVar(consvars[i])) )
1683 /* if the original has already has a copy in the master problem, then this is used. Otherwise, the master
1714 SCIP_CALL( SCIPcreateConsLinear(relaxdata->masterprob, &mastercons, name, nconsvars, consvars, consvals,
1728 if( GCGgetDecompositionMode(scip) == DEC_DECMODE_BENDERS || GCGgetDecompositionMode(scip) == DEC_DECMODE_ORIGINAL )
1746 SCIP_CALL( saveOriginalVarMastercoeffs(scip, SCIPgetVars(scip), SCIPgetNVars(scip), relaxdata->nmasterconss, relaxdata->origmasterconss, relaxdata->masterconss) );
1756 SCIP_HASHMAP** hashorig2pricingvar /**< hashmap mapping original to corresponding pricing variables */
1776 SCIP_CALL( SCIPhashmapCreate(&hashorig2pricingconstmp, SCIPblkmem(scip), SCIPgetNConss(scip)) ); /*lint !e613*/
1783 SCIPdebugMessage("copying %s to pricing problem %d\n", SCIPconsGetName(subscipconss[b][c]), b);
1794 SCIP_CALL( SCIPgetConsCopy(scip, relaxdata->pricingprobs[b], subscipconss[b][c], &newcons, SCIPconsGetHdlr(subscipconss[b][c]),
1820 if( SCIPisFeasEQ( scip, SCIPvarGetLbGlobal(curvars[i]), SCIPvarGetUbGlobal(curvars[i]) ) && SCIPisFeasEQ( scip, SCIPvarGetUbGlobal(curvars[i]), 0. ) )
1823 assert(GCGvarIsPricing(curvars[i]) || ( SCIPvarIsNegated(curvars[i]) && GCGvarIsPricing(SCIPvarGetNegatedVar(curvars[i]) ) ) );
1839 /** creates the master problem and the pricing problems and copies the constraints into them */
1878 /* if the original problem is to be solved, then we need to free the currently master problem and create a new
1887 SCIP_CALL( SCIPsetIntParam(relaxdata->altmasterprob, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
1895 /* setting the total node limit to 1 for the original SCIP instance. This is because Benders' decomposition solves
1896 * the MIP within the relaxator of the root node. So no branching in the original problem is required.
1924 /* get clocktype of the original SCIP instance in order to use the same clocktype in master and pricing problems */
1927 /* get numerical tolerances of the original SCIP instance in order to use the same numerical tolerances in master and pricing problems */
1936 SCIP_CALL( createMasterProblem(relaxdata->masterprob, name, clocktype, infinity, epsilon, sumepsilon, feastol,
1947 SCIP_CALL( createPricingProblem(&(relaxdata->pricingprobs[i]), name, clocktype, infinity, epsilon, sumepsilon,
1949 SCIP_CALL( SCIPhashmapCreate(&(hashorig2pricingvar[i]), SCIPblkmem(scip), SCIPgetNVars(scip)) ); /*lint !e613*/
1952 SCIP_CALL( SCIPsetCharParam(relaxdata->pricingprobs[i], "estimation/restarts/restartpolicy", 'n') );
1958 * If the master problem is solved directly, then we can still call methods creating the pricing problems. These
1959 * methods check the number of pricing problems and number of blocks. As such, if the original problem is solved
1982 SCIP_CALL( SCIPcreateConsLinear(relaxdata->masterprob, &(relaxdata->convconss[i]), name, 0, NULL, NULL,
1992 SCIP_CALL( displayPricingStatistics(scip, relaxdata->pricingprobs, relaxdata->npricingprobs, relaxdata->blockrepresentative) );
2062 SCIP_CALL( SCIPincSolVal(scip, *newsol, vars[v], SCIPgetSolVal(probs[block], SCIPgetBestSol(probs[block]), pricingvar)) );
2087 /* if the Benders' decomposition is used, then the transformed problem of the subproblems must be freed.
2088 * This is because the within the create subproblem stage, if the subproblem is an LP, then the SCIP instance is put
2095 /* if the problem is not in SCIP_STAGE_PROBLEM, then the transformed problem must be freed. The subproblem
2126 /* SCIPinfoMessage(scip, NULL, "%s: %f block %d\n", SCIPvarGetName(origvar), SCIPvarGetObj(origvar),
2179 blocktimelimit = (timelimit - SCIPgetSolvingTime(scip)) * 1.02 + SCIPgetSolvingTime(blockprob);
2209 if( GCGgetDecompositionMode(scip) == DEC_DECMODE_DANTZIGWOLFE || GCGgetDecompositionMode(scip) == DEC_DECMODE_ORIGINAL )
2223 /* since the diagonal blocks are being solved, this indicates that the subproblems are independent. As such, we
2230 SCIP_CALL( SCIPsolveBendersSubproblem(relaxdata->masterprob, benders, NULL, blocknum, &infeasible,
2278 if( GCGgetDecompositionMode(scip) == DEC_DECMODE_DANTZIGWOLFE || GCGgetDecompositionMode(scip) == DEC_DECMODE_ORIGINAL )
2326 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Block diagonal structure detected, solving blocks individually.\n");
2327 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "There is an objective function offet of %f.\n", SCIPgetTransObjoffset(scip));
2330 /* if the original problem is solved directly, then we call solveBlockProblem with the master problem */
2333 SCIP_CALL( solveBlockProblem(scip, relaxdata->masterprob, relaxdata, timelimit, -1, &solveresult, &objvalue) );
2346 SCIP_CALL( solveBlockProblem(scip, relaxdata->pricingprobs[i], relaxdata, timelimit, i, &solveresult, &objvalue) );
2360 SCIP_CALL( GCGtransformMastersolToOrigsol(scip, SCIPgetBestSol(relaxdata->masterprob), &newsol) );
2364 SCIP_CALL( combineSolutions(scip, &newsol, relaxdata->pricingprobs, relaxdata->npricingprobs) );
2367 /* update lower bound pointer and add solution such that this node will be cut off automatically */
2380 /* if the original problem is solved directly, then we call freeBlockProblem with the master problem */
2469 SCIP_CALL( SCIPduplicateBufferArray(scip, &oldconss, relaxdata->masterconss, relaxdata->nmasterconss) );
2487 SCIP_CALL( SCIPtransformCons(masterprob, relaxdata->convconss[i], &(relaxdata->convconss[i])) );
2554 /* when the original problem should be solved directly, then a decomposition must be made with zero blocks */
2581 SCIPwarningMessage(scip, "No complete decomposition available. Creating basic decomposition.\n");
2591 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Chosen structure has %d blocks", DECdecompGetNBlocks(relaxdata->decomp));
2592 /* every master-only variable internally also counts as linking, but should not be reported as linking variable */
2593 if ( DECdecompGetNLinkingvars(relaxdata->decomp) - DECdecompGetNMastervars(relaxdata->decomp) > 0)
2595 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", %d linking variables", DECdecompGetNLinkingvars(relaxdata->decomp) - DECdecompGetNMastervars(relaxdata->decomp));
2600 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", %d master-only (static) variables", DECdecompGetNMastervars(relaxdata->decomp));
2607 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " and %d linking constraints.\n", DECdecompGetNLinkingconss(relaxdata->decomp));
2608 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "This decomposition has a maxwhite score of %f.\n", DECdecompGetMaxwhiteScore(relaxdata->decomp));
2626 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Warning: Discretization with continuous variables is only an experimental feature.\n");
2631 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Warning: Discretization with continuous variables is disabled by parameter relaxing/gcg/mipdiscretization.\n");
2640 SCIP_CALL( SCIPactivateBenders(relaxdata->masterprob, SCIPfindBenders(relaxdata->masterprob, "gcg"),
2649 SCIP_CALL( SCIPsetObjlimit(relaxdata->masterprob, (int) SCIPgetObjsense(scip) * SCIPgetObjlimit(scip)) );
2782 /** initialize the relaxator and master problem for solving the original problem by Dantzig-Wolfe reformulation and
2828 /** solving process initialization method of relaxator (called when branch and bound process is about to begin) */
2844 /* if the master problem decomposition mode is the same as the original SCIP instance mode, then the master problem
2857 /* alternative verbosity levels are used for the Benders' decomposition and original mode compared to the Dantzig-Wolfe
2860 if( GCGgetDecompositionMode(scip) == DEC_DECMODE_BENDERS || GCGgetDecompositionMode(scip) == DEC_DECMODE_ORIGINAL )
2862 /* first getting the verbosity level for the original problem before setting it to none. While the verbosity level
2872 /* setting the total node limit to 1 for the original SCIP instance. This is because Benders' decomposition solves
2873 * the MIP within the relaxator of the root node. So no branching in the original problem is required.
2878 /* fixing the GCG mode parameter. This ensure that the user does not change this during the solution process. If the
2883 /* Informing the user of the decomposition technique that is being used to solve the original problem */
2887 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "A Dantzig-Wolfe reformulation is applied to solve the original problem.\n");
2891 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "A Benders' decomposition is applied to solve the original problem.\n");
2895 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "No reformulation will be performed. Solving the original model.\n");
2905 /** solving process deinitialization method of relaxator (called before branch and bound process data is freed) */
2924 SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->markedmasterconss), relaxdata->maxmarkedmasterconss);
2961 SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->blockrepresentative), relaxdata->npricingprobs);
2994 /** method to solve the master problem that is used by Dantzig-Wolfe and Benders' decomposition */
3036 mastertimelimit = (timelimit - SCIPgetSolvingTime(scip)) * 1.02 + SCIPgetSolvingTime(masterprob);
3045 /* if we have a blockdetection, see whether the node is block diagonal. Additionally, the solveDiagonalBlocks can
3048 if( DECdecompGetType(relaxdata->decomp) == DEC_DECTYPE_DIAGONAL || GCGgetDecompositionMode(scip) == DEC_DECMODE_ORIGINAL )
3070 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "time for master problem was too short, extending time by %f.\n", mastertimelimit - SCIPgetSolvingTime(masterprob));
3086 assert(SCIPgetStatus(masterprob) == SCIP_STATUS_TIMELIMIT || SCIPgetBestSol(masterprob) != NULL || SCIPgetStatus(masterprob) == SCIP_STATUS_INFEASIBLE || SCIPgetStatus(masterprob) == SCIP_STATUS_UNKNOWN);
3087 if( SCIPgetStatus(masterprob) == SCIP_STATUS_OPTIMAL && GCGmasterIsCurrentSolValid(masterprob) )
3089 else if( SCIPgetStatus(masterprob) == SCIP_STATUS_INFEASIBLE || SCIPgetStatus(masterprob) == SCIP_STATUS_TIMELIMIT || !GCGmasterIsCurrentSolValid(masterprob) )
3115 /* NOTE: All other points when result is set, the function is exited immediately. Ensure that this is checked for
3152 SCIPdebugMessage("Solving node %"SCIP_LONGINT_FORMAT"'s relaxation.\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
3173 SCIP_CALL( SCIPtrySol(scip, relaxdata->currentorigsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
3176 /* if a new primal solution was found in the master problem, transfer it to the original problem */
3177 if( SCIPgetBestSol(relaxdata->masterprob) != NULL && relaxdata->lastmastersol != SCIPgetBestSol(relaxdata->masterprob) && GCGmasterIsCurrentSolValid(masterprob) )
3194 /** @bug The solution doesn't have to be accepted, numerics might bite us, so the transformation might fail.
3205 SCIP_CALL( GCGrelaxBranchMasterSolved(scip, GCGconsOrigbranchGetBranchrule(GCGconsOrigbranchGetActiveCons(scip) ),
3213 SCIPdebugMessage(" root node time clock stopped at %6.2fs.\n", SCIPgetClockTime(scip, relaxdata->rootnodetime));
3225 /** method to solve the master problem for Benders' decomposition and when solving the original problem directly. */
3250 SCIPdebugMessage("Solving node %"SCIP_LONGINT_FORMAT"'s relaxation.\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
3252 /* prior to performing the decomposition the original problem verbosity is changed to NONE. This avoids output from
3253 * the original problem before the decomposition output. Once the decomposition has been performed, then the
3259 /* getting the node limit from the original problem. This is because the master problem is solved to optimality in
3267 /* if the master problem has been detected as infeasible, then the result must be set to SCIP_CUTOFF. */
3271 /* if the master problem has been solved to optimality, the we cutoff the root node. This informs that original
3279 /* if there is no primal solution for the original problem, then the master solution is transferred */
3280 if( SCIPgetBestSol(relaxdata->masterprob) != NULL && relaxdata->lastmastersol != SCIPgetBestSol(relaxdata->masterprob) )
3287 SCIP_CALL( GCGtransformMastersolToOrigsol(scip, SCIPgetBestSol(relaxdata->masterprob), &newsol) );
3298 /** @bug The solution doesn't have to be accepted, numerics might bite us, so the transformation might fail.
3309 && (SCIPgetStage(masterprob) == SCIP_STAGE_SOLVED || SCIPgetStage(masterprob) == SCIP_STAGE_SOLVING) )
3314 /* if the time, memory or node limit is hit in the Original or Benders mode, then we need to interrupt the solve.
3315 * This is required because the original problem is not solved in either of these modes, so it is not certain that
3318 if( SCIPgetStatus(masterprob) == SCIP_STATUS_TIMELIMIT || SCIPgetStatus(masterprob) == SCIP_STATUS_NODELIMIT
3324 /* if the result pointer is DIDNOTRUN, this implies that the master problem was interrupted during solving. Since
3325 * Benders' decomposition uses a one-tree approach, then the user limits must be adhered to. This means, the if a
3384 /* checking whether the relaxator needs to be initialised. If so, then the master problem and pricing problems will
3389 /* selecting the solving algorithm based upon the decomposition mode selected by the user, or whether the original
3394 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "There are no pricing problems in the decomposition. The original problem will be solved directly.\n");
3407 SCIPverbMessage(scip, SCIP_VERBLEVEL_DIALOG, NULL, "Sorry, the automatic selection is not currently available\n");
3432 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, name, "A Tool for Computing Automorphism Groups of Graphs by T. Junttila and P. Kaski (http://www.tcs.hut.fi/Software/bliss/)") );
3437 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, "Cliquer", "A set of C routines for finding cliques in an arbitrary weighted graph by S. Niskanen and P. Ostergard (https://users.aalto.fi/~pat/cliquer.html)") );
3455 SCIP_CALL( SCIPincludeRelax(scip, RELAX_NAME, RELAX_DESC, RELAX_PRIORITY, RELAX_FREQ, relaxCopyGcg, relaxFreeGcg, relaxInitGcg,
3465 /* initialize the scip data structure for the master problem. The master problem is initialized as the Dantzig-Wolfe
3466 * master problem. The alternate master problem is initialized as the Benders' decomposition master problem.
3477 SCIP_CALL( SCIPsetIntParam(relaxdata->masterprob, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
3492 /* initializing the alternate master problem. The alternate master problem is initially the Benders' decomposition
3500 SCIP_CALL( SCIPsetIntParam(relaxdata->altmasterprob, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
3508 "should discretization (TRUE) or convexification (FALSE) approach be used in mixed-integer programs?",
3517 "the decomposition mode that GCG will use. (0: Dantzig-Wolfe (default), 1: Benders' decomposition, "
3526 &(relaxdata->searchnodelimit), TRUE, (int)DEFAULT_BLISS_SEARCH_NODE_LIMIT, 0, INT_MAX, NULL, NULL) );
3529 &(relaxdata->generatorlimit), TRUE, (int)DEFAULT_BLISS_GENERATOR_LIMIT, 0, INT_MAX, NULL, NULL) );
3549 GCG_DECL_BRANCHDEACTIVEMASTER((*branchdeactivemaster)),/**< deactivation method for branchrule */
3552 GCG_DECL_BRANCHDATADELETE((*branchdatadelete))/**< branchdata deletion method for branchrule */
3650 SCIP_CALL( relaxdata->branchrules[i]->branchdeactivemaster(relaxdata->masterprob, branchdata) );
3692 SCIP_CALL( relaxdata->branchrules[i]->branchpropmaster(relaxdata->masterprob, branchdata, result) );
3872 SCIP_CALL( GCGmasterAddMasterconsToHashmap(relaxdata->masterprob, relaxdata->masterconss[relaxdata->nmasterconss],
3893 /* retrieving the Benders' decomposition and the pricer plugins. There should only be one or the other for a given
3998 /** returns TRUE iff the pricing problem of the given number is relevant, that means is not identical to
4116 /** returns the linking constraints in the original problem that correspond to the constraints in the master problem */
4329 * @note A corresponding probing node must be added to the master problem right before solving the probing LP
4360 /* add a probing node in the original problem together with an original branching constraint */
4376 * furthermore, this method must be called after bound changes to the original problem have been made
4424 * which ensures that bound changes are transferred to master and pricing problems as well as additional
4428 * furthermore, this method must be called after bound changes to the original problem have been made
4473 GCGconsMasterbranchGetActiveCons(masterprob), branchrule, branchdata, origbranchconss, norigbranchconss, maxorigbranchconss) );
4486 int probingdepth /**< probing depth of the node in the probing path that should be reactivated */
4523 SCIP_Longint* nlpiterations, /**< pointer to store the number of performed LP iterations (or NULL) */
4580 SCIP_CALL( SCIPsolveProbingLPWithPricing(masterprob, FALSE, TRUE, maxpricerounds, lperror, NULL) );
4601 *cutoff = *cutoff || (lpsolstat == SCIP_LPSOLSTAT_OBJLIMIT || lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE);
4623 SCIP_Longint* nlpiterations, /**< pointer to store the number of performed LP iterations (or NULL) */
4642 SCIP_Longint* nlpiterations, /**< pointer to store the number of performed LP iterations (or NULL) */
4696 /* if a new primal solution was found in the master problem, transfer it to the original problem
4699 if( SCIPgetBestSol(masterprob) != NULL && relaxdata->lastmastersol != SCIPgetBestSol(masterprob) )
4750 assert(SCIPisFeasEQ(scip, SCIPgetRelaxSolObj(scip), SCIPgetSolTransObj(scip, relaxdata->currentorigsol)));
4763 /** checks whether a variable shoudl be added as an external branching candidate, if so it is added */
4773 if( SCIPvarGetType(var) <= SCIP_VARTYPE_INTEGER && !SCIPisFeasIntegral(scip, SCIPgetRelaxSolVal(scip, var)) )
4777 SCIPdebugMessage("lblocal = %g, ublocal = %g\n", SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
4778 SCIPdebugMessage("var = %s, vartype = %d, val = %g\n", SCIPvarGetName(var), SCIPvarGetType(var),
4832 if( SCIPgetStage(relaxdata->masterprob) == SCIP_STAGE_SOLVED || SCIPgetLPSolstat(relaxdata->masterprob) == SCIP_LPSOLSTAT_OPTIMAL )
4860 if( !SCIPisInfinity(scip, SCIPgetSolOrigObj(relaxdata->masterprob, mastersol)) && GCGmasterIsSolValid(relaxdata->masterprob, mastersol) )
4870 assert(SCIPisEQ(scip, SCIPgetRelaxSolObj(scip), SCIPgetSolTransObj(scip, relaxdata->currentorigsol)));
4873 SCIP_CALL( SCIPtrySol(scip, relaxdata->currentorigsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
4877 SCIPdebugMessage("updated current original LP solution, %s feasible in the original problem!\n",
4883 /* in the case of Benders decomposition, only the master variables can be added as branching candidates */
4945 /* @todo replace the computation by relaxdata->pricingprobsmemused if we can assure that the memory
5141 /** returns the decomposition mode of the master problem. The mode is given by the existence of either the GCG pricer or
5154 /* retrieving the Benders' decomposition and the pricer plugins. There should only be one or the other for a given
5162 /* both the Benders' master and the original master have the Benders' decomposition included. */
5173 SCIPerrorMessage("Sorry, the decomposition mode of the master problem is invalid. This should not happen.");
5304 SCIPverbMessage(scip, SCIP_VERBLEVEL_DIALOG, NULL, "The detection for the original problem took place already.\n");
5316 SCIPverbMessage(scip, SCIP_VERBLEVEL_DIALOG, NULL, "The detection for the presolved problem took place already.\n");
5372 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "there is an original decomposition and problem is not presolved yet -> disable presolving and start optimizing (rerun with presolve command before detect command for detecting in presolved problem) \n");
5384 if( !GCGdetectionTookPlace(scip, TRUE) && !GCGdetectionTookPlace(scip, FALSE) && GCGconshdlrDecompGetNFinishedPartialdecsTransformed(scip) == 0 )
5391 assert(bestdecomp == NULL && (GCGdetectionTookPlace(scip, TRUE) || GCGdetectionTookPlace(scip, FALSE)));
5393 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "No decomposition exists or could be detected. Solution process started with original problem...\n");
5396 else if( !GCGdetectionTookPlace(scip, TRUE) && !GCGdetectionTookPlace(scip, FALSE) && GCGconshdlrDecompGetNFinishedPartialdecsTransformed(scip) > 0 )
5404 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Preexisting decomposition found. Solution process started...\n");
SCIP_Bool GCGconshdlrDecompOrigPartialdecExists(SCIP *scip)
returns whether or not an original decompositions exists in the data structures
Definition: cons_decomp.cpp:5683
SCIP_RETCODE GCGoriginalVarAddBlock(SCIP *scip, SCIP_VAR *var, int newblock, int nblocks, DEC_DECMODE mode)
Definition: gcgvar.c:726
GCG interface methods.
static SCIP_RETCODE freeBlockProblem(SCIP *scip, SCIP *blockprob, SCIP_RELAXDATA *relaxdata, int blocknum)
Definition: relax_gcg.c:2266
SCIP_RETCODE GCGrelaxNewProbingnodeMasterCons(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss, int maxorigbranchconss)
Definition: relax_gcg.c:4430
GCG_BRANCHDATA * GCGconsOrigbranchGetBranchdata(SCIP_CONS *cons)
Definition: cons_origbranch.c:585
SCIP_RETCODE GCGrelaxPerformProbing(SCIP *scip, int maxlpiterations, SCIP_Longint *nlpiterations, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4620
void GCGlinkingVarSetLinkingCons(SCIP_VAR *var, SCIP_CONS *cons, int index)
Definition: gcgvar.c:806
int GCGconshdlrDecompGetNFormerDetectionConssForID(SCIP *scip, int id)
gets number of active constraints during the detection of the decomp with given id
Definition: cons_decomp.cpp:5374
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4202
static SCIP_RETCODE solveMasterProblem(SCIP *scip, SCIP *masterprob, SCIP_RELAXDATA *relaxdata, SCIP_Longint nodelimit, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:2996
static SCIP_RETCODE checkIdentical(SCIP *scip, SCIP_RELAXDATA *relaxdata, int probnr1, int probnr2, SCIP_HASHMAP *varmap, SCIP_Bool *identical, SCIP *scip1, SCIP *scip2)
Definition: relax_gcg.c:621
static SCIP_RETCODE combineSolutions(SCIP *scip, SCIP_SOL **newsol, SCIP **probs, int nprobs)
Definition: relax_gcg.c:2015
SCIP_RETCODE GCGrelaxBranchMasterSolved(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_Real newlowerbound)
Definition: relax_gcg.c:3749
SCIP_RETCODE GCGrelaxNewProbingnodeMaster(SCIP *scip)
Definition: relax_gcg.c:4378
static SCIP_RETCODE createPricingProblem(SCIP **pricingscip, const char *name, int clocktype, SCIP_Real infinity, SCIP_Real epsilon, SCIP_Real sumepsilon, SCIP_Real feastol, SCIP_Real lpfeastolfactor, SCIP_Real dualfeastol, SCIP_Bool enableppcuts)
Definition: relax_gcg.c:1536
Definition: struct_decomp.h:51
data structures for branching rules
SCIP_RETCODE GCGrelaxBranchDataDelete(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA **branchdata)
Definition: relax_gcg.c:3704
SCIP_VAR *** DECdecompGetSubscipvars(DEC_DECOMP *decomp)
Definition: decomp.c:823
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:587
SCIP_Bool GCGmasterIsSolValid(SCIP *scip, SCIP_SOL *mastersol)
Definition: pricer_gcg.cpp:5173
static SCIP_RETCODE solveBlockProblem(SCIP *scip, SCIP *blockprob, SCIP_RELAXDATA *relaxdata, SCIP_Real timelimit, int blocknum, SCIP_RESULT *result, SCIP_Real *objvalue)
Definition: relax_gcg.c:2135
unsigned int GCGconshdlrDecompGetNFinishedPartialdecsTransformed(SCIP *scip)
Gets the number of finished partialdecs available for the transformed problem.
Definition: cons_decomp.cpp:5463
SCIP_RETCODE GCGoriginalVarAddCoef(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_CONS *cons)
Definition: gcgvar.c:679
SCIP_Bool GCGisLinkingVarInBlock(SCIP_VAR *var, int block)
Definition: gcgvar.c:1064
SCIP_RETCODE DECpermuteDecomp(SCIP *scip, DEC_DECOMP *decomp, SCIP_RANDNUMGEN *randnumgen)
Definition: decomp.c:4323
SCIP_RETCODE GCGconshdlrDecompSelectPartialdec(SCIP *scip, int partialdecid, SCIP_Bool select)
selects/unselects a partialdecomp
Definition: cons_decomp.cpp:5749
SCIP_RETCODE GCGoriginalVarCreatePricingVar(SCIP *scip, SCIP_VAR *origvar, SCIP_VAR **var)
Definition: gcgvar.c:1213
SCIP_RETCODE GCGcreateConsMasterbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss, int maxorigbranchconss)
Definition: cons_masterbranch.c:2278
SCIP plugins for generic column generation.
SCIP_RETCODE GCGconshdlrDecompCreateVarmapForPartialdecId(SCIP *scip, SCIP_HASHMAP **hashorig2pricingvar, int partialdecid, int probnr1, int probnr2, SCIP *scip1, SCIP *scip2, SCIP_HASHMAP *varmap)
for two identical pricing problems a corresponding varmap is created
Definition: cons_decomp.cpp:4960
constraint handler for structure detection
Definition: params_visu.c:113
int * DECdecompGetNSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:917
static SCIP_RETCODE setOriginalVarBlockNr(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_VAR *var, int newblock)
Definition: relax_gcg.c:181
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:490
SCIP_RETCODE GCGrelaxBranchActiveMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
Definition: relax_gcg.c:3586
SCIP_RETCODE GCGrelaxTransOrigToMasterCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: relax_gcg.c:3789
static SCIP_RETCODE createMaster(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:1841
static SCIP_RETCODE createLinkingPricingVars(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_VAR *origvar)
Definition: relax_gcg.c:1164
SCIP_VAR ** DECdecompGetLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1036
void GCGoriginalVarSetNCoefs(SCIP_VAR *var, int ncoefs)
Definition: gcgvar.c:658
SCIP_CONS ** DECdecompGetLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:967
static SCIP_RETCODE createMasterprobConss(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:1617
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:216
GCG Benders' decomposition.
void GCGgetBlissName(char *buffer, int len)
GCG variable pricer.
SCIP_RETCODE GCGconshdlrDecompArePricingprobsIdenticalForPartialdecid(SCIP *scip, int partialdecid, int probnr1, int probnr2, SCIP_Bool *identical)
checks if two pricing problems are identical based on information from detection
Definition: cons_decomp.cpp:3673
static SCIP_RETCODE transformMaster(SCIP *scip, SCIP_RELAX *relax)
Definition: relax_gcg.c:2446
SCIP_RETCODE GCGrelaxBranchDeactiveMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
Definition: relax_gcg.c:3624
static SCIP_RETCODE ensureSizeBranchrules(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:463
SCIP_RETCODE GCGconshdlrDecompTranslateOrigPartialdecs(SCIP *scip)
translates unpresolved partialdec to a complete presolved one
Definition: cons_decomp.cpp:5858
SCIP_RETCODE GCGincludeBendersPlugins(SCIP *scip)
Definition: bendersplugins.c:44
various SCIP helper methods
#define GCG_DECL_BRANCHDEACTIVEMASTER(x)
Definition: type_branchgcg.h:76
SCIP_RETCODE GCGrelaxUpdateCurrentSol(SCIP *scip)
Definition: relax_gcg.c:4796
static SCIP_RETCODE markConsMaster(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_CONS *cons)
Definition: relax_gcg.c:225
SCIP plugins for the master problem running in Benders' decomposition mode.
static SCIP_RETCODE checkSetppcStructure(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:487
SCIP_CONS * GCGconsOrigbranchGetActiveCons(SCIP *scip)
Definition: cons_origbranch.c:529
SCIP_CONS ** GCGlinkingVarGetLinkingConss(SCIP_VAR *var)
Definition: gcgvar.c:787
static SCIP_RETCODE checkAndAddExternalBranchingCandidate(SCIP *scip, SCIP_VAR *var)
Definition: relax_gcg.c:4765
SCIP_RETCODE GCGconsOrigbranchAddRootCons(SCIP *scip)
Definition: cons_origbranch.c:710
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4000
static SCIP_RETCODE createMasterProblem(SCIP *masterscip, const char *name, int clocktype, SCIP_Real infinity, SCIP_Real epsilon, SCIP_Real sumepsilon, SCIP_Real feastol, SCIP_Real lpfeastolfactor, SCIP_Real dualfeastol, DEC_DECMODE mode)
Definition: relax_gcg.c:1459
SCIP_HASHMAP * DECdecompGetVartoblock(DEC_DECOMP *decomp)
Definition: decomp.c:1199
SCIP_SOL * SCIPbendersGetRelaxSol(SCIP_BENDERS *benders)
Definition: benders_gcg.c:753
SCIP_BRANCHRULE * GCGconsOrigbranchGetBranchrule(SCIP_CONS *cons)
Definition: cons_origbranch.c:598
static SCIP_RETCODE relaxExecGcgOriginalProblem(SCIP *scip, SCIP_RELAX *relax, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:3354
SCIP_Bool GCGisMasterSetPartitioning(SCIP *scip)
Definition: relax_gcg.c:4240
constraint handler for storing the branching decisions at each node of the tree
void GCGoriginalVarSetPricingVar(SCIP_VAR *var, SCIP_VAR *pricingvar)
Definition: gcgvar.c:235
static SCIP_RETCODE pricingprobsAreIdenticalFromDetectionInfo(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_HASHMAP **hashorig2pricingvar, int probnr1, int probnr2, SCIP_HASHMAP *varmap, SCIP_Bool *identical)
Definition: relax_gcg.c:793
SCIP_RETCODE SCIPconshdlrDecompRepairConsNames(SCIP *scip)
Definition: cons_decomp.cpp:5909
SCIP_RETCODE GCGtransformMastersolToOrigsol(SCIP *scip, SCIP_SOL *mastersol, SCIP_SOL **origsol)
Definition: misc.c:120
SCIP_RETCODE GCGoriginalVarAddMasterVar(SCIP *scip, SCIP_VAR *origvar, SCIP_VAR *var, SCIP_Real val)
Definition: gcgvar.c:1121
SCIP_RETCODE GCGmasterAddMasterconsToHashmap(SCIP *scip, SCIP_CONS *cons, int pos)
Definition: pricer_gcg.cpp:4296
SCIP_RETCODE DECcreateBasicDecomp(SCIP *scip, DEC_DECOMP **decomp, SCIP_Bool solveorigprob)
Definition: decomp.c:2388
constraint handler for storing the branching decisions at each node of the tree
SCIP_RETCODE GCGrelaxBacktrackProbing(SCIP *scip, int probingdepth)
Definition: relax_gcg.c:4484
SCIP_RETCODE GCGlinkingVarCreatePricingVar(SCIP *pricingscip, int pricingprobnr, SCIP_VAR *origvar, SCIP_VAR **var)
Definition: gcgvar.c:1250
static SCIP_RETCODE createPricingVar(SCIP_RELAXDATA *relaxdata, SCIP_VAR *origvar)
Definition: relax_gcg.c:1134
SCIP_RETCODE GCGcreateInitialMasterVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **newvar)
Definition: gcgvar.c:1472
DEC_DECMODE GCGgetMasterDecompMode(SCIP *masterprob)
Definition: relax_gcg.c:5144
Definition: struct_branchgcg.h:46
SCIP_RETCODE GCGrelaxBranchPropMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_RESULT *result)
Definition: relax_gcg.c:3662
SCIP_RETCODE DECdetectStructure(SCIP *scip, SCIP_RESULT *result)
interface method to detect the structure including presolving
Definition: cons_decomp.cpp:2627
static SCIP_RETCODE convertStructToGCG(SCIP *scip, SCIP_RELAXDATA *relaxdata, DEC_DECOMP *decomp)
Definition: relax_gcg.c:263
SCIP_SOL * GCGgetBendersRelaxationSol(SCIP *scip)
Definition: relax_gcg.c:5100
SCIP_CONS ** GCGoriginalVarGetMasterconss(SCIP_VAR *var)
Definition: gcgvar.c:710
SCIP_RETCODE GCGrelaxStartProbing(SCIP *scip, SCIP_HEUR *probingheur)
Definition: relax_gcg.c:4264
static SCIP_RETCODE initRelaxProblemdata(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:1425
static SCIP_RETCODE createPricingprobConss(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_HASHMAP **hashorig2pricingvar)
Definition: relax_gcg.c:1753
SCIP_RETCODE GCGrelaxNewProbingnodeOrig(SCIP *scip)
Definition: relax_gcg.c:4331
Definition: relax_gcg.c:100
SCIP_SOL * GCGrelaxGetCurrentOrigSol(SCIP *scip)
Definition: relax_gcg.c:4183
SCIP_Real DECdecompGetMaxwhiteScore(DEC_DECOMP *decomp)
Definition: decomp.c:701
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:621
SCIP_CONS *** DECdecompGetSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:908
static SCIP_RETCODE setPricingObjsOriginal(SCIP *scip, SCIP **probs, int nprobs)
Definition: relax_gcg.c:2069
int GCGgetBlockRepresentative(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4023
static SCIP_RETCODE createPricingVariables(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_HASHMAP **hashorig2pricingvar)
Definition: relax_gcg.c:1275
static SCIP_RETCODE setPricingProblemParameters(SCIP *scip, int clocktype, SCIP_Real infinity, SCIP_Real epsilon, SCIP_Real sumepsilon, SCIP_Real feastol, SCIP_Real lpfeastolfactor, SCIP_Real dualfeastol, SCIP_Bool enableppcuts)
Definition: relax_gcg.c:1038
static SCIP_RETCODE displayPricingStatistics(SCIP *scip, SCIP **pricingprobs, int npricingprobs, int *blockrepresentative)
Definition: relax_gcg.c:1386
automorphism recognition of SCIPs
static SCIP_RETCODE relaxExecGcgDantzigWolfe(SCIP *scip, SCIP_RELAX *relax, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:3126
SCIP_RETCODE GCGcreateConsOrigbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
Definition: cons_origbranch.c:444
SCIP_Real GCGgetPricingprobsMemUsed(SCIP *scip)
Definition: relax_gcg.c:4925
GCG relaxator.
void GCGVisuFreeParams(SCIP *scip, GCG_PARAMDATA *paramdata)
Definition: params_visu.c:695
static SCIP_RETCODE initRelaxator(SCIP *scip, SCIP_RELAX *relax)
Definition: relax_gcg.c:2535
SCIP_RETCODE DECdecompAddRemainingConss(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2179
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
Definition: cons_masterbranch.c:2628
SCIP_RETCODE GCGorigVarCreateData(SCIP *scip, SCIP_VAR *var)
Definition: gcgvar.c:313
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:1015
int GCGconshdlrDecompAddBasicPartialdec(SCIP *scip, SCIP_Bool presolved)
creates and adds a basic partialdecomp (all cons/vars are assigned to master)
Definition: cons_decomp.cpp:3421
SCIP_RETCODE SCIPincludeBendersGcg(SCIP *scip, SCIP *origprob)
Definition: benders_gcg.c:719
SCIP_Bool GCGgetConsIsSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_SETPPCTYPE *setppctype)
Definition: scip_misc.c:763
SCIP_RETCODE GCGpricingVarAddOrigVar(SCIP *scip, SCIP_VAR *pricingvar, SCIP_VAR *origvar)
Definition: gcgvar.c:531
Definition: branch_bpstrong.c:109
SCIP_Bool GCGmasterIsCurrentSolValid(SCIP *scip)
Definition: pricer_gcg.cpp:5090
static SCIP_RETCODE GCGsetStructDecomp(SCIP *scip, DEC_DECOMP *decomp)
Definition: relax_gcg.c:2418
helper functions for automorphism detection
SCIP_RETCODE GCGlinkingVarCreateMasterCons(SCIP *masterscip, int pricingprobnr, SCIP_VAR *origvar, SCIP_CONS **linkcons)
Definition: gcgvar.c:1285
SCIP_RETCODE GCGmasterCreateInitialMastervars(SCIP *scip)
Definition: pricer_gcg.cpp:4980
static SCIP_RETCODE pricingprobsAreIdentical(SCIP *scip, SCIP_RELAXDATA *relaxdata, int probnr1, int probnr2, SCIP_HASHMAP *varmap, SCIP_Bool *identical)
Definition: relax_gcg.c:839
SCIP_RETCODE GCGrelaxPerformProbingWithPricing(SCIP *scip, int maxpricerounds, SCIP_Longint *nlpiterations, int *npricerounds, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4639
static SCIP_RETCODE solveDiagonalBlocks(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_RESULT *result, SCIP_Real *lowerbound)
Definition: relax_gcg.c:2300
static SCIP_RETCODE checkIdenticalBlocks(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_HASHMAP **hashorig2pricingvar)
Definition: relax_gcg.c:896
static SCIP_RETCODE initializeMasterProblemSolve(SCIP *scip, SCIP_RELAX *relax)
Definition: relax_gcg.c:2786
static SCIP_RETCODE ensureSizeMasterConss(SCIP *scip, SCIP_RELAXDATA *relaxdata, int size)
Definition: relax_gcg.c:438
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4053
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3939
SCIP_RETCODE SCIPcreateParamsVisu(SCIP *scip, GCG_PARAMDATA **paramdata)
Definition: params_visu.c:716
SCIP_RETCODE cmpGraphPair(SCIP *origscip, SCIP *scip1, SCIP *scip2, int prob1, int prob2, SCIP_RESULT *result, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, unsigned int searchnodelimit, unsigned int generatorlimit)
Definition: bliss_automorph.cpp:1334
SCIP_RETCODE DECdecompCheckConsistency(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2267
static SCIP_RETCODE relaxExecGcgBendersDecomposition(SCIP *scip, SCIP_RELAX *relax, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:3336
void GCGlinkingVarSetPricingVar(SCIP_VAR *origvar, int pricingprobnr, SCIP_VAR *var)
Definition: gcgvar.c:427
SCIP_VAR ** GCGlinkingVarGetPricingVars(SCIP_VAR *var)
Definition: gcgvar.c:409
SCIP_RETCODE GCGincludeMasterPlugins(SCIP *scip)
Definition: masterplugins.c:192
static SCIP_Bool realArraysAreEqual(SCIP *scip, SCIP_Real *array1, int array1length, SCIP_Real *array2, int array2length)
Definition: relax_gcg.c:590
static SCIP_RETCODE saveOriginalVarMastercoeffs(SCIP *scip, SCIP_VAR **origvars, int norigvars, int nmasterconss, SCIP_CONS **origmasterconss, SCIP_CONS **masterconss)
Definition: relax_gcg.c:1563
static SCIP_RETCODE performProbing(SCIP *scip, int maxlpiterations, int maxpricerounds, SCIP_Bool usepricing, SCIP_Longint *nlpiterations, int *npricerounds, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4518
SCIP_Bool GCGdetectionTookPlace(SCIP *scip, SCIP_Bool original)
Definition: cons_decomp.cpp:5897
SCIP_RETCODE SCIPincludePricerGcg(SCIP *scip, SCIP *origprob)
Definition: pricer_gcg.cpp:4112
static SCIP_RETCODE solveMasterProblemAndEvaluate(SCIP *scip, SCIP_RELAX *relax, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:3227
SCIP_RETCODE GCGrelaxIncludeBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_DECL_BRANCHACTIVEMASTER((*branchactivemaster)), GCG_DECL_BRANCHDEACTIVEMASTER((*branchdeactivemaster)), GCG_DECL_BRANCHPROPMASTER((*branchpropmaster)), GCG_DECL_BRANCHMASTERSOLVED((*branchmastersolved)), GCG_DECL_BRANCHDATADELETE((*branchdatadelete)))
Definition: relax_gcg.c:3545
SCIP_Bool GCGconshdlrDecompCheckConsistency(SCIP *scip)
check whether partialdecs are consistent
Definition: cons_decomp.cpp:4766
DEC_DECOMP * DECgetBestDecomp(SCIP *scip, SCIP_Bool printwarnings)
Gets the best known decomposition.
Definition: cons_decomp.cpp:2898