A RetroSearch Logo

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

Search Query:

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

SCIP Doxygen Documentation: heur_shiftandpropagate.c Source File

61#define HEUR_NAME "shiftandpropagate" 62#define HEUR_DESC "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques" 63#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP 64#define HEUR_PRIORITY 1000 67#define HEUR_MAXDEPTH -1 68#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 69#define HEUR_USESSUBSCIP FALSE 71#define DEFAULT_WEIGHT_INEQUALITY 1 72#define DEFAULT_WEIGHT_EQUALITY 3 73#define DEFAULT_RELAX TRUE 74#define DEFAULT_PROBING TRUE 75#define DEFAULT_ONLYWITHOUTSOL TRUE 76#define DEFAULT_NPROPROUNDS 10 77#define DEFAULT_PROPBREAKER 65000 78#define DEFAULT_CUTOFFBREAKER 15 79#define DEFAULT_RANDSEED 29 80#define DEFAULT_SORTKEY 'v' 81#define DEFAULT_SORTVARS TRUE 82#define DEFAULT_COLLECTSTATS TRUE 83#define DEFAULT_STOPAFTERFEASIBLE TRUE 84#define DEFAULT_PREFERBINARIES TRUE 85#define DEFAULT_SELECTBEST FALSE 86#define DEFAULT_MAXCUTOFFQUOT 0.0 87#define SORTKEYS "nrtuv" 89#define DEFAULT_NOZEROFIXING FALSE 90#define DEFAULT_FIXBINLOCKS TRUE 91#define DEFAULT_BINLOCKSFIRST FALSE 92#define DEFAULT_NORMALIZE TRUE 93#define DEFAULT_UPDATEWEIGHTS FALSE 94#define DEFAULT_IMPLISCONTINUOUS TRUE 95#define DEFAULT_MINFIXINGRATELP 0.0 97#define EVENTHDLR_NAME "eventhdlrshiftandpropagate" 98#define EVENTHDLR_DESC "event handler to catch bound changes" 99#define EVENTTYPE_SHIFTANDPROPAGATE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED) 157struct

ConstraintMatrix

180struct

SCIP_EventhdlrData

185 int

* violatedrowpos;

231

assert(matrix !=

NULL

);

232

assert(0 <= rowindex && rowindex < matrix->nrows);

234

arrayposition = matrix->rowmatbegin[rowindex];

236 if

( nrowvals !=

NULL

)

238 if

( rowindex == matrix->nrows - 1 )

239

*nrowvals = matrix->nnonzs - arrayposition;

241

*nrowvals = matrix->rowmatbegin[rowindex + 1] - arrayposition;

244 if

( valpointer !=

NULL

)

245

*valpointer = &(matrix->rowmatvals[arrayposition]);

246 if

( indexpointer !=

NULL

)

247

*indexpointer = &(matrix->rowmatind[arrayposition]);

250

*lhs = matrix->lhs[rowindex];

253

*rhs = matrix->rhs[rowindex];

268

assert(matrix !=

NULL

);

269

assert(0 <= colindex && colindex < matrix->ncols);

271

arrayposition = matrix->colmatbegin[colindex];

273 if

( ncolvals !=

NULL

)

275 if

( colindex == matrix->ncols - 1 )

276

*ncolvals = matrix->nnonzs - arrayposition;

278

*ncolvals = matrix->colmatbegin[colindex + 1] - arrayposition;

280 if

( valpointer !=

NULL

)

281

*valpointer = &(matrix->colmatvals[arrayposition]);

283 if

( indexpointer !=

NULL

)

284

*indexpointer = &(matrix->colmatind[arrayposition]);

305

assert(var !=

NULL

);

309

assert(varcol !=

NULL

);

319

assert(colvals !=

NULL

|| ncolvals == 0);

324

assert(matrix->normalized);

326 for

(

r

= 0;

r

< ncolvals; ++

r

)

336

colrow = colrows[

r

];

339 if

( rowindex == -1 )

342

assert(colvals !=

NULL

);

343

colval = colvals[

r

];

345

assert(0 <= rowindex && rowindex < matrix->nrows);

365

matrix->lhs[rowindex] -= colval * lhsvarbound;

370

matrix->rhs[rowindex] -= colval * rhsvarbound;

374 SCIPdebugMsg

