31 #define COMPR_NAME "largestrepr" 32 #define COMPR_DESC "heuristic searching for large common representatives" 33 #define COMPR_PRIORITY 2000 34 #define COMPR_MINNNODES 20 36 #define DEFAUL_MEM_REPR 10 37 #define DEFAULT_ITERS 5 38 #define DEFAULT_MINCOMMONVARS 3 50 int representativessize;
85 for( v = nvars - 1; v >= 0; --v )
122 const char** varnames;
128 unsigned int* leaveids;
136 assert(scip !=
NULL);
137 assert(comprdata !=
NULL);
156 SCIPdebugMsg(scip,
"-> try compression with %d node(s)\n", nleaveids);
162 assert(nids == nleaveids);
177 for( k = 0; k < nleaveids; k++ )
193 SCIPgetReoptnodePath(scip, reoptnode, vars[k], vals[k], bounds[k], mem_vars, &nvars2, &nafterdualvars);
195 nvars[k] = nvars2 + nafterdualvars;
198 calcSignature(vars[k], vals[k], nvars[k], &signature0[k], &signature1[k]);
201 for( start_id = 0; start_id < nleaveids; start_id++ )
207 if( nvars[start_id] <= comprdata->mincomvars + 1 )
213 current_id = start_id;
220 SCIPdebugMsg(scip,
"+---+ start round %d +---+\n", start_id + 1);
223 while( nreps-1 <= comprdata->niters && (nreps == -1 || (current_id % nleaveids) != start_id) )
225 int* idx_common_vars;
236 while( covered[current_id % nleaveids] && (nreps == -1 || (current_id % nleaveids) != start_id) )
239 current_id %= nleaveids;
241 if( nreps > 0 && current_id == start_id )
245 nreps =
MAX(0, nreps);
250 covered[current_id] =
TRUE;
253 next_id = (current_id + 1) % nleaveids ;
254 while( covered[next_id] && next_id != current_id )
255 next_id = (next_id + 1) % nleaveids;
257 if( next_id == current_id )
261 if( nvars[next_id] <= comprdata->mincomvars + 1 )
278 for( v = 0; v < nvars[current_id]; v++ )
294 SCIPdebugMsg(scip,
"start with ID %u, %d fixed variables\n", leaveids[current_id], nnon_zero_vars);
296 covered_ids[ncovered] = current_id;
299 while( nnon_zero_vars >= comprdata->mincomvars )
302 while( covered[next_id % nleaveids] && (next_id % nleaveids) != current_id )
305 if( (signature0[current_id] & signature0[next_id % nleaveids]) == 0
306 && (signature1[current_id] & signature1[next_id % nleaveids]) == 0 )
312 if( (next_id % nleaveids) == current_id )
315 next_id %= nleaveids;
317 if( covered[next_id] )
323 for( v = 0; v < nvars[next_id]; v++ )
325 if( common_vars[
SCIPvarGetProbindex(vars[next_id][v])] == (vals[next_id][v] == 0 ? 1 : 2) )
333 if( ncommon_vars < comprdata->mincomvars )
337 for( v = 0; v < nnon_zero_vars; )
340 for( v2 = 0; v2 < ncommon_vars; v2++ )
342 if( idx_non_zero[v] == idx_common_vars[v2] )
347 if( v2 == ncommon_vars )
349 common_vars[idx_non_zero[v]] = 0;
352 idx_non_zero[v] = idx_non_zero[nnon_zero_vars-1];
360 if( nnon_zero_vars > 0 )
362 covered[next_id] =
TRUE;
365 SCIPdebugMessage(
"-> found intersection with ID %u, %d/%d common variables\n", leaveids[next_id],
366 nnon_zero_vars,
MAX(nvars[current_id], nvars[next_id]));
368 covered_ids[ncovered] = next_id;
375 if( next_id % nleaveids == (current_id-1) % nleaveids )
379 if( nnemptyinters > 0 )
389 nrepvars[nreps-2] = nnon_zero_vars;
392 for( k = 0; k < nnon_zero_vars; k++ )
394 repvars[nreps-2][k] =
SCIPfindVar(scip, varnames[idx_non_zero[k]]);
395 repvals[nreps-2][k] = common_vars[idx_non_zero[k]] - 1;
396 assert(repvals[nreps-2][k] == 0 || repvals[nreps-2][k] == 1);
401 SCIPdebugMsg(scip,
"-> did not found a intersection larger than %d\n", comprdata->mincomvars);
402 covered[current_id] =
FALSE;
406 score += (
SCIP_Real) ncovered * nnon_zero_vars;
408 SCIPdebugMessage(
"-> current representation is of size %d with score = %.1f\n", nreps, score);
410 current_id = (current_id + 1) % nleaveids;
423 SCIPdebugMessage(
"-> final representation is of size %d with score = %.1f\n", nreps, score);
436 if( comprdata->representativessize < nreps )
443 comprdata->representativessize = nreps;
454 comprdata->score = score;
455 comprdata->nrepresentatives = nreps;
457 for( k = 0; k < nreps-1; k++ )
461 for( v = 0; v < nrepvars[k]; v++ )
472 for( k = 0; k <= nreps-2; k++ )
487 if( comprdata->nrepresentatives > 0 )
489 SCIPdebugMessage(
"best representation found has %d leaf nodes and score = %g\n", comprdata->nrepresentatives, comprdata->score);
492 for( k = 0; k < comprdata->nrepresentatives-1; k++ )
499 for( r = k + 1; r < comprdata->nrepresentatives; r++ )
508 int npathafterdualvars;
519 SCIPgetReoptnodePath(scip, comprdata->representatives[k], pathvars, pathvals, pathboundtypes, pathvarssize,
520 &npathvars, &npathafterdualvars);
526 for( i = 0; i < npathvars; i++ )
539 if(
SCIPisEQ(scip, pathvals[i], 0.0) )
547 assert(
SCIPisEQ(scip, pathvals[i], 1.0));
567 for( k = nleaveids-1; k >= 0; k-- )
601 assert(scip !=
NULL);
602 assert(compr !=
NULL);
603 assert(comprdata !=
NULL);
607 if( comprdata->nrepresentatives == 0 )
611 for( r = 0; r < comprdata->nrepresentatives; r++ )
634 assert(compr !=
NULL);
650 assert(compr !=
NULL);
653 assert(comprdata !=
NULL);
668 assert(compr !=
NULL);
671 assert(comprdata !=
NULL);
673 if( comprdata->initialized )
675 if( comprdata->representativessize > 0 )
680 comprdata->representatives =
NULL;
681 comprdata->representativessize = 0;
682 comprdata->nrepresentatives = 0;
683 comprdata->initialized =
FALSE;
696 assert(comprdata !=
NULL);
698 if( !comprdata->initialized )
703 comprdata->nrepresentatives = 0;
704 comprdata->rate = 0.0;
705 comprdata->score = 0.0;
706 comprdata->nnodes = 0;
712 comprdata->initialized =
TRUE;
752 assert(comprdata !=
NULL);
753 comprdata->initialized =
FALSE;
757 comprExecLargestrepr, comprdata) );
759 assert(compr !=
NULL);
enum SCIP_Result SCIP_RESULT
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
enum SCIP_BoundType SCIP_BOUNDTYPE
SCIP_RETCODE SCIPsetComprFree(SCIP *scip, SCIP_COMPR *compr, SCIP_DECL_COMPRFREE((*comprfree)))
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPcomprGetMinNodes(SCIP_COMPR *compr)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPgetNOrigVars(SCIP *scip)
static void calcSignature(SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Longint *signature0, SCIP_Longint *signature1)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPincludeComprBasic(SCIP *scip, SCIP_COMPR **compr, const char *name, const char *desc, int priority, int minnnodes, SCIP_DECL_COMPREXEC((*comprexec)), SCIP_COMPRDATA *comprdata)
enum SCIP_Retcode SCIP_RETCODE
int SCIPvarGetProbindex(SCIP_VAR *var)
#define SCIPfreeBlockMemory(scip, ptr)
public methods for reoptimization
SCIP_RETCODE SCIPinitRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_COMPRDATA * SCIPcomprGetData(SCIP_COMPR *compr)
#define SCIPallocBlockMemory(scip, ptr)
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)
SCIP_RETCODE SCIPfreeRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetReoptCompression(SCIP *scip, SCIP_REOPTNODE **representation, int nrepresentatives, SCIP_Bool *success)
SCIP_RETCODE SCIPsetComprCopy(SCIP *scip, SCIP_COMPR *compr, SCIP_DECL_COMPRCOPY((*comprcopy)))
static SCIP_RETCODE applyCompression(SCIP *scip, SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata, SCIP_RESULT *result)
#define DEFAULT_MINCOMMONVARS
void SCIPreoptnodeSetParentID(SCIP_REOPTNODE *reoptnode, unsigned int parentid)
const char * SCIPvarGetName(SCIP_VAR *var)
static SCIP_DECL_COMPRCOPY(comprCopyLargestrepr)
struct SCIP_ComprData SCIP_COMPRDATA
SCIP_Bool SCIPvarIsOriginal(SCIP_VAR *var)
#define SCIPallocBufferArray(scip, ptr, num)
int SCIPreoptnodeGetNVars(SCIP_REOPTNODE *reoptnode)
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPreoptnodeGetLowerbound(SCIP_REOPTNODE *reoptnode)
SCIP_RETCODE SCIPincludeComprLargestrepr(SCIP *scip)
SCIP_RETCODE SCIPaddReoptnodeCons(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR **vars, SCIP_Real *vals, SCIP_BOUNDTYPE *boundtypes, SCIP_Real lhs, SCIP_Real rhs, int nvars, REOPT_CONSTYPE constype, SCIP_Bool linear)
SCIP_RETCODE SCIPaddReoptnodeBndchg(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR *var, SCIP_Real bound, SCIP_BOUNDTYPE boundtype)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
void SCIPgetReoptnodePath(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR **vars, SCIP_Real *vals, SCIP_BOUNDTYPE *boundtypes, int mem, int *nvars, int *nafterdualvars)
static SCIP_DECL_COMPRFREE(comprFreeLargestrepr)
int SCIPgetNBinVars(SCIP *scip)
#define SCIPallocClearMemoryArray(scip, ptr, num)
const char * SCIPcomprGetName(SCIP_COMPR *compr)
internal methods for tree compressions
static SCIP_DECL_COMPREXEC(comprExecLargestrepr)
SCIP_RETCODE SCIPsetComprExit(SCIP *scip, SCIP_COMPR *compr, SCIP_DECL_COMPREXIT((*comprexit)))
SCIP_RETCODE SCIPgetReoptLeaveIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int idssize, int *nids)
largestrepr tree compression
void SCIPcomprSetData(SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata)
static SCIP_DECL_COMPREXIT(comprExitLargestrepr)
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
int SCIPgetNReoptLeaves(SCIP *scip, SCIP_NODE *node)
SCIP_RETCODE SCIPresetRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
static SCIP_RETCODE constructCompression(SCIP *scip, SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata, SCIP_RESULT *result)