Code using a sub-IP to find "cluster constraint" cutting planes. More...
Macros | |
| #define | max(A, B) ((A) > (B) ? (A) : (B)) |
| #define | min(A, B) ((A) < (B) ? (A) : (B)) |
Functions | |
| static SCIP_RETCODE | AddClusterCut (SCIP *scip, const ParentSetData *psd, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *incluster, int cluster_size, int kval, SCIP_Bool addtopool, SCIP_Bool forcecuts, SCIP_Bool *found_efficacious_ptr, SCIP_Bool ci_cut, SCIP_Bool matroidpaircuts, int matroidpaircutslimit, int matroidpairmaxcuts, SCIP_Real excess, SCIP_Bool *cutoff) |
| Given a cluster, finds family variables for that cluster and adds the cluster cut. More... | |
| static SCIP_RETCODE | FindFamilyVarsinClusterCut (SCIP *scip, const ParentSetData *psd, const SCIP_Bool *incluster, int cluster_size, int **cluster, ParentSetData **outpsd) |
| static SCIP_RETCODE | FindPairs (SCIP *scip, const ParentSetData *old_psd, const ParentSetData *psd, const int *cluster, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int maxcuts, SCIP_Bool addtopool, SCIP_Bool forcecuts, SCIP_Bool *found_efficacious_ptr, SCIP_Real excess, SCIP_Bool *cutoff) |
| Find which variables in a cluster can be paired to give an efficacious cut. More... | |
| static void | inc_loss (SCIP_Real **loss, int a, int b, SCIP_Real inc) |
| SCIP_RETCODE | IP_findCuts (SCIP *scip, ParentSetData *psd, SolutionInfo *solinfo, SCIP_SOL *sol, int *nGen, int k_lb, int k_ub, SCIP_CONSHDLR *conshdlr, SCIP_Bool addtopool, SCIP_Bool forcecuts, SCIP_Bool *found_efficacious_ptr, SCIP_Real limits_time, SCIP_Real limits_gap, SCIP_Real limits_absgap, SCIP_Bool incumbent_cons, int *must_be_included, int n_must_be_included, int *must_be_excluded, int n_must_be_excluded, SCIP_Bool ci_cut, SCIP_Bool matroidpaircuts, int matroidpaircutslimit, int matroidpairmaxcuts, SCIP_Bool *cutoff) |
| main routine for looking for cutting planes More... | |
| static SCIP_Bool | stays (const ParentSetData *psd, int a, int b, int i, int k) |
Detailed Description
Code using a sub-IP to find "cluster constraint" cutting planes.
Function Documentation
◆ AddClusterCut()
|
static |
Given a cluster, finds family variables for that cluster and adds the cluster cut.
- Parameters
-
scip (Main) SCIP instance psd family variable information conshdlr the constraint handler responsible for adding these cuts (will be 'dagcluster') sol solution to be separated incluster the cluster itself: incluster[i] = TRUE iff i is in the cluster cluster_size the size of the found cluster kval kval = 1 for normal cluster cuts, kval = k for a 'k-cluster cut' addtopool whether to add the cut to the global cut pool forcecuts whether to force cuts to be added found_efficacious_ptr for recording whether the cutting plane is efficacious ci_cut whether we are adding a CI cut cutoff cutoff = TRUE if a cut is added which leads to a cutoff ( set by SCIPaddRow )
References ParentSetData::n, and ParentSetData::PaVars.
Referenced by IP_findCuts().
◆ FindFamilyVarsinClusterCut()
|
static |
- Parameters
-
scip (Main) SCIP instance psd family variable information incluster the cluster itself: incluster[i] = TRUE iff i is in the cluster cluster_size the size of the found cluster cluster (*cluster)[i] will be the ith cluster member outpsd family variables in the cut
References ParentSetData::n, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, and ParentSetData::PaVars.
◆ FindPairs()
|
static |
Find which variables in a cluster can be paired to give an efficacious cut.
- Parameters
-
scip (Main) SCIP instance old_psd original family variable information psd specialised family variable information cluster the cluster conshdlr the constraint handler responsible for adding these cuts (will be 'dagcluster') sol solution to be separated maxcuts the maximum number of cuts to add (in this function) addtopool whether to add the cut to the global cut pool forcecuts whether to force cuts to be added found_efficacious_ptr for recording whether the cutting plane is efficacious cutoff cutoff = TRUE if a cut is added which leads to a cutoff ( set by SCIPaddRow )
References ParentSetData::n, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, and ParentSetData::PaVars.
◆ IP_findCuts()
| SCIP_RETCODE IP_findCuts | ( | SCIP * | scip, |
| ParentSetData * | psd, | ||
| SolutionInfo * | solinfo, | ||
| SCIP_SOL * | sol, | ||
| int * | nGen, | ||
| int | k_lb, | ||
| int | k_ub, | ||
| SCIP_CONSHDLR * | conshdlr, | ||
| SCIP_Bool | addtopool, | ||
| SCIP_Bool | forcecuts, | ||
| SCIP_Bool * | found_efficacious_ptr, | ||
| SCIP_Real | limits_time, | ||
| SCIP_Real | limits_gap, | ||
| SCIP_Real | limits_absgap, | ||
| SCIP_Bool | incumbent_cons, | ||
| int * | must_be_included, | ||
| int | n_must_be_included, | ||
| int * | must_be_excluded, | ||
| int | n_must_be_excluded, | ||
| SCIP_Bool | ci_cut, | ||
| SCIP_Bool | matroidpaircuts, | ||
| int | matroidpaircutslimit, | ||
| int | matroidpairmaxcuts, | ||
| SCIP_Bool * | cutoff | ||
| ) |
main routine for looking for cutting planes
The number of found cutting planes is recorded in *nGen. A positive value indicates that the current solution is infeasible.
< sub MIP for finding good clusters for cutting planes
< subIP variables: family[i][k] = 1 if kth parent set of ith variable is one of those in cluster cut
< subIP variables: incluster[i] if variable i in cluster
< lower bound on number of parents to be in cluster for family variable to be set
< clausecons[i][k] is the constraint "if family[i][k]=1 then incluster[i]=1"
< overlapcons[i][k] is the constraint "if family[i][k]=1 then \sum_{u \in W} >= kvar"
< constraint for lb for cluster size (depends on kvar)
< (optional) constraint that incumbent must lie on cluster cut
- Parameters
-
scip SCIP data structure psd family variable information solinfo information about the solution to be separated sol solution to be separated nGen *nGen is number of cutting planes added ( even non-efficacious ones are added ) k_lb lowerbound on 'k' values for k-cluster searching, always positive k_ub upperbound on 'k' values for k-cluster searching conshdlr constraint handler addtopool whether to add any found cut to the global cut pool forcecuts whether to force cuts to be added found_efficacious_ptr to return whether an efficacious cutting plane was found limits_time limit on how long to spend sub-IP solving limits_gap limit on size of gap in sub-IP limits_absgap limit on size of the absolute gap in sub-IP incumbent_cons whether to consider only cutting planes on which the incumbent lies must_be_included set of nodes which must be included in any found cluster n_must_be_included size of the set of nodes which must be included in any found cluster must_be_excluded set of nodes which must be excluded from any found cluster n_must_be_excluded size of the set of nodes which must be excluded from any found cluster ci_cut TRUE if we are looking for conditional independence cuts cutoff cutoff = TRUE if a cut is added which leads to a cutoff ( set by SCIPaddRow )
References AddClusterCut(), SolutionInfo::lpsolvals, ParentSetData::n, ParentSetData::nParents, ParentSetData::nParentSets, SolutionInfo::nposvars, scored_parentset::nvars, ParentSetData::ParentSets, ParentSetData::PaVars, and SolutionInfo::posvars.