(

scip

,

"Row <%s> changed:Coefficient <%g>, LHS <%g> --> <%g>, RHS <%g> --> <%g>\n"

,

375 SCIProwGetName

(colrow), colval, lhs, matrix->lhs[rowindex], rhs, matrix->rhs[rowindex]);

404

assert(matrix !=

NULL

);

405

assert(0 <= colpos && colpos < heurdata->nlpcols);

406

col = heurdata->lpcols[colpos];

407

assert(col !=

NULL

);

411

assert(var !=

NULL

);

416

negatecoeffs =

FALSE

;

424

negatecoeffs =

TRUE

;

426

deltashift = matrix->transformshiftvals[colpos];

427

matrix->transformshiftvals[colpos] = 0.0;

436

matrix->transformshiftvals[colpos] = lb;

442

negatecoeffs =

TRUE

;

445

matrix->transformshiftvals[colpos] = ub;

468

assert(nrows == 0 ||(vals !=

NULL

&& rows !=

NULL

));

471 for

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

473 int

rowpos = rows[i];

475

assert(rowpos < matrix->nrows);

478

matrix->lhs[rowpos] -= (vals[i]) * deltashift;

481

matrix->rhs[rowpos] -= (vals[i]) * deltashift;

484

(vals[i]) = -(vals[i]);

489 SCIPdebugMsg

(

scip

,

"Variable <%s> at colpos %d transformed. Status %d LB <%g> --> <%g>, UB <%g> --> <%g>\n"

,

490 SCIPvarGetName

(var), colpos, matrix->transformstatus[colpos], lb, 0.0, ub, matrix->upperbounds[colpos]);

519

assert(matrix !=

NULL

);

520

assert(initialized!=

NULL

);

521

assert(infeasible !=

NULL

);

522

assert(nmaxrows !=

NULL

);

524 SCIPdebugMsg

(

scip

,

"entering Matrix Initialization method of SHIFTANDPROPAGATE heuristic!\n"

);

528

lpcols = heurdata->lpcols;

529

ncols = heurdata->nlpcols;

531

matrix->nrows = nrows;

533

matrix->normalized =

FALSE

;

534

matrix->ndiscvars = 0;

536

impliscontinuous = heurdata->impliscontinuous;

539 for

( j = 0; j < ncols; ++j )

541

assert(lpcols[j] !=

NULL

);

551

matrix->ncols = matrix->ndiscvars;

553 if

( matrix->nnonzs == 0 )

555 SCIPdebugMsg

(

scip

,

"No matrix entries - Terminating initialization of matrix.\n"

);

557

*initialized =

FALSE

;

578 for

( j = 0; j < matrix->ndiscvars; ++j )

582

*infeasible =

FALSE

;

587 for

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

605

matrix->rowmatbegin[i] = currentpointer;

622 SCIPdebugMsg

(

scip

,

" Matrix initialization stopped because of row infeasibility! \n"

);

627 for

( j = 0; j < nrowlpnonz; ++j )

632

assert(currentpointer < matrix->nnonzs);

634

matrix->rowmatvals[currentpointer] = rowvals[j];

635

matrix->rowmatind[currentpointer] = colposs[

SCIPcolGetLPPos

(cols[j])];

641

matrix->normalized =

TRUE

;

646

assert(currentpointer == matrix->nnonzs);

651 for

( j = 0; j < matrix->ncols; ++j )

660

currentcol = lpcols[j];

666

matrix->colnorms[j] = ncolnonz;

668

*nmaxrows =

MAX

(*nmaxrows, ncolnonz);

671

matrix->colmatbegin[j] = currentpointer;

673 for

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

677

assert(rows[i] !=

NULL

);

680

assert(currentpointer < matrix->nnonzs);

681

matrix->colmatvals[currentpointer] = colvals[i];

684 if

( heurdata->normalize )

688

matrix->colnorms[j] +=

ABS

(normval);

692

assert(currentpointer == matrix->nnonzs);

695 for

( j = 0; j < (relax ? ncols : matrix->ndiscvars); ++j )

702

matrix->transformshiftvals[j] = 0.0;

713

*initialized =

TRUE

;

715 SCIPdebugMsg

(

scip

,

"Matrix initialized for %d discrete variables with %d cols, %d rows and %d nonzero entries\n"

,

716

matrix->ndiscvars, matrix->ncols, matrix->nrows, matrix->nnonzs);

728

assert(matrix !=

NULL

);

731 if

( (*matrix)->nnonzs > 0 )

733

assert((*matrix) !=

NULL

);

734

assert((*matrix)->rowmatbegin !=

NULL

);

735

assert((*matrix)->rowmatvals !=

NULL

);

736

assert((*matrix)->rowmatind !=

NULL

);

737

assert((*matrix)->colmatbegin !=

NULL

);

738

assert((*matrix)->colmatvals!=

NULL

);

739

assert((*matrix)->colmatind !=

NULL

);

740

assert((*matrix)->lhs !=

NULL

);

741

assert((*matrix)->rhs !=

NULL

);

742

assert((*matrix)->transformstatus !=

NULL

);

743

assert((*matrix)->transformshiftvals !=

NULL

);

760

(*matrix)->nrows = 0;

761

(*matrix)->ncols = 0;

775 int

* violatedrowpos,

785

assert(matrix !=

NULL

);

786

assert(violatedrows !=

NULL

);

787

assert(violatedrowpos !=

NULL

);

788

assert(nviolatedrows !=

NULL

);

796

assert(*nviolatedrows < matrix->nrows);

798

violatedrows[*nviolatedrows] = rowindex;

799

violatedrowpos[rowindex] = *nviolatedrows;

802

++rowweights[rowindex];

810 if

( violatedrowpos[rowindex] != *nviolatedrows - 1 )

812

assert(*nviolatedrows - 1 >= 0);

813

violatedrows[violatedrowpos[rowindex]] = violatedrows[*nviolatedrows - 1];

814

violatedrowpos[violatedrows[*nviolatedrows - 1]] = violatedrowpos[rowindex];

818

violatedrowpos[rowindex] = -1;

824 for

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

826

matrix->violrows[cols[c]] += violadd;

827

assert(matrix->violrows[cols[c]] >= 0);

840 int

* violatedrowpos,

850

assert(matrix !=

NULL

);

851

assert(violatedrows !=

NULL

);

852

assert(violatedrowpos !=

NULL

);

853

assert(nviolatedrows !=

NULL

);

854

assert(-1 <= colidx && colidx < matrix->ncols);

861

nrows = matrix->nrows;

866 for

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

867

violatedrowpos[i] = -1;

873

assert(colidx < 0 || *nviolatedrows >= 0);

876 for

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

881

assert(rowindices !=

NULL

);

882

rowpos = rowindices[i];

887 checkRowViolation

(

scip

, matrix, rowpos, violatedrows, violatedrowpos, nviolatedrows, rowweights, updateweights);

906

assert(matrix !=

NULL

);

907

assert(var !=

NULL

);

909

status = matrix->transformstatus[varindex];

917 return

solvalue + matrix->transformshiftvals[varindex];

922 return

matrix->transformshiftvals[varindex] - solvalue;

937 int

* violationchange,

954

assert(beststep !=

NULL

);

955

assert(rowviolations !=

NULL

);

956

assert(rowweights !=

NULL

);

957

assert(steps !=

NULL

);

958

assert(violationchange !=

NULL

);

959

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

961

upperbound = matrix->upperbounds[varindex];

971 for

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

983

lhs = matrix->lhs[rowpos];

984

rhs = matrix->rhs[rowpos];

985

rowweight = rowweights[rowpos];

986

val = direction * vals[i];

995 if

( !rowisviolated )

1011

slacksurplus -= val;

1018

slacksurplus += val;

1024

steps[i] = maxfeasshift + 1.0;

1025

violationchange[i] = rowweight;

1030

steps[i] = upperbound;

1031

violationchange[i] = 0;

1062

steps[i] = minfeasshift;

1063

violationchange[i] = -rowweight;

1068

steps[i] = upperbound;

1069

violationchange[i] = 0;

1080

*beststep = direction * upperbound;

1102

sum += violationchange[i];

1107 if

( (i == nrows-1 || steps[i+1] > steps[i]) && sum < *rowviolations )

1109

*rowviolations = sum;

1110

*beststep = direction * steps[i];

1113

assert(*rowviolations <= 0);

1132 int

* violatedrowpos,

1141

assert(matrix !=

NULL

);

1142

assert(0 <= varindex && varindex < matrix->ndiscvars);

1146

status = matrix->transformstatus[varindex];

1148 SCIPdebugMsg

(

scip

,

" Variable <%d> [%g,%g], status %d(%g), ub %g \n"

, varindex, lb, ub, status,

1149

matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);

1151

checkviolations =

FALSE

;

1159

checkviolations =

TRUE

;

1163

deltashift = lb - (matrix->transformshiftvals[varindex]);

1164

matrix->transformshiftvals[varindex] = lb;

1166

matrix->upperbounds[varindex] = ub - lb;

1175

checkviolations =

TRUE

;

1179

deltashift = (matrix->transformshiftvals[varindex]) - ub;

1180

matrix->transformshiftvals[varindex] = ub;

1196

checkviolations =

TRUE

;

1205 SCIPerrorMessage

(

"Error: Invalid variable status <%d> in shift and propagagate heuristic, aborting!\n"

, status);

1223 for

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

1225 SCIPdebugMsg

(

scip

,

" update slacks of row<%d>: coefficient <%g>, %g <= 0 <= %g \n"

,

1226

rows[i], vals[i], matrix->lhs[rows[i]], matrix->rhs[rows[i]]);

1229

matrix->lhs[rows[i]] -= (vals[i]) * deltashift;

1232

matrix->rhs[rows[i]] -= (vals[i]) * deltashift;

1234

checkviolations =

TRUE

;

1238 if

( checkviolations )

1239 checkViolations

(

scip

, matrix, varindex, violatedrows, violatedrowpos, nviolatedrows, heurdata->rowweights, heurdata->updateweights);

1241 SCIPdebugMsg

(

scip

,

" Variable <%d> [%g,%g], status %d(%g), ub %g \n"

, varindex, lb, ub, status,

1242

matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);

1264

assert(var1 !=

NULL

&& var2 !=

NULL

);

1323

assert(heurdata !=

NULL

);

1331 " DETAILS : %d violations left, %d probing status\n"

,

1332

heurdata->nremainingviols,

1337

heurdata->nprobings,

1338

heurdata->ntotaldomredsfound,

1340

heurdata->nlpiters);

1356

assert(heurdata !=

NULL

);

1364

heurdata->nremainingviols = 0;

1365

heurdata->nprobings = 0;

1366

heurdata->ntotaldomredsfound = 0;

1367

heurdata->ncutoffs = 0;

1368

heurdata->nlpiters = 0;

1382

assert(heurdata !=

NULL

);

1383

eventhdlr = heurdata->eventhdlr;

1384

assert(eventhdlr !=

NULL

);

1403

assert(heur !=

NULL

);

1427 int

* violationchange;

1430 int

* violatedrowpos;

1432 int

* violatedvarrows;

1437 int

lastindexofsusp;

1458

assert(heurdata !=

NULL

);

1460

eventhdlr = heurdata->eventhdlr;

1461

assert(eventhdlr !=

NULL

);

1464

assert(eventhdlrdata !=

NULL

);

1467 SCIPdebugMsg

(

scip

,

"entering execution method of shift and propagate heuristic\n"

);

1501

assert(nlpcols == 0 || lpcols !=

NULL

);

1504 if

( nlprows == 0 || nlpcols == 0 )

1508

initialized =

FALSE

;

1512

heurdata->nlpcols = nlpcols;

1514

impliscontinuous = heurdata->impliscontinuous;

1523 SCIPsortPtr

((

void

**)heurdata->lpcols, heurSortColsShiftandpropagate, nlpcols);

1532 for

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

1537

col = heurdata->lpcols[c];

1538

assert(col !=

NULL

);

1540

assert(colvar !=

NULL

);

1555

assert(nbinvars + nintvars <= ndiscvars);

1561 if

( heurdata->collectstats )

1574

infeasible =

FALSE

;

1578 SCIP_CALL

(

initMatrix

(

scip

, matrix, heurdata, colposs, &nmaxrows, heurdata->relax, &initialized, &infeasible) );

1581 if

( !initialized || infeasible )

1583 SCIPdebugMsg

(

scip

,

" MATRIX not initialized -> Execution of heuristic stopped! \n"

);

1590 if

( matrix->ndiscvars < ndiscvars )

1592 SCIPdebugMsg

(

scip

,

"Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n"

);

1596

assert(nmaxrows > 0);

1598

eventhdlrdata->matrix = matrix;

1599

eventhdlrdata->heurdata = heurdata;

1616

eventhdlrdata->violatedrows = violatedrows;

1617

eventhdlrdata->violatedrowpos = violatedrowpos;

1618

eventhdlrdata->nviolatedrows = &nviolatedrows;

1621 for

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

1625 for

(

r

= 0;

r

< matrix->nrows; ++

r

)

1632

colnorms = matrix->colnorms;

1634

assert(nbinvars >= 0);

1635

assert(nintvars >= 0);

1638 checkViolations

(

scip

, matrix, -1, violatedrows, violatedrowpos, &nviolatedrows, heurdata->rowweights, heurdata->updateweights);

1641 if

( heurdata->sortvars && (heurdata->sortkey ==

't'

|| heurdata->sortkey ==

'v'

) )

1647

violatedvarrows =

NULL

;

1652 if

( heurdata->sortvars )

1654 switch

(heurdata->sortkey)

1658 if

( heurdata->preferbinaries )

1662 if

( nbinvars < ndiscvars )

1669 SCIPdebugMsg

(

scip

,

"Variables sorted down w.r.t their normalized columns!\n"

);

1673 if

( heurdata->preferbinaries )

1677 if

( nbinvars < ndiscvars )

1678 SCIPsortRealInt

(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);

1684 SCIPdebugMsg

(

scip

,

"Variables sorted w.r.t their normalized columns!\n"

);

1688

assert(violatedvarrows !=

NULL

);

1689 if

( heurdata->preferbinaries )

1693 if

( nbinvars < ndiscvars )

1694 SCIPsortDownIntInt

(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);

1701 SCIPdebugMsg

(

scip

,

"Variables sorted down w.r.t their number of currently infeasible rows!\n"

);

1705

assert(violatedvarrows !=

NULL

);

1706 if

( heurdata->preferbinaries )

1710 if

( nbinvars < ndiscvars )

1711 SCIPsortIntInt

(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);

1718 SCIPdebugMsg

(

scip

,

"Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n"

);

1722 if

( heurdata->preferbinaries )

1726 if

( nbinvars < ndiscvars )

1728

ndiscvars - nbinvars - 1);

1743 if

( heurdata->binlocksfirst )

1746 int

nbinwithoutlocks = 0;

1749 if

( heurdata->preferbinaries )

1751 for

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

1761 for

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

1773 if

( nbinwithoutlocks > 0 )

1781 while

( c < nbinwithoutlocks &&

b

< ndiscvars )

1784

assert(c < ndiscvars);

1785

assert(

b

< ndiscvars);

1794 if

( c >= nbinwithoutlocks )

1798 if

( c >= nbinwithoutlocks )

1811

assert(

b

< ndiscvars);

1816

tmp = permutation[

b

];

1817

permutation[

b

] = permutation[c];

1818

permutation[c] = tmp;

1827 for

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

1840 for

( c = 0; c < matrix->ndiscvars; ++c )

1845

assert(var !=

NULL

);

1847

assert(eventdatas[c] ==

NULL

);

1851

eventdatas[c]->colpos = c;

1858

lastindexofsusp = -1;

1859

probing = heurdata->probing;

1860

infeasible =

FALSE

;

1862 SCIPdebugMsg

(

scip

,

"SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n"

,

1863

nviolatedrows, ndiscvars);

1865

assert(matrix->ndiscvars == ndiscvars);

1868 for

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

1877 int

permutedvarindex;

1881 if

( heurdata->selectbest )

1884 while

( j < ndiscvars )

1887 if

( matrix->violrows[permutation[c]] < matrix->violrows[permutation[j]] )

1890

tmp = permutation[c];

1891

permutation[c] = permutation[j];

1892

permutation[j] = tmp;

1897

permutedvarindex = permutation[c];

1898

optimalshiftvalue = 0.0;

1916 if

( heurdata->probing )

1922 SCIPdebugMsg

(

scip

,

"Variable %s with local bounds [%g,%g], status <%d>, matrix bound <%g>\n"

,

1923 SCIPvarGetName

(var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);

1936

marksuspicious =

FALSE

;

1956 if

( !heurdata->stopafterfeasible || nviolatedrows > 0 )

1960

&optimalshiftvalue, &nviolations) );

1967 int

ndownviolations;

1969

downshiftvalue = 0.0;

1970

ndownviolations = 0;

1972

&downshiftvalue, &ndownviolations) );

1977 if

( ndownviolations < nviolations )

1979

optimalshiftvalue = downshiftvalue;

1984

optimalshiftvalue = 0.0;

1987 if

( heurdata->nozerofixing && nviolations > 0 &&

SCIPisFeasZero

(

scip

, optimalshiftvalue) )

1988

marksuspicious =

TRUE

;

2005 if

( !marksuspicious && probing )

