50#define COMPR_NAME "largestrepr"
51#define COMPR_DESC "heuristic searching for large common representatives"
52#define COMPR_PRIORITY 2000
53#define COMPR_MINNNODES 20
55#define DEFAUL_MEM_REPR 10
56#define DEFAULT_ITERS 5
57#define DEFAULT_MINCOMMONVARS 3
69 int representativessize;
70 SCIP_Bool initialized;
98 uint64_t varsignature;
104 for( v =
nvars - 1; v >= 0; --v )
108 (*signature0) |= varsignature;
110 (*signature1) |= varsignature;
140 SCIP_Real* lowerbounds;
142 const char** varnames;
145 uint64_t* signature0;
146 uint64_t* signature1;
148 unsigned int* leaveids;
182 assert(nids == nleaveids);
197 for( k = 0; k < nleaveids; k++ )
215 nvars[k] = nvars2 + nafterdualvars;
221 for( start_id = 0; start_id < nleaveids; start_id++ )
227 if(
nvars[start_id] <= comprdata->mincomvars + 1 )
233 current_id = start_id;
243 while( nreps-1 <= comprdata->niters && (nreps == -1 || (current_id % nleaveids) != start_id) )
245 int* idx_common_vars;
256 while( covered[current_id % nleaveids] && (nreps == -1 || (current_id % nleaveids) != start_id) )
259 current_id %= nleaveids;
261 if( nreps > 0 && current_id == start_id )
265 nreps =
MAX(0, nreps);
270 covered[current_id] =
TRUE;
273 next_id = (current_id + 1) % nleaveids ;
274 while( covered[next_id] && next_id != current_id )
275 next_id = (next_id + 1) % nleaveids;
277 if( next_id == current_id )
281 if(
nvars[next_id] <= comprdata->mincomvars + 1 )
298 for( v = 0; v <
nvars[current_id]; v++ )
314 SCIPdebugMsg(
scip,
"start with ID %u, %d fixed variables\n", leaveids[current_id], nnon_zero_vars);
316 covered_ids[ncovered] = current_id;
319 while( nnon_zero_vars >= comprdata->mincomvars )
322 while( covered[next_id % nleaveids] && (next_id % nleaveids) != current_id )
325 if( (signature0[current_id] & signature0[next_id % nleaveids]) == 0
326 && (signature1[current_id] & signature1[next_id % nleaveids]) == 0 )
332 if( (next_id % nleaveids) == current_id )
335 next_id %= nleaveids;
337 if( covered[next_id] )
343 for( v = 0; v <
nvars[next_id]; v++ )
353 if( ncommon_vars < comprdata->mincomvars )
357 for( v = 0; v < nnon_zero_vars; )
360 for( v2 = 0; v2 < ncommon_vars; v2++ )
362 if( idx_non_zero[v] == idx_common_vars[v2] )
367 if( v2 == ncommon_vars )
369 common_vars[idx_non_zero[v]] = 0;
372 idx_non_zero[v] = idx_non_zero[nnon_zero_vars-1];
380 if( nnon_zero_vars > 0 )
382 covered[next_id] =
TRUE;
385 SCIPdebugMessage(
"-> found intersection with ID %u, %d/%d common variables\n", leaveids[next_id],
388 covered_ids[ncovered] = next_id;
395 if( next_id % nleaveids == (current_id-1) % nleaveids )
399 if( nnemptyinters > 0 )
409 nrepvars[nreps-2] = nnon_zero_vars;
412 for( k = 0; k < nnon_zero_vars; k++ )
415 repvals[nreps-2][k] = common_vars[idx_non_zero[k]] - 1;
416 assert(repvals[nreps-2][k] == 0 || repvals[nreps-2][k] == 1);
421 SCIPdebugMsg(
scip,
"-> did not found a intersection larger than %d\n", comprdata->mincomvars);
422 covered[current_id] =
FALSE;
426 score += (
SCIP_Real) ncovered * nnon_zero_vars;
428 SCIPdebugMessage(
"-> current representation is of size %d with score = %.1f\n", nreps, score);
430 current_id = (current_id + 1) % nleaveids;
443 SCIPdebugMessage(
"-> final representation is of size %d with score = %.1f\n", nreps, score);
456 if( comprdata->representativessize < nreps )
463 comprdata->representativessize = nreps;
474 comprdata->score = score;
475 comprdata->nrepresentatives = nreps;
477 for( k = 0; k < nreps-1; k++ )
481 for( v = 0; v < nrepvars[k]; v++ )
492 for( k = 0; k <= nreps-2; k++ )
507 if( comprdata->nrepresentatives > 0 )
509 SCIPdebugMessage(
"best representation found has %d leaf nodes and score = %g\n", comprdata->nrepresentatives, comprdata->score);
512 for( k = 0; k < comprdata->nrepresentatives-1; k++ )
519 for(
r = k + 1;
r < comprdata->nrepresentatives;
r++ )
528 int npathafterdualvars;
540 &npathvars, &npathafterdualvars);
546 for(
i = 0;
i < npathvars;
i++ )
587 for( k = nleaveids-1; k >= 0; k-- )
627 if( comprdata->nrepresentatives == 0 )
631 for(
r = 0;
r < comprdata->nrepresentatives;
r++ )
693 if( comprdata->initialized )
695 if( comprdata->representativessize > 0 )
700 comprdata->representatives =
NULL;
701 comprdata->representativessize = 0;
702 comprdata->nrepresentatives = 0;
703 comprdata->initialized =
FALSE;
718 if( !comprdata->initialized )
723 comprdata->nrepresentatives = 0;
724 comprdata->rate = 0.0;
725 comprdata->score = 0.0;
726 comprdata->nnodes = 0;
732 comprdata->initialized =
TRUE;
773 comprdata->initialized =
FALSE;
777 comprExecLargestrepr, comprdata) );
static SCIP_RETCODE constructCompression(SCIP *scip, SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata, SCIP_RESULT *result)
static void calcSignature(SCIP_VAR **vars, SCIP_Real *vals, int nvars, uint64_t *signature0, uint64_t *signature1)
SCIP_RETCODE SCIPincludeComprLargestrepr(SCIP *scip)
static SCIP_RETCODE applyCompression(SCIP *scip, SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata, SCIP_RESULT *result)
#define DEFAULT_MINCOMMONVARS
largestrepr tree compression
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNOrigVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
#define SCIPhashSignature64(a)
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)
void SCIPcomprSetData(SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata)
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)
SCIP_COMPRDATA * SCIPcomprGetData(SCIP_COMPR *compr)
SCIP_RETCODE SCIPsetComprCopy(SCIP *scip, SCIP_COMPR *compr,)
SCIP_RETCODE SCIPsetComprFree(SCIP *scip, SCIP_COMPR *compr,)
SCIP_RETCODE SCIPsetComprExit(SCIP *scip, SCIP_COMPR *compr,)
const char * SCIPcomprGetName(SCIP_COMPR *compr)
int SCIPcomprGetMinNodes(SCIP_COMPR *compr)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPallocClearMemoryArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNReoptLeaves(SCIP *scip, SCIP_NODE *node)
SCIP_RETCODE SCIPaddReoptnodeBndchg(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR *var, SCIP_Real bound, SCIP_BOUNDTYPE boundtype)
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
SCIP_RETCODE SCIPinitRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
SCIP_RETCODE SCIPsetReoptCompression(SCIP *scip, SCIP_REOPTNODE **representation, int nrepresentatives, SCIP_Bool *success)
SCIP_RETCODE SCIPgetReoptLeaveIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int idssize, int *nids)
void SCIPgetReoptnodePath(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR **vars, SCIP_Real *vals, SCIP_BOUNDTYPE *boundtypes, int mem, int *nvars, int *nafterdualvars)
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 SCIPfreeRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
SCIP_RETCODE SCIPresetRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIPvarIsOriginal(SCIP_VAR *var)
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
public methods for tree compressions
public methods for message output
public data structures and miscellaneous methods
public methods for reoptimization
SCIP_Real SCIPreoptnodeGetLowerbound(SCIP_REOPTNODE *reoptnode)
void SCIPreoptnodeSetParentID(SCIP_REOPTNODE *reoptnode, unsigned int parentid)
int SCIPreoptnodeGetNVars(SCIP_REOPTNODE *reoptnode)
public methods for problem variables
public methods for compression plugins
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for reoptimization
struct SCIP_ComprData SCIP_COMPRDATA
#define SCIP_DECL_COMPRFREE(x)
#define SCIP_DECL_COMPREXEC(x)
#define SCIP_DECL_COMPREXIT(x)
#define SCIP_DECL_COMPRCOPY(x)
enum SCIP_BoundType SCIP_BOUNDTYPE
@ REOPT_CONSTYPE_DUALREDS
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE