solver_cliquer.c
Go to the documentation of this file.
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
51 #define SOLVER_DESC "heuristic solver for pricing problems that solves independent set problems with cliquer"
91 /** Returns whether 2 variables are linked, either simply or in a transitive way in respect to a given linkmatrix matrix.
99 int* vartrace, /**< Array to keep track of which nodes have already been visited during recursion */
133 return areVarsLinkedRec(linkmatrix,SCIPvarGetProbindex(linkedvars[i]),vindex2,vartrace,traceindex,linkedvars,nlinkedvars);
141 /** Wrapper function for areVarsLinkedRec, mallocs and cleans up the necessary memory and passes through the result */
175 varslinked = areVarsLinkedRec(linkmatrix,vindex1,vindex2,vartrace,traceindex,linkedvars,nlinkedvars);
182 /** Update transitivity in the linkmatrix matrix between 2 variables that are to be linked and all linked variables */
201 /* Check if the variables are part of a link already, add them elsewise to the linkedvars array */
233 /* It is sufficient to check the links between var1 and all other vars, since var1 and var2 are linked */
266 /** Returns the node index of a given variable in the bijection or that of a linked variable, if any. */
306 /** Add a variable to the bijection graph g and indsetvars array. Returns the index of the corresponding node in the graph. */
323 nodeindex = getLinkedNodeIndex(scip,consvar,indsetvars,*indexcount,linkmatrix,linkedvars,nlinkedvars);
335 g->weights[*indexcount] = 1 + abs((int) (scalingfactor * SCIPvarGetObj(indsetvars[*indexcount])));
351 SCIP_Real* solvals, /**< Array holding the current solution values of all variables of the problem */
400 /** Scale the objective coefficients of the variables maximally s.t. they become integral and the sum of values does not exceed INT_MAX */
436 /* Basic idea of the heuristic solver: The biggest independent set in a graph corresponds to the biggest clique
437 * of the complement graph, for which we use the cliquer library to find it. We therefore transform the variables
438 * into graph nodes and delete the edge between two nodes if there is an independent set constraint involving both.
439 * By doing this, they cannot both be part of the maximum clique and thus not be both part of the independent set.
440 * The correspondence between variables and graph nodes is done by a bijection using the indsetvars array:
441 * The variable indsetvars[i] is the i-th node of the graph, indexcount keeps track of the next unmapped graph node.
442 * There is also the possibility that two variables x and y are linked with an equality constraint x-y = 0 due to
443 * Ryan-Foster-Branching. In this case, all linked variables are mapped to the same node. There are functions
446 * Since we want to add a column with the best reduced cost, we take the objective coefficient of variables into
447 * account by giving their graph nodes corresponding weights and searching for a weight-maximal clique.
449 * If you would like to add the handling of more types of constraints, please note that the current code
557 /* Build complementary graph by first creating a complete graph and then deleting edges of IS constraints. */
558 /* Size is first chosen to be maximal and then later cropped down to the actual number of nodes. */
575 /* Check for "same"-constraints present in Ryan-Foster-Branching and save the links between the variables. */
584 if( SCIPisEQ(pricingprob, SCIPgetLhsVarbound(pricingprob,constraints[i]), SCIPgetRhsVarbound(pricingprob,constraints[i])) )
587 if( (SCIPgetRhsVarbound(pricingprob,constraints[i]) == 0) && (SCIPgetVbdcoefVarbound(pricingprob,constraints[i]) == -1) )
592 /* Since the vars may not be part of the graph, we have to be able to set their solval later, thus we save the constraint */
600 /* All links have to be established first before we can add nodes to the graph, else pairs (a,b) and (c,d) would be mapped to different nodes */
601 /* if link (b,c) is present but later in the list. We have to run through the constraints again as the linked variables need to be assigned to nodes */
606 if( SCIPisEQ(pricingprob, SCIPgetLhsVarbound(pricingprob,markedconstraints[i]), SCIPgetRhsVarbound(pricingprob,markedconstraints[i])) )
609 if( (SCIPgetRhsVarbound(pricingprob,markedconstraints[i]) == 0) && (SCIPgetVbdcoefVarbound(pricingprob,markedconstraints[i]) == -1) )
612 nodeindex0 = addVarToGraph(pricingprob,g,vconsvars[0],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
629 if( !SCIPisEQ(pricingprob,SCIPgetLhsLinear(pricingprob,constraints[i]),SCIPgetRhsLinear(pricingprob,constraints[i])) )
635 /* Preprocessing: Constraint is only relevant for pricing if one of the variables has an objective value < 0 */
636 if( SCIPisLT(pricingprob,SCIPvarGetObj(lconsvars[0]),0) || SCIPisLT(pricingprob,SCIPvarGetObj(lconsvars[1]),0)
637 || (getLinkedNodeIndex(pricingprob,lconsvars[0],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1 &&
638 getLinkedNodeIndex(pricingprob,lconsvars[1],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1) )
642 nodeindex0 = addVarToGraph(pricingprob,g,lconsvars[0],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
646 nodeindex0 = getLinkedNodeIndex(pricingprob,lconsvars[0],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars);
651 nodeindex1 = addVarToGraph(pricingprob,g,lconsvars[1],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
655 nodeindex1 = getLinkedNodeIndex(pricingprob,lconsvars[1],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars);
672 /* Handle other constraints that behave like IS constraints, i.e. cx+dy<=rhs with c+d>rhs, c>0, d>0 */
673 else if( SCIPgetNVarsLinear(pricingprob,constraints[i]) == 2 && consvals[0] > 0 && consvals[1] > 0
674 && SCIPisLT(pricingprob, SCIPgetRhsLinear(pricingprob,constraints[i]),consvals[0] + consvals[1])
681 nodeindex0 = addVarToGraph(pricingprob,g,lconsvars[0],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
685 nodeindex0 = getLinkedNodeIndex(pricingprob,lconsvars[0],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars);
690 nodeindex1 = addVarToGraph(pricingprob,g,lconsvars[1],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
694 nodeindex1 = getLinkedNodeIndex(pricingprob,lconsvars[1],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars);
731 if( !(coefindex == -1) && SCIPisEQ(pricingprob,SCIPgetRhsLinear(pricingprob,constraints[i]),1) )
738 if( SCIPisLT(pricingprob,SCIPvarGetObj(lconsvars[j]),0) || getLinkedNodeIndex(pricingprob,lconsvars[j],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1 )
740 nodeindex0 = addVarToGraph(pricingprob,g,lconsvars[j],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
745 || getLinkedNodeIndex(pricingprob,lconsvars[k],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1))
747 nodeindex1 = addVarToGraph(pricingprob,g,lconsvars[k],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
762 else if( !(coefindex == -1) && SCIPisEQ(pricingprob,SCIPgetRhsLinear(pricingprob,constraints[i]), 0.0) )
764 /* Special case: The coupling constraint is purely decorative (coefficient + 1 of coupling var >= #vars)*/
768 /* If the node is part of the maximum clique, it is safe to set it to one, so we simply add it to the graph */
769 nodeindex0 = addVarToGraph(pricingprob,g,lconsvars[coefindex],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
778 /* If the node is part of the maximum clique, it is safe to set it to one, so we simply add it to the graph */
780 nodeindex0 = addVarToGraph(pricingprob,g,lconsvars[coefindex],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
785 /* Delete the edges between all the variables of the constraint that are not the coupling variable.
791 || getLinkedNodeIndex(pricingprob,lconsvars[j],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1) )
794 nodeindex0 = addVarToGraph(pricingprob,g,lconsvars[j],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
799 || getLinkedNodeIndex(pricingprob,lconsvars[k],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1))
801 nodeindex1 = addVarToGraph(pricingprob,g,lconsvars[k],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
849 if( SCIPisLT(pricingprob,SCIPgetVbdcoefVarbound(pricingprob,constraints[i]),-1) || SCIPisEQ(pricingprob,SCIPgetVbdcoefVarbound(pricingprob,constraints[i]),-1) )
852 if( SCIPisLT(pricingprob,SCIPvarGetObj(vconsvars[0]),0) || getLinkedNodeIndex(pricingprob,vconsvars[0],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1 )
854 nodeindex0 = addVarToGraph(pricingprob,g,vconsvars[0],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
855 nodeindex1 = addVarToGraph(pricingprob,g,vconsvars[1],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
856 /* It may be the case, that both the constraints x - y <= 0 and x + y <= 1 are part of the problem */
866 nodeindex1 = addVarToGraph(pricingprob,g,vconsvars[1],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
869 /* If none of the nodes are relevant, force x to be zero, since the constraint would be violated if x = 1 and y = 0 */
875 SCIPdebugMessage("Exit: Coefficient of Varbound unhandled Rhs: %g, Coeff: %g.\n",SCIPgetRhsVarbound(pricingprob,constraints[i]),SCIPgetVbdcoefVarbound(pricingprob,constraints[i]));
882 * The constraint may also be of the form c + 1 > rhs and c < rhs, i.e. a non-standard IS-constraint.
885 else if( (SCIPisEQ(pricingprob,SCIPgetRhsVarbound(pricingprob,constraints[i]),1) && SCIPisEQ(pricingprob,SCIPgetVbdcoefVarbound(pricingprob,constraints[i]),1))
886 || (SCIPisLT(pricingprob,SCIPgetRhsVarbound(pricingprob,constraints[i]),SCIPgetVbdcoefVarbound(pricingprob,constraints[i]) + 1)
887 && SCIPisLT(pricingprob,SCIPgetVbdcoefVarbound(pricingprob,constraints[i]), SCIPgetRhsVarbound(pricingprob,constraints[i]))) )
889 /* Preprocessing: Constraint is only relevant for pricing if one of the variables has an objective value < 0 */
890 if( SCIPisLT(pricingprob,SCIPvarGetObj(vconsvars[0]),0) || SCIPisLT(pricingprob,SCIPvarGetObj(vconsvars[1]),0)
891 || (getLinkedNodeIndex(pricingprob,vconsvars[0],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1 &&
892 getLinkedNodeIndex(pricingprob,vconsvars[1],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars) != -1) )
896 nodeindex0 = addVarToGraph(pricingprob,g,vconsvars[0],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
900 nodeindex0 = getLinkedNodeIndex(pricingprob,vconsvars[0],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars);
905 nodeindex1 = addVarToGraph(pricingprob,g,vconsvars[1],&indexcount,scalingfactor,indsetvars,linkmatrix,linkedvars,nlinkedvars);
909 nodeindex1 = getLinkedNodeIndex(pricingprob,vconsvars[1],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars);
929 SCIPdebugMessage("Exit: Rhs of Varbound unhandled, Rhs: %g, Coeff:%g.\n",SCIPgetRhsVarbound(pricingprob,constraints[i]),SCIPgetVbdcoefVarbound(pricingprob,constraints[i]));
935 else if( SCIPisEQ(pricingprob, SCIPgetLhsVarbound(pricingprob,constraints[i]), SCIPgetRhsVarbound(pricingprob,constraints[i])) )
938 if( !((SCIPgetRhsVarbound(pricingprob,constraints[i]) == 0) && (SCIPgetVbdcoefVarbound(pricingprob,constraints[i]) == -1)) )
941 SCIPdebugMessage("Exit: Unhandled equality constraint, c: %g, rhs: %g.\n", SCIPgetVbdcoefVarbound(pricingprob,constraints[i]), SCIPgetRhsVarbound(pricingprob,constraints[i]));
949 SCIPdebugMessage("Exit: Varbound of type lhs <= x+c*y, c: %g, rhs: %g.\n", SCIPgetVbdcoefVarbound(pricingprob,constraints[i]), SCIPgetRhsVarbound(pricingprob,constraints[i]));
985 SCIPdebugMessage("Exit: Density criteria not met,density: %g.\n",(float)nedges / ((float)(g->n - 1) * (g->n) / 2));
999 /* Clean up the graph. If a variable's solval has been set to 0, it should not be part of the max clique */
1000 /* We enforce this by isolating the node and setting its weight to 1 as nodes cannot be deleted */
1005 nodeindex0 = getLinkedNodeIndex(pricingprob,pricingprobvars[i],indsetvars,indexcount,linkmatrix,linkedvars,nlinkedvars);
1037 /* Coupling variables were pre-set to -2.0, if they are part of the maximum clique, we enable them.
1040 if( SET_CONTAINS(clique,i) && (SCIPisLT(pricingprob,SCIPvarGetObj(indsetvars[i]),0) || solvals[SCIPvarGetProbindex(indsetvars[i])] == -2.0)
1061 /* Handle the case of marked inequality constraints of type x - y <= 0 in combination with x + y <= 1 -Constraints */
1067 if( (solvals[SCIPvarGetProbindex(vconsvars[0])] == 1) && (solvals[SCIPvarGetProbindex(vconsvars[1])] == 0) )
1077 && SCIPisEQ(pricingprob, SCIPgetLhsVarbound(pricingprob,markedconstraints[i]), SCIPgetRhsVarbound(pricingprob,markedconstraints[i])) )
1079 if( solvals[SCIPvarGetProbindex(vconsvars[0])] == 0 || solvals[SCIPvarGetProbindex(vconsvars[1])] == 0 )
1085 /* One or both of the vars are unset and the other one, if not -1, is forced to be 1, thus we can set both to 1 */
1091 /* There may be variables left which are unconstrained. We set these to 1 manually if they have an objective value < 0*/
1108 SCIP_CALL( GCGcreateGcgCol(pricingprob, &col, probnr, pricingprobvars, solvals, npricingprobvars, FALSE, SCIPinfinity(pricingprob)) );
static int addVarToGraph(SCIP *scip, graph_t *g, SCIP_VAR *consvar, int *indexcount, SCIP_Real scalingfactor, SCIP_VAR **indsetvars, int **linkmatrix, SCIP_VAR **linkedvars, int nlinkedvars)
Definition: solver_cliquer.c:308
SCIP_RETCODE GCGcreateGcgCol(SCIP *pricingprob, GCG_COL **gcgcol, int probnr, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Bool isray, SCIP_Real redcost)
Definition: gcgcol.c:52
static GCG_DECL_SOLVERSOLVEHEUR(solverSolveHeurCliquer)
Definition: solver_cliquer.c:1161
Definition: struct_gcgcol.h:50
static int getLinkedNodeIndex(SCIP *scip, SCIP_VAR *var, SCIP_VAR **indsetvars, int indexcount, int **linkmatrix, SCIP_VAR **linkedvars, int nlinkedvars)
Definition: solver_cliquer.c:268
SCIP_EXPORT void GCGsolverSetData(GCG_SOLVER *solver, GCG_SOLVERDATA *solverdata)
Definition: solver.c:387
heuristic solver for pricing problems that solves independent set problems with cliquer
public methods for working with gcg columns
static SCIP_Bool areObjectivesIntegral(SCIP *scip)
Definition: solver_cliquer.c:377
GCG variable pricer.
static SCIP_Bool isVarLinked(SCIP_VAR **linkedvars, int nlinkedvars, SCIP_VAR *var)
Definition: solver_cliquer.c:71
Definition: solver_cliquer.c:59
static void setLinkedSolvals(SCIP *scip, SCIP_Real *solvals, int **linkmatrix, SCIP_VAR **linkedvars, int nlinkedvars, SCIP_VAR *var, SCIP_Real val)
Definition: solver_cliquer.c:349
SCIP_RETCODE GCGincludeSolverCliquer(SCIP *scip)
Definition: solver_cliquer.c:1175
SCIP_EXPORT GCG_SOLVERDATA * GCGsolverGetData(GCG_SOLVER *solver)
Definition: solver.c:377
static SCIP_Bool areVarsLinked(SCIP *scip, int **linkmatrix, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_VAR **linkedvars, int nlinkedvars)
Definition: solver_cliquer.c:143
SCIP_RETCODE GCGpricerIncludeSolver(SCIP *scip, const char *name, const char *desc, int priority, SCIP_Bool heurenabled, SCIP_Bool exactenabled, GCG_DECL_SOLVERUPDATE((*solverupdate)), GCG_DECL_SOLVERSOLVE((*solversolve)), GCG_DECL_SOLVERSOLVEHEUR((*solversolveheur)), GCG_DECL_SOLVERFREE((*solverfree)), GCG_DECL_SOLVERINIT((*solverinit)), GCG_DECL_SOLVEREXIT((*solverexit)), GCG_DECL_SOLVERINITSOL((*solverinitsol)), GCG_DECL_SOLVEREXITSOL((*solverexitsol)), GCG_SOLVERDATA *solverdata)
Definition: pricer_gcg.cpp:4370
GCG relaxator.
SCIP_RETCODE GCGpricerAddCol(SCIP *scip, GCG_COL *col)
Definition: pricer_gcg.cpp:4764
public methods for GCG variables
static SCIP_Bool areVarsLinkedRec(int **linkmatrix, int vindex1, int vindex2, int *vartrace, int traceindex, SCIP_VAR **linkedvars, int nlinkedvars)
Definition: solver_cliquer.c:95
static SCIP_RETCODE solveCliquer(SCIP_Bool exactly, SCIP *scip, SCIP *pricingprob, GCG_SOLVERDATA *solver, int probnr, SCIP_Real *lowerbound, GCG_PRICINGSTATUS *status)
Definition: solver_cliquer.c:462
static void updateVarLinks(SCIP *scip, int **linkmatrix, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_VAR **linkedvars, int *nlinkedvars)
Definition: solver_cliquer.c:184
static int getNodeIndex(SCIP_VAR *var, SCIP_VAR **indsetvars, int indexcount)
Definition: solver_cliquer.c:250