2016 SCIPdebugMsg

(

scip

,

" Shift %g(%g originally) is optimal, propagate solution\n"

, optimalshiftvalue, origsolval);

2020 SCIPstatistic

( heurdata->ntotaldomredsfound += ndomredsfound );

2024

assert(!cutoff || probing);

2034 if

( heurdata->cutoffbreaker >= 0 && ncutoffs >= ((heurdata->maxcutoffquot *

SCIPgetProbingDepth

(

scip

)) + heurdata->cutoffbreaker) )

2069 SCIPstatistic

( heurdata->ntotaldomredsfound += ndomredsfound );

2084 SCIPstatistic

( heurdata->ntotaldomredsfound += ndomredsfound );

2096

marksuspicious =

TRUE

;

2100 if

( marksuspicious )

2103

assert(permutedvarindex == permutation[c]);

2106

assert(lastindexofsusp >= 0 && lastindexofsusp <= c);

2108

permutation[c] = permutation[lastindexofsusp];

2109

permutation[lastindexofsusp] = permutedvarindex;

2111 SCIPdebugMsg

(

scip

,

" Suspicious variable! Postponed from pos <%d> to position <%d>\n"

, c, lastindexofsusp);

2115 SCIPdebugMsg

(

scip

,

"Variable <%d><%s> successfully shifted by value <%g>!\n"

, permutedvarindex,

2128 SCIPdebugMsg

(

scip

,

"Heuristic finished with %d remaining violations and %d remaining variables!\n"

,

2129

nviolatedrows, lastindexofsusp + 1);

2134 if

( nviolatedrows == 0 && !cutoff )

2140 for

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

2144 int

permutedvarindex;

2147

permutedvarindex = permutation[v];

2152 if

( heurdata->probing )

2169 if

( nviolatedrows > 0 )

2175 if

( nlpcols != matrix->ndiscvars )

2179 int

nminfixings = (int)(

SCIPceil

(

scip

, heurdata->minfixingratelp * nvars));

2180 int

nfixedvars = ndiscvars;

2185 for

( v = ndiscvars; v < nvars && nfixedvars < nminfixings; ++v )

2191

solvelp = (nfixedvars >= nminfixings);

2193 SCIPdebugMsg

(

scip

,

"Fixed %d of %d (%.1f %%) variables after probing -> %s\n"

,

2194

nfixedvars, nvars, (100.0 * nfixedvars / (

SCIP_Real

)nvars),

2195

solvelp ?

"continue and solve LP for remaining variables"

:

"terminate without LP"

);

2215

assert(vars !=

NULL

);

2217 for

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

2234 if

( nunfixedcols > 0.5 * ncols )

2237 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n"

,

2238

100.0 * (nunfixedcols / (

SCIP_Real

)ncols), nunfixedcols, ncols);

2258 SCIPwarningMessage

(

scip

,

"Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n"

,

2290

printreason =

TRUE

;

2292

printreason =

FALSE

;

2297

completely =

FALSE

;

2315 SCIPdebugMsg

(

scip

,

"Solution constructed by heuristic is already known to be infeasible\n"

);

2318 SCIPstatistic

( heurdata->nremainingviols = nviolatedrows; );

2322 for

( c = matrix->ndiscvars - 1; c >= 0; --c )

2327

assert(var !=

NULL

);

2328

assert(eventdatas[c] !=

NULL

);

2335 if

( violatedvarrows !=

NULL

)

2337

assert(heurdata->sortkey ==

'v'

|| heurdata->sortkey ==

't'

);

2349

eventhdlrdata->nviolatedrows =

NULL

;

2350

eventhdlrdata->violatedrowpos =

NULL

;

2351

eventhdlrdata->violatedrows =

NULL

;

2356

heurdata->ncutoffs += ncutoffs;

2357

heurdata->nprobings += nprobings;

2365

eventhdlrdata->matrix =

NULL

;

2385

assert(eventhdlr !=

NULL

);

2389

assert(eventhdlrdata !=

NULL

);

2391

matrix = eventhdlrdata->matrix;

2393

heurdata = eventhdlrdata->heurdata;

2394

assert(heurdata !=

NULL

&& heurdata->lpcols !=

NULL

);

2396

colpos = eventdata->colpos;

2398

assert(0 <= colpos && colpos < matrix->ndiscvars);

2400

col = heurdata->lpcols[colpos];

2407

eventhdlrdata->violatedrowpos, eventhdlrdata->nviolatedrows) );

