RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://scip.zib.de/doc/html/heur__shifting_8c_source.php below:

SCIP Doxygen Documentation: heur_shifting.c Source File

52#define HEUR_NAME "shifting" 53#define HEUR_DESC "LP rounding heuristic with infeasibility recovering also using continuous variables" 54#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING 55#define HEUR_PRIORITY -5000 58#define HEUR_MAXDEPTH -1 59#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP 60#define HEUR_USESSUBSCIP FALSE 62#define MAXSHIFTINGS 50 63#define WEIGHTFACTOR 1.1 64#define DEFAULT_RANDSEED 31 99

assert(violrows !=

NULL

);

100

assert(violrowpos !=

NULL

);

101

assert(nviolrows !=

NULL

);

128 if

( oldviol != newviol )

139

violpos = violrowpos[rowpos];

140

assert(0 <= violpos && violpos < *nviolrows);

141

assert(violrows[violpos] == row);

142

violrowpos[rowpos] = -1;

145 if

( nfracsinrow[rowpos] > 0 )

147

assert(violpos < *nviolfracrows);

150 if

( violpos != *nviolfracrows - 1 )

152

violrows[violpos] = violrows[*nviolfracrows - 1];

154

violpos = *nviolfracrows - 1;

159

assert(violpos >= *nviolfracrows);

162 if

( violpos != *nviolrows - 1 )

164

violrows[violpos] = violrows[*nviolrows - 1];

172

assert(violrowpos[rowpos] == -1);

173

violrows[*nviolrows] = row;

174

violrowpos[rowpos] = *nviolrows;

180 if

( nfracsinrow[rowpos] > 0 )

182 if

( *nviolfracrows < *nviolrows - 1 )

186

violrows[*nviolrows - 1] = violrows[*nviolfracrows];

187

violrowpos[

SCIProwGetLPPos

(violrows[*nviolrows - 1])] = *nviolrows - 1;

189

violrows[*nviolfracrows] = row;

190

violrowpos[rowpos] = *nviolfracrows;

221

assert(activities !=

NULL

);

222

assert(nviolrows !=

NULL

);

223

assert(0 <= *nviolrows && *nviolrows <= nlprows);

225

delta = newsolval - oldsolval;

230

assert(ncolrows == 0 || (colrows !=

NULL

&& colvals !=

NULL

));

232 for

(

= 0;

< ncolrows; ++

)

239

assert(-1 <= rowpos && rowpos < nlprows);

249

oldactivity = activities[rowpos];

252

newactivity = oldactivity + delta * colvals[

];

257

activities[rowpos] = newactivity;

260 updateViolations

(

scip

, row, violrows, violrowpos, nviolrows, nviolfracrows, nfracsinrow, oldactivity, newactivity);

297

assert(direction == +1 || direction == -1);

298

assert(nincreases !=

NULL

);

299

assert(ndecreases !=

NULL

);

300

assert(shiftvar !=

NULL

);

301

assert(oldsolval !=

NULL

);

302

assert(newsolval !=

NULL

);

320 for

( c = 0; c < nrowcols; ++c )

340

increase = (direction * val > 0.0);

352

shiftscore = ndecreases[probindex]/increaseweight;

354

shiftscore = nincreases[probindex]/increaseweight;

359 if

( shiftscore <= bestshiftscore )

366

assert(direction * val < 0.0);

373

assert(activitydelta/val < 0.0);

374

shiftval = solval + activitydelta/val;

375

assert(shiftval <= solval);

379

shiftval =

MAX

(shiftval, lb);

385

assert(direction * val > 0.0);

392

assert(activitydelta/val > 0.0);

393

shiftval = solval + activitydelta/val;

394

assert(shiftval >= solval);

398

shiftval =

MIN

(shiftval, ub);

408 if

( shiftscore < bestshiftscore || deltaobj < bestdeltaobj )

410

bestshiftscore = shiftscore;

411

bestdeltaobj = deltaobj;

414

*newsolval = shiftval;

449

assert(shiftvar !=

NULL

);

450

assert(oldsolval !=

NULL

);

451

assert(newsolval !=

NULL

);

457 for

( v = 0; v < nlpcands; ++v )

469 if

( nlocks >= maxnlocks )

472

deltaobj = obj * (shiftval - solval);

476

bestdeltaobj = deltaobj;

479

*newsolval = shiftval;

485 if

( nlocks >= maxnlocks )

488

deltaobj = obj * (shiftval - solval);

492

bestdeltaobj = deltaobj;

495

*newsolval = shiftval;

523

assert(nviolrows >= *nviolfracrows);

