42 #define HEUR_NAME "greedycolsel"
43 #define HEUR_DESC "greedy column selection heuristic"
44 #define HEUR_DISPCHAR 'e'
45 #define HEUR_PRIORITY 0
47 #define HEUR_FREQOFS 0
48 #define HEUR_MAXDEPTH -1
50 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP
51 #define HEUR_USESSUBSCIP FALSE
53 #define DEFAULT_MINCOLUMNS 200
54 #define DEFAULT_USEOBJ FALSE
88 SCIP_Real* activities,
101 col = SCIPvarGetCol(mastervar);
102 colrows = SCIPcolGetRows(col);
103 colvals = SCIPcolGetVals(col);
104 ncolrows = SCIPcolGetNLPNonz(col);
105 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
108 for( r = 0; r < ncolrows; r++ )
114 rowpos = SCIProwGetLPPos(row);
115 assert(-1 <= rowpos);
117 if( rowpos >= 0 && !SCIProwIsLocal(row) )
119 SCIP_Real oldactivity;
120 SCIP_Real newactivity;
122 oldactivity = activities[rowpos];
123 newactivity = oldactivity + colvals[r];
125 if( SCIPisFeasLT(scip, oldactivity, SCIProwGetLhs(row)) || SCIPisFeasGT(scip, oldactivity, SCIProwGetRhs(row)) )
127 if( SCIPisFeasGE(scip, newactivity, SCIProwGetLhs(row)) && SCIPisFeasLE(scip, oldactivity, SCIProwGetRhs(row)) )
132 if( SCIPisFeasLT(scip, newactivity, SCIProwGetLhs(row)) || SCIPisFeasGT(scip, newactivity, SCIProwGetRhs(row)) )
146 SCIP_Real* activities,
155 SCIP_VAR** mastervars;
165 assert(origprob != NULL);
168 SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
169 assert(nmastervars >= 0);
172 *violchange = INT_MAX;
173 curobj = SCIPinfinity(scip);
175 for( i = nmastervars - 1; i >= 0; i-- )
180 mastervar = mastervars[i];
197 && !SCIPisEQ(scip, SCIPvarGetLbLocal(mastervar), SCIPvarGetUbLocal(mastervar))
198 && SCIPisFeasGE(scip, SCIPgetSolVal(scip, mastersol, mastervar), SCIPvarGetUbLocal(mastervar)) )
201 tmpobj = SCIPvarGetObj(mastervar);
202 if( tmpviolchange < *violchange ||
203 (tmpviolchange == *violchange && SCIPisLE(scip, tmpobj, curobj) && useobj) )
206 *violchange = tmpviolchange;
219 SCIP_Real* activities,
230 assert(activities != NULL);
232 col = SCIPvarGetCol(mastervar);
233 colrows = SCIPcolGetRows(col);
234 colvals = SCIPcolGetVals(col);
235 ncolrows = SCIPcolGetNLPNonz(col);
236 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
238 for( r = 0; r < ncolrows; ++r )
240 SCIP_ROW* row = colrows[r];
241 int rowpos = SCIProwGetLPPos(row);
243 assert(-1 <= rowpos);
245 if( rowpos >= 0 && !SCIProwIsLocal(row) )
247 SCIP_Real oldactivity;
248 SCIP_Real newactivity;
250 assert(SCIProwIsInLP(row));
253 oldactivity = activities[rowpos];
254 newactivity = oldactivity + colvals[r];
255 if( SCIPisInfinity(scip, newactivity) )
256 newactivity = SCIPinfinity(scip);
257 else if( SCIPisInfinity(scip, -newactivity) )
258 newactivity = -SCIPinfinity(scip);
259 activities[rowpos] = newactivity;
272 SCIP_VAR** zeromastervar
275 SCIP_VAR** mastervars;
282 SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
284 *zeromastervar = NULL;
287 for( i = 0; i < nmastervars && *zeromastervar == NULL; ++i )
289 SCIP_VAR* mastervar = mastervars[i];
299 for( j = 0; j < norigvars; ++j )
300 if( !SCIPisZero(scip, origvals[j]) )
305 *zeromastervar = mastervar;
317 SCIP_HEURDATA* heurdata,
319 SCIP_VAR** zeromastervar
324 if( heurdata->zerovars[block] == NULL )
327 *zeromastervar = heurdata->zerovars[block];
341 #define heurCopyGreedycolsel NULL
347 SCIP_HEURDATA* heurdata;
349 assert(heur != NULL);
350 assert(scip != NULL);
353 heurdata = SCIPheurGetData(heur);
354 assert(heurdata != NULL);
357 SCIPfreeBlockMemory(scip, &heurdata);
358 SCIPheurSetData(heur, NULL);
369 SCIP_HEURDATA* heurdata;
374 assert(heur != NULL);
375 assert(scip != NULL);
379 assert(origprob != NULL);
382 heurdata = SCIPheurGetData(heur);
383 assert(heurdata != NULL);
388 heurdata->lastncols = 0;
393 heurdata->maxzerovars = SCIPcalcMemGrowSize(scip, nblocks);
394 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->zerovars, heurdata->maxzerovars) );
397 for( i = 0; i < nblocks; ++i )
398 heurdata->zerovars[i] = NULL;
408 SCIP_HEURDATA* heurdata;
410 assert(heur != NULL);
411 assert(scip != NULL);
414 heurdata = SCIPheurGetData(heur);
415 assert(heurdata != NULL);
418 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->zerovars, heurdata->maxzerovars);
425 #define heurInitsolGreedycolsel NULL
429 #define heurExitsolGreedycolsel NULL
437 SCIP_HEURDATA* heurdata;
441 SCIP_VAR** mastervars;
442 SCIP_Real* activities;
445 SCIP_Bool allblocksfull;
446 SCIP_Bool masterfeas;
460 assert(heur != NULL);
461 assert(scip != NULL);
462 assert(result != NULL);
466 assert(origprob != NULL);
469 heurdata = SCIPheurGetData(heur);
470 assert(heurdata != NULL);
472 *result = SCIP_DELAYED;
475 SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
476 assert(nmastervars >= 0);
480 minnewcols = heurdata->mincolumns * (int) (1.0 * ((1.0 + SCIPheurGetNCalls(heur)) / (1.0 + SCIPheurGetNBestSolsFound(heur))));
483 if( nmastervars - heurdata->lastncols < minnewcols )
486 *result = SCIP_DIDNOTFIND;
488 SCIPdebugMessage(
"Executing Greedy Column Selection heuristic (nmastervars = %d) ...\n", nmastervars);
492 assert(nblocks >= 0);
495 SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
496 assert(lprows != NULL);
497 assert(nlprows >= 0);
500 SCIP_CALL( SCIPallocBufferArray(scip, &blocknr, nblocks) );
501 SCIP_CALL( SCIPallocBufferArray(scip, &ignored, nmastervars) );
502 SCIP_CALL( SCIPallocBufferArray(scip, &activities, nlprows) );
505 SCIP_CALL( SCIPcreateSol(scip, &mastersol, heur) );
506 SCIP_CALL( SCIPcreateSol(origprob, &origsol, heur) );
509 BMSclearMemoryArray(blocknr, nblocks);
510 BMSclearMemoryArray(ignored, nmastervars);
511 allblocksfull = FALSE;
515 for( i = 0; i < nlprows; i++ )
520 assert(SCIProwGetLPPos(row) == i);
522 if( !SCIProwIsLocal(row) )
525 if( SCIPisFeasLT(scip, 0.0, SCIProwGetLhs(row)) || SCIPisFeasGT(scip, 0.0, SCIProwGetRhs(row)) )
530 SCIPdebugMessage(
" -> %d master LP rows violated\n", nviolrows);
536 while( !allblocksfull && !success )
544 SCIP_CALL(
getBestMastervar(scip, mastersol, activities, blocknr, ignored, heurdata->useobj, &index, &violchange) );
545 assert(index >= -1 && index < nmastervars);
550 assert(violchange == INT_MAX);
551 SCIPdebugMessage(
" -> no master variable could be selected\n");
556 mastervar = mastervars[index];
567 SCIPdebugMessage(
" -> (block %d) selected master variable %s; violchange=%d\n",
568 block, SCIPvarGetName(mastervar), violchange);
571 SCIP_CALL( SCIPincSolVal(scip, mastersol, mastervar, 1.0) );
574 for( i = 0; i < norigvars; i++ )
583 SCIP_VAR** linkingpricingvars;
589 for( j = 0; j < nblocks; j++ )
590 if( linkingpricingvars[j] != NULL )
601 SCIP_VAR* linkingmastervar;
604 assert(linkingmastervar != NULL);
605 SCIP_CALL( SCIPincSolVal(origprob, origsol, origvars[i], origvals[i]) );
606 SCIP_CALL( SCIPincSolVal(scip, mastersol, linkingmastervar, origvals[i]) );
612 value = SCIPgetSolVal(origprob, origsol, origvars[i]);
613 if( !SCIPisEQ(origprob, value, origvals[i]) )
615 SCIPdebugMessage(
" -> cannot use mastervar: origvar %s already has value %g in block %d, different to %g\n",
616 SCIPvarGetName(origvars[i]), value, j, origvals[i]);
617 ignored[index] = TRUE;
624 SCIP_VAR* pricingvar;
625 SCIP_VAR** origpricingvars;
627 int norigpricingvars;
631 if( SCIPisZero(scip, origvals[i]) )
635 assert(pricingvar != NULL);
642 assert(blocknr[block] < norigpricingvars);
646 SCIP_CALL( SCIPincSolVal(origprob, origsol, origpricingvars[blocknr[block]], origvals[i]) );
653 SCIP_CALL( SCIPincSolVal(scip, mastersol, mastervar, -1.0) );
654 for( k = 0; k < i; k++ )
658 SCIP_VAR** linkingpricingvars;
664 for( j = 0; j < nblocks; j++ )
666 if( linkingpricingvars[j] != NULL )
668 if( blocknr[j] > 0 && j != block )
679 SCIP_VAR* linkingmastervar;
682 SCIP_CALL( SCIPincSolVal(origprob, origsol, origvars[k], -origvals[k]) );
683 SCIP_CALL( SCIPincSolVal(scip, mastersol, linkingmastervar, -origvals[k]) );
688 SCIP_VAR* pricingvar;
689 SCIP_VAR** origpricingvars;
691 int norigpricingvars;
695 assert(pricingvar != NULL);
702 assert(blocknr[block] < norigpricingvars);
706 SCIP_CALL( SCIPincSolVal(origprob, origsol, origpricingvars[blocknr[block]], -origvals[k]) );
715 SCIP_CALL( SCIPtrySol(origprob, origsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
718 allblocksfull = TRUE;
719 for( i = 0; i < nblocks && allblocksfull; i++ )
728 if( success && blocknr[i] < nidentblocks )
730 SCIP_VAR* zeromastervar;
733 zeromastervar = NULL;
735 if( zeromastervar != NULL )
737 SCIPdebugMessage(
" -> (block %d) selected zero master variable %s (%d times)\n",
738 i, SCIPvarGetName(zeromastervar), nidentblocks - blocknr[i]);
740 SCIP_CALL( SCIPincSolVal(scip, mastersol, zeromastervar,
741 (SCIP_Real) nidentblocks - blocknr[i]) );
742 blocknr[i] = nidentblocks;
747 if( !(blocknr[i] >= nidentblocks) )
748 allblocksfull = FALSE;
753 if( success && allblocksfull )
756 SCIP_CALL( SCIPtrySol(scip, mastersol, TRUE, TRUE, TRUE, TRUE, TRUE, &masterfeas) );
758 SCIP_CALL( SCIPtrySol(scip, mastersol, FALSE, FALSE, TRUE, TRUE, TRUE, &masterfeas) );
762 SCIPdebugMessage(
"WARNING: original solution feasible, but no solution has been added to master problem.\n");
767 nviolrows += violchange;
773 *result = SCIP_FOUNDSOL;
774 SCIPdebugMessage(
"heuristic successful - feasible solution found, obj=%g\n",
775 SCIPgetSolOrigObj(origprob, origsol));
779 SCIPdebugMessage(
"no feasible solution found or solution already known; %d constraints violated.\n", nviolrows);
782 SCIP_CALL( SCIPfreeSol(origprob, &origsol) );
783 SCIP_CALL( SCIPfreeSol(scip, &mastersol) );
784 SCIPfreeBufferArray(scip, &activities);
785 SCIPfreeBufferArray(scip, &ignored);
786 SCIPfreeBufferArray(scip, &blocknr);
788 heurdata->lastncols = nmastervars;
805 SCIP_HEURDATA* heurdata;
808 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
810 heurdata->zerovars = NULL;
811 heurdata->maxzerovars = 0;
821 SCIP_CALL( SCIPaddIntParam(scip,
"heuristics/"HEUR_NAME"/mincolumns",
822 "minimum number of columns to regard in the master problem",
824 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/useobj",
825 "use objective coefficients as tie breakers",