2427

eventhandlerdata->matrix =

NULL

;

2431

eventExecShiftandpropagate, eventhandlerdata) );

2432

assert(eventhdlr !=

NULL

);

2436

heurdata->rowweights =

NULL

;

2437

heurdata->nlpcols = 0;

2438

heurdata->eventhdlr = eventhdlr;

2445

assert(heur !=

NULL

);

2455 "The number of propagation rounds used for each propagation"

,

2462 "Should heuristic only be executed if no primal solution was found, yet?"

,

2467 "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom"

,

2474 "Should the heuristic stop calculating optimal shift values when no more rows are violated?"

,

2477 "Should binary variables be shifted first?"

,

2480 "should variables with a zero shifting value be delayed instead of being fixed?"

,

2483 "should binary variables with no locks in one direction be fixed to that direction?"

,

2486 "should binary variables with no locks be preferred in the ordering?"

,

2489 "should coefficients be normalized by max row coeff for col norm?"

,

2492 "should row weight be increased every time the row is violated?"

,

2495 "should implicit integer variables be treated as continuous variables?"

,

2498 "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?"

,

2501 "maximum percentage of allowed cutoffs before stopping the heuristic"

,

2504 "minimum fixing rate over all variables (including continuous) to solve LP"

,

#define SCIP_MAXTREEDEPTH

#define SCIP_LONGINT_FORMAT

SCIP_Bool SCIPisStopped(SCIP *scip)

int SCIPgetNContVars(SCIP *scip)

int SCIPgetNVars(SCIP *scip)

SCIP_VAR ** SCIPgetVars(SCIP *scip)

void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)

void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)

SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)

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 SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)

SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)

void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)

SCIP_RETCODE SCIPincludeHeurShiftandpropagate(SCIP *scip)

int SCIPcolGetLPPos(SCIP_COL *col)

SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)

SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)

SCIP_Real * SCIPcolGetVals(SCIP_COL *col)

SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)

int SCIPcolGetNLPNonz(SCIP_COL *col)

SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)

SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)

const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)

SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)

SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)

SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)

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_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))

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

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_RETCODE SCIPflushLP(SCIP *scip)

SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)

SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)

SCIP_Bool SCIPisLPConstructed(SCIP *scip)

SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)

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

int SCIPgetNLPRows(SCIP *scip)

SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)

int SCIPgetNUnfixedLPCols(SCIP *scip)

int SCIPgetNLPCols(SCIP *scip)

SCIP_RETCODE SCIPwriteLP(SCIP *scip, const char *filename)

SCIP_Bool SCIPisLPSolBasic(SCIP *scip)

#define SCIPfreeBuffer(scip, ptr)

#define SCIPallocBufferArray(scip, ptr, num)

#define SCIPfreeBufferArray(scip, ptr)

#define SCIPallocBuffer(scip, ptr)

#define SCIPfreeBlockMemory(scip, ptr)

#define SCIPfreeBlockMemoryNull(scip, ptr)

#define SCIPallocBlockMemory(scip, ptr)

int SCIPgetProbingDepth(SCIP *scip)

SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)

char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)

SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)

SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)

SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)

SCIP_RETCODE SCIPstartProbing(SCIP *scip)

SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)

SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)

SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)

SCIP_RETCODE SCIPendProbing(SCIP *scip)

SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)

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_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)

const char * SCIProwGetName(SCIP_ROW *row)

SCIP_Real SCIProwGetConstant(SCIP_ROW *row)

SCIP_Real * SCIProwGetVals(SCIP_ROW *row)

SCIP_SOL * SCIPgetBestSol(SCIP *scip)

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)

void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)

SCIP_Longint SCIPgetNLPIterations(SCIP *scip)

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

SCIP_Real SCIPinfinity(SCIP *scip)

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

SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)

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

SCIP_Bool SCIPisFeasZero(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 SCIPisFeasNegative(SCIP *scip, SCIP_Real val)

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

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

SCIP_Real SCIPceil(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_Real SCIPepsilon(SCIP *scip)

SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)

int SCIPgetDepth(SCIP *scip)

SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)

SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)

SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)

void SCIPdisableVarHistory(SCIP *scip)

SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)

SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)

int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)

SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)

SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)

SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)

const char * SCIPvarGetName(SCIP_VAR *var)

SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)

SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)

SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)

int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)

void SCIPenableVarHistory(SCIP *scip)

SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)

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

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

void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)

void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)

void SCIPsortIntInt(int *intarray1, int *intarray2, int len)

void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)

void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)

#define DEFAULT_ONLYWITHOUTSOL

#define DEFAULT_NORMALIZE

static void relaxVar(SCIP *scip, SCIP_VAR *var, CONSTRAINTMATRIX *matrix)

static void transformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int colpos)

static SCIP_RETCODE getOptimalShiftingValue(SCIP *scip, CONSTRAINTMATRIX *matrix, int varindex, int direction, int *rowweights, SCIP_Real *steps, int *violationchange, SCIP_Real *beststep, int *rowviolations)

static void getRowData(CONSTRAINTMATRIX *matrix, int rowindex, SCIP_Real **valpointer, SCIP_Real *lhs, SCIP_Real *rhs, int **indexpointer, int *nrowvals)

static SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)

static void checkRowViolation(SCIP *scip, CONSTRAINTMATRIX *matrix, int rowindex, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)

#define DEFAULT_MINFIXINGRATELP

static SCIP_Bool colIsDiscrete(SCIP_COL *col, SCIP_Bool impliscontinuous)

#define DEFAULT_PROPBREAKER

#define DEFAULT_IMPLISCONTINUOUS

#define DEFAULT_PREFERBINARIES

#define DEFAULT_NPROPROUNDS

static SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)

#define DEFAULT_FIXBINLOCKS

static SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)

static void freeMatrix(SCIP *scip, CONSTRAINTMATRIX **matrix)

#define DEFAULT_SELECTBEST

#define DEFAULT_BINLOCKSFIRST

static SCIP_RETCODE updateTransformation(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int varindex, SCIP_Real lb, SCIP_Real ub, int *violatedrows, int *violatedrowpos, int *nviolatedrows)

static SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)

#define DEFAULT_MAXCUTOFFQUOT

#define DEFAULT_CUTOFFBREAKER

enum TransformStatus TRANSFORMSTATUS

#define DEFAULT_WEIGHT_INEQUALITY

#define DEFAULT_NOZEROFIXING

static SCIP_DECL_HEURCOPY(heurCopyShiftandpropagate)

static SCIP_DECL_HEURINIT(heurInitShiftandpropagate)

static void checkViolations(SCIP *scip, CONSTRAINTMATRIX *matrix, int colidx, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)

#define DEFAULT_UPDATEWEIGHTS

#define DEFAULT_COLLECTSTATS

static SCIP_Real retransformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR *var, int varindex, SCIP_Real solvalue)

static SCIP_Bool varIsDiscrete(SCIP_VAR *var, SCIP_Bool impliscontinuous)

struct ConstraintMatrix CONSTRAINTMATRIX

#define DEFAULT_WEIGHT_EQUALITY

static void getColumnData(CONSTRAINTMATRIX *matrix, int colindex, SCIP_Real **valpointer, int **indexpointer, int *ncolvals)

#define DEFAULT_STOPAFTERFEASIBLE

static SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)

static SCIP_RETCODE initMatrix(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int *colposs, int *nmaxrows, SCIP_Bool relax, SCIP_Bool *initialized, SCIP_Bool *infeasible)

#define EVENTTYPE_SHIFTANDPROPAGATE

preroot heuristic that alternatingly fixes variables and propagates domains

memory allocation routines

#define BMScopyMemoryArray(ptr, source, num)

#define BMSclearMemoryArray(ptr, num)

public methods for managing events

public methods for primal heuristics

public methods for LP management

public methods for message output

#define SCIPstatisticMessage

public data structures and miscellaneous methods

methods for sorting joint arrays of various types

public methods for primal CIP solutions

public methods for problem variables

public methods for event handler plugins and event handlers

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 SCIP parameter handling

public methods for global and local (sub)problems

public methods for the probing mode

public methods for random numbers

public methods for solutions

public methods for querying solving statistics

public methods for the branch-and-bound tree

public methods for SCIP variables

struct SCIP_EventData SCIP_EVENTDATA

struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA

struct SCIP_HeurData SCIP_HEURDATA

enum SCIP_LPSolStat SCIP_LPSOLSTAT

@ SCIP_LPSOLSTAT_NOTSOLVED

enum SCIP_Retcode SCIP_RETCODE

@ SCIP_VARTYPE_CONTINUOUS

enum SCIP_Vartype SCIP_VARTYPE

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