527 for

(

= 0;

< nrows; ++

)

533

assert(0 <= rowlppos && rowlppos < nlprows);

540

nfracsinrow[rowlppos] += incval;

541

assert(nfracsinrow[rowlppos] >= 0);

542

theviolrowpos = violrowpos[rowlppos];

545 if

( theviolrowpos >= 0 )

550 if

( nfracsinrow[rowlppos] == 0 )

552

assert(theviolrowpos <= *nviolfracrows - 1);

556 if

( theviolrowpos < *nviolfracrows - 1 )

558

violrows[theviolrowpos] = violrows[*nviolfracrows - 1];

559

violrows[*nviolfracrows - 1] = rows[

];

561

violrowpos[

SCIProwGetLPPos

(violrows[theviolrowpos])] = theviolrowpos;

562

violrowpos[rowlppos] = *nviolfracrows - 1;

569 else if

( nfracsinrow[rowlppos] == incval )

571

assert(theviolrowpos >= *nviolfracrows);

574 if

( theviolrowpos > *nviolfracrows )

576

violrows[theviolrowpos] = violrows[*nviolfracrows];

577

violrows[*nviolfracrows] = rows[

];

579

violrowpos[

SCIProwGetLPPos

(violrows[theviolrowpos])] = theviolrowpos;

580

violrowpos[rowlppos] = *nviolfracrows;

598

assert(heur !=

NULL

);

620

heurdata->lastlp = -1;

641

assert(heurdata !=

NULL

);

662

assert(heurdata !=

NULL

);

663

heurdata->lastlp = -1;

696 int

nnonimprovingshifts;

706

assert(result !=

NULL

);

721

assert(heurdata !=

NULL

);

725 if

( nlps == heurdata->lastlp )

727

heurdata->lastlp = nlps;

733 if

(

nnodes

% ((ncalls/100)/(nsolsfound+1)+1) != 0 )

750 SCIPdebugMsg

(

scip

"executing shifting heuristic: %d LP rows, %d fractionals\n"

, nlprows, nfrac);

768 for

(

= 0;

< nlprows; ++

)

781

violrows[nviolrows] = row;

782

violrowpos[

] = nviolrows;

786

violrowpos[

] = -1;

789

violrowpos[

] = -1;

794 for

( c = 0; c < nlpcands; ++c )

795 addFracCounter

(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, lpcands[c], +1);

799

assert(sol !=

NULL

);

807 for

( c = 0; c < nlpcands; ++c )

811

minobj += obj * (bestshiftval - lpcandssol[c]);

815

nnonimprovingshifts = 0;

816

minnviolrows = INT_MAX;

817

increaseweight = 1.0;

818 while

( (nfrac > 0 || nviolrows > 0) && nnonimprovingshifts <

MAXSHIFTINGS

)

826 SCIPdebugMsg

(

scip

"shifting heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g), cutoff=%g\n"

830

nprevviolrows = nviolrows;

839 if

( nviolrows > 0 && (nfrac == 0 || nnonimprovingshifts <

MAXSHIFTINGS

-1) )

846

assert(nviolfracrows == 0 || nfrac > 0);

850 if

( nviolfracrows > 0 )

851

rowidx = nviolfracrows - 1;

856

assert(0 <= rowidx && rowidx < nviolrows);

857

row = violrows[rowidx];

859

assert(0 <= rowpos && rowpos < nlprows);

860

assert(violrowpos[rowpos] == rowidx);

861

assert(nfracsinrow[rowpos] == 0 || rowidx == nviolfracrows - 1);

863 SCIPdebugMsg

(

scip

"shifting heuristic: try to fix violated row <%s>: %g <= %g <= %g\n"

874

nincreases, ndecreases, increaseweight, &shiftvar, &oldsolval, &newsolval) );

877 if

( shiftvar ==

NULL

&& nfrac > 0 )

879 SCIPdebugMsg

(

scip

"shifting heuristic: search rounding variable and try to stay feasible\n"

);

886 SCIPdebugMsg

(

scip

"shifting heuristic: -> didn't find a shifting variable\n"

);

890 SCIPdebugMsg

(

scip

"shifting heuristic: -> shift var <%s>[%g,%g], type=%d, oldval=%g, newval=%g, obj=%g\n"

896

shiftvar, oldsolval, newsolval) );

897 if

( nviolrows >= nprevviolrows )

898

nnonimprovingshifts++;

899 else if

( nviolrows < minnviolrows )

901

minnviolrows = nviolrows;

902

nnonimprovingshifts = 0;

917

nnonimprovingshifts = 0;

918

minnviolrows = INT_MAX;

919 addFracCounter

(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, shiftvar, -1);

922 if

( obj > 0.0 && newsolval > oldsolval )

924 else if

( obj < 0.0 && newsolval < oldsolval )

930

minobj += obj * (newsolval - oldsolval);

934 if

( !oldsolvalisfrac )

937

assert(0 <= probindex && probindex < nvars);

939 if

( newsolval < oldsolval )

940

ndecreases[probindex] += increaseweight;

942

nincreases[probindex] += increaseweight;

943 if

( increaseweight >= 1e+09 )

947 for

( i = 0; i < nvars; ++i )

949

nincreases[i] /= increaseweight;

950

ndecreases[i] /= increaseweight;

952

increaseweight = 1.0;

956 SCIPdebugMsg

(

scip

"shifting heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n"

961 if

( nfrac == 0 && nviolrows == 0 )

1008

assert(heur !=

NULL

);

int SCIPgetNVars(SCIP *scip)

SCIP_RETCODE SCIPincludeHeurShifting(SCIP *scip)

SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)

SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)

SCIP_Real * SCIPcolGetVals(SCIP_COL *col)

SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)

int SCIPcolGetNLPNonz(SCIP_COL *col)

SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))

SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)

SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)

SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)

SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))

SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)

SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)

SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))

SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))

const char * SCIPheurGetName(SCIP_HEUR *heur)

void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)

SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)

SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)

SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)

SCIP_Real SCIPgetLPObjval(SCIP *scip)

#define SCIPallocBufferArray(scip, ptr, num)

#define SCIPfreeBufferArray(scip, ptr)

#define SCIPfreeBlockMemory(scip, ptr)

#define SCIPallocBlockMemory(scip, ptr)

SCIP_Real SCIProwGetLhs(SCIP_ROW *row)

SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)

SCIP_Real SCIProwGetRhs(SCIP_ROW *row)

int SCIProwGetNLPNonz(SCIP_ROW *row)

int SCIProwGetLPPos(SCIP_ROW *row)

SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)

SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)

const char * SCIProwGetName(SCIP_ROW *row)

SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)

SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)

SCIP_Real * SCIProwGetVals(SCIP_ROW *row)

SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)

SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)

SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)

SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)

SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)

SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)

SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)

SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)

SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)

SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)

SCIP_Longint SCIPgetNNodes(SCIP *scip)

SCIP_Longint SCIPgetNLPs(SCIP *scip)

SCIP_Real SCIPgetCutoffbound(SCIP *scip)

SCIP_Real SCIPinfinity(SCIP *scip)

SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)

SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)

SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)

SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)

SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)

SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)

SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)

SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)

SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)

SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)

SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)

SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)

int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)

SCIP_Real SCIPvarGetObj(SCIP_VAR *var)

SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)

SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)

int SCIPvarGetProbindex(SCIP_VAR *var)

const char * SCIPvarGetName(SCIP_VAR *var)

SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)

SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)

int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)

void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)

int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)

SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)

static SCIP_RETCODE selectEssentialRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_VAR **lpcands, int nlpcands, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)

static SCIP_DECL_HEURINITSOL(heurInitsolShifting)

static void addFracCounter(int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval)

static SCIP_DECL_HEUREXIT(heurExitShifting)

static SCIP_DECL_HEUREXEC(heurExecShifting)

static SCIP_DECL_HEURCOPY(heurCopyShifting)

static SCIP_RETCODE updateActivities(SCIP *scip, SCIP_Real *activities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)

static void updateViolations(SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, SCIP_Real oldactivity, SCIP_Real newactivity)

static SCIP_DECL_HEURINIT(heurInitShifting)

static SCIP_RETCODE selectShifting(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *row, SCIP_Real rowactivity, int direction, SCIP_Real *nincreases, SCIP_Real *ndecreases, SCIP_Real increaseweight, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)

LP rounding heuristic that tries to recover from intermediate infeasibilities and shifts continuous v...

memory allocation routines

#define BMSclearMemoryArray(ptr, num)

public methods for primal heuristics

public methods for LP management

public methods for message output

public data structures and miscellaneous methods

public methods for problem variables

public methods for branching rule plugins and branching

public methods for primal heuristic plugins and divesets

public methods for the LP relaxation, rows and columns

public methods for memory management

public methods for message handling

public methods for numerical tolerances

public methods for global and local (sub)problems

public methods for random numbers

public methods for solutions

public methods for querying solving statistics

struct SCIP_HeurData SCIP_HEURDATA

enum SCIP_Retcode SCIP_RETCODE

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4