RetroSearch Browse

(0,

(end, ect) -

(lst, begin));

401#define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin)))) 413#ifdef SCIP_DISABLED_CODE 426#ifdef SCIP_DISABLED_CODE 434 for

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

437

assert(vbdvar !=

);

446

duration = (int)(

size_t

)image;

449 SCIPdebugMsg

(

"check implication <%s>[%g,%g] >= <%s>[%g,%g] + <%g>\n"

453 if

( duration >= vbdconst )

459 if

( (*est) < impliedest )

483#ifdef SCIP_DISABLED_CODE 495#ifdef SCIP_DISABLED_CODE 503 for

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

506

assert(vbdvar !=

);

514 SCIPdebugMsg

(

"check implication <%s>[%g,%g] <= <%s>[%g,%g] + <%g>\n"

518 if

( duration >= -vbdconst )

524 if

( (*lct) > impliedlct )

558

startindex = nstarted - 1;

564 while

( nstarted - nfinished > nrowvars )

573

varidx = startindices[startindex];

574

assert(varidx >= 0 && varidx < consdata->nvars);

576

var = consdata->vars[varidx];

577

duration = consdata->durations[varidx];

578

demand = consdata->demands[varidx];

579

assert(var !=

);

584 if

( endtime > curtime )

602

start = curtime - duration + 1;

603

end =

(curtime, endtime - duration);

605 for

(

= 0;

< nbinvars; ++

)

607 if

( vals[

] < start )

610 if

( vals[

] > end )

613

assert(binvars[

] !=

);

616 if

( size == *nvars )

623

(*vars)[*nvars] = binvars[

];

624

(*coefs)[*nvars] = demand;

661

assert(curtime >= consdata->hmin);

662

assert(curtime < consdata->hmax);

669

startindex = nstarted - 1;

672 while

( nstarted - nfinished > counter )

674

assert(startindex >= 0);

677

varidx = startindices[startindex];

678

assert(varidx >= 0 && varidx < consdata->nvars);

680

var = consdata->vars[varidx];

681

duration = consdata->durations[varidx];

682

assert(duration > 0);

683

assert(var !=

);

690

endtime =

(starttime + duration, consdata->hmax);

693 if

( endtime > curtime )

695

(*activevars)[counter] = var;

696

sumofstarts += starttime;

697

mindelta =

(mindelta, endtime - curtime);

704

assert(mindelta > 0);

705

*lhs = lower ? sumofstarts + mindelta : sumofstarts - mindelta;

727

assert(vars !=

|| nvars == 0);

730 for

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

732

assert(vars !=

);

735

assert(var !=

);

774

assert(vars !=

|| nvars == 0);

777 for

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

779

assert(vars !=

);

782

assert(var !=

);

817

tmpnvars = consdata->nvars;

821 for

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

823

var = consdata->vars[j];

824

assert(var !=

);

825

assert(consdata->durations[j] > 0);

826

assert(consdata->demands[j] > 0);

836

startindices[*nvars] = j;

838

endtimes[*nvars] = starttimes[*nvars] + consdata->durations[j];

839

endindices[*nvars] = j;

841 SCIPdebugMsg

(

"%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n"

843

consdata->durations[j],

844

starttimes[*nvars], starttimes[*nvars] + consdata->durations[startindices[*nvars]],

845

consdata->demands[startindices[*nvars]]);

856

startindices[*nvars] = j;

858

endtimes[*nvars] = starttimes[*nvars] + consdata->durations[j];

859

endindices[*nvars] = j;

861 SCIPdebugMsg

(

"%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n"

863

consdata->durations[j],

864

starttimes[*nvars], starttimes[*nvars] + consdata->durations[startindices[*nvars]],

865

consdata->demands[startindices[*nvars]]);

878 for

( j = 0; j < *nvars; ++j )

880 SCIPdebugMsg

(

"%d: job[%d] starttime %d, endtime = %d, demand = %d\n"

, j,

881

startindices[j], starttimes[j], starttimes[j] + consdata->durations[startindices[j]],

882

consdata->demands[startindices[j]]);

885 for

( j = 0; j < *nvars; ++j )

887 SCIPdebugMsg

(

"%d: job[%d] endtime %d, demand = %d\n"

, j, endindices[j], endtimes[j],

888

consdata->demands[endindices[j]]);

924

assert(durations !=

);

925

assert(demands !=

);

926

assert(capacity >= 0);

932

assert(vars !=

);

946

(*timepoints)[0] = starttimes[0];

947

(*cumulativedemands)[0] = 0;

951 for

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

956

curtime = starttimes[j];

958 if

( curtime >= hmax )

962 while

( endindex < nvars && endtimes[endindex] <= curtime )

966 if

( (*timepoints)[*ntimepoints] < endtimes[endindex] )

969

(*timepoints)[*ntimepoints] = endtimes[endindex];

970

(*cumulativedemands)[*ntimepoints] = 0;

973

idx = endindices[endindex];

975

totaldemand -= (

) demands[idx] * durations[idx] / (endtimes[endindex] - est);

978

(*cumulativedemands)[*ntimepoints] = totaldemand;

981

idx = startindices[j];

983

totaldemand += (

) demands[idx] * durations[idx] / (lct - starttimes[j]);

985 if

( (*timepoints)[*ntimepoints] < curtime )

988

(*timepoints)[*ntimepoints] = curtime;

989

(*cumulativedemands)[*ntimepoints] = 0;

992

(*cumulativedemands)[*ntimepoints] = totaldemand;

995 while

( j+1 < nvars && starttimes[j+1] == curtime )

998

idx = startindices[j];

1000

totaldemand += (

) demands[idx] * durations[idx] / (lct - starttimes[j]);

1002

(*cumulativedemands)[*ntimepoints] = totaldemand;

1007 while

( endindex < nvars

)

1012 if

( (*timepoints)[*ntimepoints] < endtimes[endindex] )

1015

(*timepoints)[*ntimepoints] = endtimes[endindex];

1016

(*cumulativedemands)[*ntimepoints] = 0;

1019

idx = endindices[endindex];

1021

totaldemand -= (

) demands[idx] * durations[idx] / (endtimes[endindex] - est);

1022

(*cumulativedemands)[*ntimepoints] = totaldemand;

1029

(*minfreecapacity) = INT_MAX;

1030 for

( j = 0; j < *ntimepoints; ++j )

1032 if

( (*timepoints)[j] >= hmin && (*timepoints)[j] < hmax )

1033

*minfreecapacity =

( *minfreecapacity, (

)capacity - (*cumulativedemands)[j] );

1069

assert(consdata !=

);

1071

nvars = consdata->nvars;

1072

capacity = consdata->capacity;

1074

globalmaxdemand = 0.0;

1081 for

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

1092

peak = consdata->demands[v];

1097 if

( consdata->demands[v] > capacity / 3 )

1100 for

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

1110 if

( lb <= timepoint && lb + consdata->durations[j] > timepoint )

1112

peak += consdata->demands[j];

1115 if

( consdata->demands[j] > consdata->capacity / 3 )

1121

globalpeak =

(globalpeak, peak);

1122

globalmaxdemand =

(globalmaxdemand, maxdemand);

1124 if

( peak > capacity )

1126

disjfactor2 =

( disjfactor2, (peak-(

)capacity)/peak * (nlarge/(

)ndemands) );

1127

cumfactor1 =

( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(

)capacity );

1128

resstrength2 =

(resstrength2, (capacity-maxdemand)/(peak-maxdemand) );

1132

resstrength1 = (capacity-globalmaxdemand) / (globalpeak-globalmaxdemand);

1135

consdata->disjfactor2 = disjfactor2;

1136

consdata->cumfactor1 = cumfactor1;

1137

consdata->resstrength2 = resstrength2;

1138

consdata->resstrength1 = resstrength1;

1152

minfreecapacity = INT_MAX;

1154 SCIP_CALL

( computeRelevantEnergyIntervals(

, nvars, consdata->vars,

1155

consdata->durations, consdata->demands,

1156

capacity, consdata->hmin, consdata->hmax, &timepoints, &estimateddemands,

1157

&ntimepoints, &maxdemand, &minfreecapacity) );

1163

consdata->estimatedstrength = (

)(capacity - minfreecapacity) / (

) capacity;

1166 SCIPstatisticPrintf

(

"cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n"

1167 SCIPconsGetName

(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,

1168

consdata->estimatedstrength);

1198 if

( realconstant < 0.0 )

1203 if

( realscalar < 0.0 )

1214

assert(*scalar != 0);

1232 for

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

1274

assert(subscip !=

);

1285 for

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

1292 if

( objvals ==

)

1295

objval = objvals[v];

1303

njobs, subvars, durations, demands, capacity) );

1348

(*infeasible) =

;

1352

(*unbounded) =

;

1361

assert(sol !=

);

1363 for

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

1380 for

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

1402 for

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

1423

(*infeasible) =

;

1424

(*unbounded) =

;

1427 SCIPdebugMessage

(

"solve independent cumulative condition with %d variables\n"

, njobs);

1434

njobs, capacity, hmin, hmax,

1435

maxnodes, timelimit, memorylimit,

1437

infeasible, unbounded, solved, error);

1447#ifdef SCIP_DISABLED_CODE 1466

(*infeasible) =

;

1467

(*unbounded) =

;

1470 SCIPdebugMsg

(

"solve independent cumulative condition with %d variables\n"

, njobs);

1489 for

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

1497 if

( objvals ==

)

1500

objval = objvals[v];

1506

timeinterval = lst - est + 1;

1507

assert(timeinterval > 0);

1510

minest =

(minest, est);

1511

maxlct =

(maxlct, lst + durations[v]);

1520 for

( t = 0; t < timeinterval; ++t )

1533

binvars[v][t] = binvar;

1542

hmin =

(hmin, minest);

1543

hmax =

(hmax, maxlct);

1544

assert(hmin > INT_MIN);

1545

assert(hmax < INT_MAX);

1546

assert(hmin < hmax);

1549 for

( t = hmin; t < hmax; ++t )

1560 for

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

1573

duration = durations[v];

1574

assert(duration > 0);

1577 if

( t < est || t >= lst + duration )

1580

demand = demands[v];

1581

assert(demand >= 0);

1583

start =

(t - duration + 1, est);

1586

assert(start <= end);

1588 for

( k = start; k <= end; ++k )

1590

assert(binvars[v][k] !=

);

1625

(*infeasible) =

;

1629

(*unbounded) =

;

1637

assert(sol !=

);

1639 for

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

1649

timeinterval = lst - est + 1;

1652 for

( t = 0; t < timeinterval; ++t )

1672 for

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

1682

timeinterval = lst - est + 1;

1685 for

( t = 0; t < timeinterval; ++t )

1695 for

( t = timeinterval - 1; t >= 0; --t )

1718 for

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

1728

timeinterval = lst - est + 1;

1730 for

( t = 0; t < timeinterval; ++t )

1765

assert(conshdlrdata !=

);

1766

assert(eventhdlr !=

);

1771

(*conshdlrdata)->eventhdlr = eventhdlr;

1774

(*conshdlrdata)->solveCumulative = solveCumulativeViaScipCp;

1776#ifdef SCIP_STATISTIC 1777

(*conshdlrdata)->nlbtimetable = 0;

1778

(*conshdlrdata)->nubtimetable = 0;

1779

(*conshdlrdata)->ncutofftimetable = 0;

1780

(*conshdlrdata)->nlbedgefinder = 0;

1781

(*conshdlrdata)->nubedgefinder = 0;

1782

(*conshdlrdata)->ncutoffedgefinder = 0;

1783

(*conshdlrdata)->ncutoffoverload = 0;

1784

(*conshdlrdata)->ncutoffoverloadTTEF = 0;

1786

(*conshdlrdata)->nirrelevantjobs = 0;

1787

(*conshdlrdata)->nalwaysruns = 0;

1788

(*conshdlrdata)->nremovedlocks = 0;

1789

(*conshdlrdata)->ndualfixs = 0;

1790

(*conshdlrdata)->ndecomps = 0;

1791

(*conshdlrdata)->ndualbranchs = 0;

1792

(*conshdlrdata)->nallconsdualfixs = 0;

1793

(*conshdlrdata)->naddedvarbounds = 0;

1794

(*conshdlrdata)->naddeddisjunctives = 0;

1807

assert(conshdlrdata !=

);

1808

assert(*conshdlrdata !=

);

1832

assert(consdata !=

);

1833

assert(eventhdlr !=

);

1836 for

( v = 0; v < consdata->nvars; ++v )

1855

assert(consdata !=

);

1856

assert(eventhdlr !=

);

1857

assert(0 <= pos && pos < consdata->nvars);

1858

assert(consdata->vars[pos] !=

);

1877

assert(consdata !=

);

1880 for

( v = 0; v < consdata->nvars; ++v )

1898

nvars = consdata->nvars;

1901 for

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

1903

consdata->downlocks[v] = locked;

1904

consdata->uplocks[v] = locked;

1927

assert(consdata !=

);

1928

assert(vars !=

|| nvars > 0);

1929

assert(demands !=

);

1930

assert(durations !=

);

1931

assert(capacity >= 0);

1933

assert(hmin < hmax);

1938

(*consdata)->hmin = hmin;

1939

(*consdata)->hmax = hmax;

1941

(*consdata)->capacity = capacity;

1942

(*consdata)->demandrows =

;

1943

(*consdata)->demandrowssize = 0;

1944

(*consdata)->ndemandrows = 0;

1945

(*consdata)->scoverrows =

;

1946

(*consdata)->nscoverrows = 0;

1947

(*consdata)->scoverrowssize = 0;

1948

(*consdata)->bcoverrows =

;

1949

(*consdata)->nbcoverrows = 0;

1950

(*consdata)->bcoverrowssize = 0;

1951

(*consdata)->nvars = nvars;

1952

(*consdata)->varssize = nvars;

1953

(*consdata)->signature = 0;

1954

(*consdata)->validsignature =

;

1955

(*consdata)->normalized =

;

1956

(*consdata)->covercuts =

;

1957

(*consdata)->propagated =

;

1958

(*consdata)->varbounds =

;

1959

(*consdata)->triedsolving =

;

1963

assert(vars !=

);

1968

(*consdata)->linkingconss =

;

1976 if

( linkingconss !=

)

1992 for

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

1997 if

( linkingconss !=

)

2002 for

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

2011 for

( v = 0; v < (*consdata)->nvars; ++v )

2017

(*consdata)->vars =

;

2018

(*consdata)->downlocks =

;

2019

(*consdata)->uplocks =

;

2020

(*consdata)->demands =

;

2021

(*consdata)->durations =

;

2022

(*consdata)->linkingconss =

;

2026

(*consdata)->resstrength1 = -1.0;

2027

(*consdata)->resstrength2 = -1.0;

2028

(*consdata)->cumfactor1 = -1.0;

2029

(*consdata)->disjfactor1 = -1.0;

2030

(*consdata)->disjfactor2 = -1.0;

2031

(*consdata)->estimatedstrength = -1.0;

2047

assert(consdata !=

);

2048

assert(*consdata !=

);

2050 for

(

= 0;

< (*consdata)->ndemandrows; ++

)

2052

assert((*consdata)->demandrows[

] !=

);

2058

(*consdata)->ndemandrows = 0;

2059

(*consdata)->demandrowssize = 0;

2062 for

(

= 0;

< (*consdata)->nscoverrows; ++

)

2064

assert((*consdata)->scoverrows[

] !=

);

2070

(*consdata)->nscoverrows = 0;

2071

(*consdata)->scoverrowssize = 0;

2073 for

(

= 0;

< (*consdata)->nbcoverrows; ++

)

2075

assert((*consdata)->bcoverrows[

] !=

);

2081

(*consdata)->nbcoverrows = 0;

2082

(*consdata)->bcoverrowssize = 0;

2084

(*consdata)->covercuts =

;

2099

assert(consdata !=

);

2100

assert(*consdata !=

);

2102

nvars = (*consdata)->nvars;

2103

varssize = (*consdata)->varssize;

2113 if

( (*consdata)->linkingconss !=

)

2115 for

( v = nvars-1; v >= 0; --v )

2117

assert((*consdata)->linkingconss[v] !=

);

2148

assert(consdata !=

);

2153 for

( v = 0; v < consdata->nvars; ++v )

2155

assert(consdata->vars[v] !=

);

2160

consdata->durations[v], consdata->demands[v]);

2162 SCIPinfoMessage

(

, file,

")[%d,%d) <= %d"

, consdata->hmin, consdata->hmax, consdata->capacity);

2178

assert(consdata !=

);

2179

assert(cons !=

);

2183 SCIPdebugMsg

(

"cumulative constraint <%s>: remove variable <%s>\n"

2189

consdata->downlocks[pos] =

;

2190

consdata->uplocks[pos] =

;

2192 if

( consdata->linkingconss !=

)

2199

assert(conshdlr !=

);

2201

assert(conshdlrdata !=

);

2202

assert(conshdlrdata->eventhdlr !=

);

2207 SCIPdebugMsg

(

"remove variable <%s>[%g,%g] from cumulative constraint <%s>\n"

2213 if

( pos != consdata->nvars - 1 )

2215

consdata->vars[pos] = consdata->vars[consdata->nvars-1];

2216

consdata->downlocks[pos] = consdata->downlocks[consdata->nvars-1];

2217

consdata->uplocks[pos] = consdata->uplocks[consdata->nvars-1];

2218

consdata->demands[pos] = consdata->demands[consdata->nvars-1];

2219

consdata->durations[pos] = consdata->durations[consdata->nvars-1];

2221 if

( consdata->linkingconss !=

)

2223

consdata->linkingconss[pos]= consdata->linkingconss[consdata->nvars-1];

2228

consdata->validsignature =

;

2229

consdata->normalized =

;

2245

assert(consdata !=

);

2247

nvars = consdata->nvars;

2249

assert(consdata->linkingconss ==

);

2253 for

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

2258

var = consdata->vars[v];

2259

assert(var !=

);

2274

consdata->linkingconss[v] = cons;

2283

assert(consdata->linkingconss[v] !=

);

2318 int

* startsolvalues;

2332

assert(violated !=

);

2334

(*violated) =

;

2339

assert(vars !=

);

2340

assert(demands !=

);

2341

assert(durations !=

);

2350 for

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

2362

startsolvalues[j] =

(solvalue, hmin);

2363

startindices[j] = j;

2365

endsolvalues[j] =

(solvalue + durations[j], hmin);

2376

freecapacity = capacity;

2381 for

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

2384

curtime = startsolvalues[j];

2386 if

( curtime >= hmax )

2390

freecapacity -= demands[startindices[j]];

2391 while

( j+1 < nvars && startsolvalues[j+1] == curtime )

2394

freecapacity -= demands[startindices[j]];

2398 while

( endindex < nvars && curtime >= endsolvalues[endindex] )

2400

freecapacity += demands[endindices[endindex]];

2403

assert(freecapacity <= capacity);

2406 if

( absviol < (

) (-freecapacity) )

2408

absviol = -freecapacity;

2413 if

( freecapacity < 0 && curtime >= hmin )

2416

(*violated) =

;

2427 ";\nviolation: at time point %d available capacity = %d, needed capacity = %d\n"

2428

curtime, capacity, capacity - freecapacity);

2430 for

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

2432 if

( startsolvalues[i] + durations[startindices[i]] > curtime )

2435 SCIPvarGetName

(vars[startindices[i]]), startsolvalues[i], durations[startindices[i]],

2436

demands[startindices[i]]);

2472

assert(cons !=

);

2473

assert(violated !=

);

2478

assert(consdata !=

);

2482

consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,

2483

violated, cons, printreason) );

2527 SCIPdebugMsg

(

"variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n"

2532

capacity -= inferdemand;

2542 for

( j = 0; j < nvars && capacity >= 0; ++j )

2545

assert(var !=

);

2548 if

( var == infervar )

2551

duration = durations[j];

2552

assert(duration > 0);

2560 SCIPdebugMsg

(

"variable <%s>: glb=[%g,%g] conflict=[%g,%g] (duration %d, demand %d)\n"

2570 if

( inferpeak < ect && lst <= inferpeak )

2572

capacity -= demands[j];

2573

reported[j] =

;

2575

maxlst =

(maxlst, lst);

2576

minect =

(minect, ect);

2577

assert(maxlst < minect);

2579 if

( explanation !=

)

2580

explanation[j] =

;

2597 if

( inferpeak < ect && lst <= inferpeak )

2599

capacity -= demands[j];

2600

reported[j] =

;

2602

maxlst =

(maxlst, lst);

2603

minect =

(minect, ect);

2604

assert(maxlst < minect);

2606 if

( explanation !=

)

2607

explanation[j] =

;

2611 if

( capacity >= 0 )

2623 for

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

2626

assert(var !=

);

2629 if

( var == infervar || reported[j] )

2632

duration = durations[j];

2633

assert(duration > 0);

2645 SCIPdebugMsg

(

"variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n"

2650 if

( inferpeak < ect && lst <= inferpeak )

2653

canddemands[ncands] = demands[j];

2656

capacity -= demands[j];

2663

assert(capacity < 0);

2667 while

( capacity + canddemands[ncands-1] < 0 )

2670

capacity += canddemands[ncands];

2675 for

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

2677

var = vars[cands[c]];

2678

assert(var !=

);

2680

duration = durations[cands[c]];

2685

maxlst =

(maxlst, lst);

2686

minect =

(minect, ect);

2687

assert(maxlst < minect);

2690 SCIPdebugMsg

(

"infer peak %d, relaxed peak %d, lst %d, ect %d\n"

, inferpeak, relaxedpeak, maxlst, minect);

2691

assert(inferpeak >= maxlst);

2692

assert(inferpeak < minect);

2695 if

( relaxedpeak < inferpeak )

2697

inferpeak =

(maxlst, relaxedpeak);

2699 else if

( relaxedpeak > inferpeak )

2701

inferpeak =

(minect-1, relaxedpeak);

2703

assert(inferpeak >= hmin);

2704

assert(inferpeak < hmax);

2705

assert(inferpeak >= maxlst);

2706

assert(inferpeak < minect);

2709 for

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

2711

var = vars[cands[c]];

2712

assert(var !=

);

2714 if

( usebdwidening )

2716

duration = durations[cands[c]];

2727 if

( explanation !=

)

2728

explanation[cands[c]] =

;

2737 if

( provedpeak !=

)

2738

*provedpeak = inferpeak;

2758

ect = est + duration;

2759

lct = lst + duration;

2762 if

( lct <= end && est >= begin )

2765

assert(lst <= end && ect >= begin);

2773 return MIN3

(left, right, end - begin);

2811

requiredenergy = ((

) end - begin) * capacity;

2818 for

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

2828

assert(var !=

);

2834

demand = demands[v];

2837

duration = durations[v];

2838

assert(duration > 0);

2841 if

( infervar == var )

2849 SCIPdebugMsg

(

"inference variable <%s>[%g,%g] %s %g (duration %d, demand %d)\n"

2872

right =

MIN3

(end - lst, end - begin, duration);

2878

assert(begin <= lct);

2882

left =

(lct - begin + 1, end - begin);

2886

overlap =

(left, right);

2887

assert(overlap > 0);

2888

assert(overlap <= end - begin);

2889

assert(overlap <= duration);

2891 if

( usebdwidening )

2914

assert(ect > begin);

2919

left =

MIN3

(ect - begin, end - begin, duration);

2929

right =

(end - est + 1, end - begin);

2933

overlap =

(left, right);

2934

assert(overlap > 0);

2935

assert(overlap <= end - begin);

2936

assert(overlap <= duration);

2938 if

( usebdwidening )

2952 if

( explanation !=

)

2953

explanation[v] =

;

2967 if

( est + duration > begin && lst < end )

2970

glbenergy =

computeOverlap

(begin, end, est, lst, duration) * demand;

2973

requiredenergy -= glbenergy;

2975 if

( explanation !=

)

2976

explanation[v] =

;

2986 if

( est + duration > begin && lst < end )

2991

locenergies[v] = overlaps[v] * demand - glbenergy;

2992

assert(locenergies[v] >= 0);

3000 for

( v = 0; v < nvars && requiredenergy >= 0; ++v )

3010

assert(idx >= 0 && idx < nvars);

3013

assert(var !=

);

3014

assert(var != infervar);

3016

duration = durations[idx];

3017

assert(duration > 0);

3019

overlap = overlaps[v];

3020

assert(overlap > 0);

3022

requiredenergy -= locenergies[v];

3024 if

( requiredenergy < -1 )

3028

demand = demands[idx];

3031

overlap += (int)((requiredenergy + 1) / demand);

3034

requiredenergy += locenergies[v];

3036

assert(requiredenergy < 0);

3039

assert(overlap > 0);

3041

relaxlb = begin - duration + overlap;

3042

relaxub = end - overlap;

3044 SCIPdebugMsg

(

"variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n"

3049

relaxlb, relaxub, demands[idx], duration);

3054 if

( explanation !=

)

3055

explanation[idx] =

;

3058

assert(requiredenergy < 0);

3101 if

( inferpos >= nvars || vars[inferpos] != infervar )

3104 for

( inferpos = 0; inferpos < nvars && vars[inferpos] != infervar; ++inferpos )

3107

assert(inferpos < nvars);

3108

assert(vars[inferpos] == infervar);

3110

inferdemand = demands[inferpos];

3111

inferduration = durations[inferpos];

3120 SCIPdebugMsg

(

"variable <%s>: upper bound changed from %g to %g (relaxed %g)\n"

3133

relaxedpeak =

(relaxedpeak, hmax-1);

3139

relaxedpeak =

(relaxedpeak, inferpeak);

3140

assert(relaxedpeak >= inferpeak);

3141

assert(relaxedpeak >= hmin);

3147 SCIPdebugMsg

(

"variable <%s>: lower bound changed from %g to %g (relaxed %g)\n"

3160

relaxedpeak =

(relaxedpeak, hmin);

3166

relaxedpeak =

(relaxedpeak, inferpeak);

3167

assert(relaxedpeak < hmax);

3172

infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );

3176 if

( usebdwidening )

3190 if

( usebdwidening )

3201 if

( explanation !=

)

3202

explanation[inferpos] =

;

3214

assert(begin < end);

3216

begin =

(begin, hmin);

3217

end =

(end, hmax);

3220

begin, end, infervar, boundtype, bdchgidx, relaxedbd, usebdwidening, explanation) );

3251 int

* alternativelbs,

3252 int

* alternativeubs,

3260 for

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

3266

assert(var !=

);

3276 if

( alternativelbs[v] <= ub )

3279

(*branched) =

;

3294 if

( alternativeubs[v] >= lb )

3297

(*branched) =

;

3322#if defined SCIP_DEBUG && !defined NDEBUG 3325

assert(idx !=

);

3328

assert(idx !=

);

3331

assert(starttimes !=

);

3332

assert(starttimes !=

);

3333

assert(freecapacity !=

);

3334

assert(starttimes[*idx] == curtime);

3335

assert(consdata->demands !=

);

3336

assert(freecapacity != idx);

3339

(*freecapacity) -= consdata->demands[startindices[*idx]];

3341 while

( (*idx)+1 < nvars && starttimes[(*idx)+1] == curtime )

3344

(*freecapacity) -= consdata->demands[startindices[(*idx)]];

3345

assert(freecapacity != idx);

3348

assert(oldidx <= *idx);

3364#if defined SCIP_DEBUG && !defined NDEBUG 3370 while

( endtimes[*idx] <= curtime && *idx < nvars)

3372

(*freecapacity) += consdata->demands[endindices[*idx]];

3377

assert(oldidx <= *idx);

3405

assert(consdata !=

);

3407

nvars = consdata->nvars;

3410

*timepoint = consdata->hmax;

3412

assert(consdata->vars !=

);

3421

starttimes, endtimes, startindices, endindices);

3424

freecapacity = consdata->capacity;

3425

hmin = consdata->hmin;

3426

hmax = consdata->hmax;

3429 for

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

3431

curtime = starttimes[j];

3434 if

( curtime >= hmax )

3441 addEndingJobDemands

(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);

3443

assert(freecapacity <= consdata->capacity);

3444

assert(endindex <= nvars);

3450 if

( freecapacity < 0 && curtime >= hmin )

3452

*timepoint = curtime;

3480

assert(conss !=

);

3484

SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,

) );

3487

assert(conss !=

);

3489 for

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

3498

assert(cons !=

);

3504

assert(consdata !=

);

3509 if

( curtime < consdata->hmin || curtime >= consdata->hmax )

3513 for

( j = 0; j < consdata->nvars; ++j )

3519

var = consdata->vars[j];

3520

assert(var !=

);

3529 if

( lb <= curtime && ub + consdata->durations[j] > curtime && lb < ub )

3535

score =

(solval - lb, ub - solval) / ((

)ub-lb);

3571 if

( nbranchcands > 0 )

3582 for

( c = 0; c < nconss && !violated; ++c )

3587

assert(cons !=

);

3620

assert(consdata !=

);

3622

nvars = consdata->nvars;

3623

vars = consdata->vars;

3624

downlocks = consdata->downlocks;

3625

uplocks = consdata->uplocks;

3628 for

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

3633

assert(var !=

);

3693 if

( ncheckconss == 1 )

3738

assert(consdata !=

);

3743 if

( consdata->triedsolving )

3753

consdata->triedsolving =

;

3755 SCIPdebugMsg

(

"the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n"

3759

nvars = consdata->nvars;

3760

vars = consdata->vars;

3766 for

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

3774

assert(var !=

);

3797

consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved, cutoff, unbounded, &error) );

3799 if

( !(*cutoff) && !(*unbounded) && !error )

3807 for

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

3810 if

( lbs[v] + 0.5 > ubs[v] )

3813

assert(!infeasible);

3818

consdata->triedsolving =

;

3824

assert(!infeasible);

3829

consdata->triedsolving =

;

3833

assert(!infeasible);

3838

consdata->triedsolving =

;

3880 SCIPdebugMsg

(

"detected infeasibility due to adding a core to the core resource profile\n"

);

3890

infervar, inferdemand, inferpeak, inferpeak,

, usebdwidening,

, explanation) );

3895 if

( usebdwidening )

3906

*initialized =

;

3948

assert(var !=

);

3950

duration = durations[idx];

3951

assert(duration > 0);

3953

demand = demands[idx];

3965 SCIPdebugMsg

(

"propagate earliest start time (lower bound) (pos %d)\n"

, pos);

3980

assert(pos == tmppos);

3983

ect = est + duration;

4011

newlb =

(newlb, ect);

4020

var, duration, demand, newlb-1, usebdwidening, initialized, explanation) );

4022 if

( explanation !=

)

4023

explanation[idx] =

;

4025

*infeasible =

;

4045

assert(!(*infeasible));

4060

assert(est >= newlb);

4068 while

( est < lst );

4099

assert(var !=

);

4100

assert(duration > 0);

4112

lct = lst + duration;

4141

assert(pos == tmppos);

4170

newub =

(newub, lst) - duration;

4171

assert(newub >= est);

4188

assert(!infeasible);

4203

assert(lst <= newub);

4204

lct = lst + duration;

4212 while

( est < lst );

4226 int

* coreEnergyAfterEst,

4227 int

* coreEnergyAfterLct

4236

t = ntimepoints - 1;

4240 for

( v = nvars-1; v >= 0; --v )

4258

coreEnergyAfterEst[v] = energy;

4261

t = ntimepoints - 1;

4265 for

( v = nvars-1; v >= 0; --v )

4283

coreEnergyAfterLct[v] = energy;

4308 for

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

4319

duration = durations[v];

4320

assert(duration > 0);

4324

ect = est + duration;

4325

lct = lst + duration;

4336

leftadjust =

(0, hmin - est);

4339

rightadjust =

(0, lct - hmax);

4342

flexenergies[v] = duration - leftadjust - rightadjust - core;

4343

flexenergies[v] =

(0, flexenergies[v]);

4344

flexenergies[v] *= demands[v];

4345

assert(flexenergies[v] >= 0);

4348

ects[v] =

(ect, lst);

4351

lsts[v] =

(ect, lst);

4385

assert(begin >= hmin);

4386

assert(end <= hmax);

4389 if

( !conshdlrdata->ttefinfer )

4393 if

( est >= end || ect <= begin )

4399 if

( est >= begin && ect <= end )

4420

newlb = end - (int) (energy / demand);

4425 if

( newlb > lct - duration )

4447

(*initialized) =

;

4452 else if

( newlb > (*bestlb) )

4456

assert(newlb > begin);

4498

assert(begin >= hmin);

4499

assert(end <= hmax);

4500

assert(est < begin);

4503 if

( !conshdlrdata->ttefinfer )

4507 if

( lst >= end || lct <= begin )

4513 if

( lst >= begin && lct <= end )

4527

assert(energy >= 0);

4534

newub = begin - duration + (int) (energy / demand);

4561

(*initialized) =

;

4566 else if

( newub < (*bestub) )

4570

assert(newub < begin);

4603 int

* coreEnergyAfterEst,

4604 int

* coreEnergyAfterLct,

4610 int

coreEnergyAfterEnd;

4625 for

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

4630

est =

(est, start);

4631

lct =

(lct, end);

4635

hmin =

(hmin, est);

4636

hmax =

(hmax, lct);

4639

coreEnergyAfterEnd = -1;

4641

maxavailable = ((

) hmax - hmin) * capacity;

4642

minavailable = maxavailable;

4646 if

( ((

) lcts[0] - ests[nvars-1]) * capacity >= totalenergy )

4654 for

( v = nvars-1; v >= 0 && !(*cutoff); --v )

4673

assert(v == 0 || lcts[v-1] <= lcts[v]);

4689 if

( !conshdlrdata->ttefinfer && end <= hmax && minavailable < maxavailable )

4693

assert(coreEnergyAfterLct[v] >= coreEnergyAfterEnd);

4694

assert(coreEnergyAfterEnd >= 0);

4697

freeenergy = capacity * ((

) end - lct) - coreEnergyAfterLct[v] + coreEnergyAfterEnd;

4699 if

( freeenergy <= minavailable )

4709

coreEnergyAfterEnd = coreEnergyAfterLct[v];

4712

minavailable = maxavailable;

4721 for

( i = nests-1; i >= 0; --i )

4733

assert(idx < nvars);

4751 if

( ((

) end - est) * capacity >= totalenergy )

4755

assert(var !=

);

4757

duration = durations[idx];

4758

assert(duration > 0);

4760

demand = demands[idx];

4771

assert(est <= minbegin);

4772 if

( minavailable < maxavailable && est < minbegin )

4778

var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),

4779

initialized, explanation, cutoff) );

4785 SCIPdebugMsg

(

"check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n"

4801

assert(lst >= begin);

4802

assert(flexenergies[idx] >= 0);

4803

flexenergy += flexenergies[idx];

4816

energy =

(flexenergies[idx], demands[idx] *

(0, (end - lst)));

4817

assert(end - lst < duration);

4818

assert(energy >= 0);

4821

flexenergy += energy;

4824

candenergy =

(flexenergies[idx], demands[idx] * (end - begin)) - energy;

4825

assert(candenergy >= 0);

4828 if

( candenergy > lbenergy )

4830

lbenergy = candenergy;

4835 SCIPdebugMsg

(

"time window [%d,%d) flexible energy <%d>\n"

, begin, end, flexenergy);

4836

assert(coreEnergyAfterEst[i] >= coreEnergyAfterEnd);

4839

freeenergy = capacity * ((

) end - begin) - flexenergy - coreEnergyAfterEst[i] + coreEnergyAfterEnd;

4842 if

( freeenergy < 0 )

4844 SCIPdebugMsg

(

"analyze overload within time window [%d,%d) capacity %d\n"

, begin, end, capacity);

4854

conshdlrdata->usebdwidening, explanation) );

4856

(*initialized) =

;

4868 if

( lbenergy > 0 && freeenergy < lbenergy )

4880

newlb = end - (int)(energy / demands[lbcand]);

4892

relaxedbd = lst + 1.0;

4899

conshdlrdata->usebdwidening, explanation) );

4901

(*initialized) =

;

4907 else if

( newlb > newlbs[lbcand] )

4916

newlbs[lbcand] = newlb;

4921 if

( minavailable > freeenergy )

4923

minavailable = freeenergy;

4926

assert(minavailable >= 0);

4954 int

* coreEnergyAfterEst,

4955 int

* coreEnergyAfterLct,

4961 int

coreEnergyAfterStart;

4982 for

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

4987

minest =

(minest, start);

4988

maxlct =

(maxlct, end);

4992

hmin =

(hmin, minest);

4993

hmax =

(hmax, maxlct);

4995

maxavailable = ((

) hmax - hmin) * capacity;

4999 if

( ((

) lcts[0] - ests[nvars-1]) * capacity >= totalenergy )

5007 for

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

5034

assert(est > begin);

5039

coreEnergyAfterStart = coreEnergyAfterEst[v];

5042

minavailable = maxavailable;

5050 for

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

5062

assert(idx < nvars);

5080 if

( ((

) lct - begin) * capacity >= totalenergy )

5084

assert(var !=

);

5086

duration = durations[idx];

5087

assert(duration > 0);

5089

demand = demands[idx];

5100

assert(lct >= minend);

5101 if

( minavailable < maxavailable && lct > minend )

5107

var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),

5108

initialized, explanation, cutoff) );

5114 SCIPdebugMsg

(

"check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n"

5131

assert(flexenergies[idx] >= 0);

5132

flexenergy += flexenergies[idx];

5145

energy =

(flexenergies[idx], demands[idx] *

(0, (ect - begin)));

5146

assert(ect - begin < duration);

5147

assert(energy >= 0);

5150

flexenergy += energy;

5153

candenergy =

(flexenergies[idx], demands[idx] * (end - begin)) - energy;

5154

assert(candenergy >= 0);

5157 if

( candenergy > ubenergy )

5159

ubenergy = candenergy;

5164 SCIPdebugMsg

(

"time window [%d,%d) flexible energy <%d>\n"

, begin, end, flexenergy);

5165

assert(coreEnergyAfterLct[i] <= coreEnergyAfterStart);

5168

freeenergy = capacity * ((

) end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[i];

5171 if

( freeenergy < 0 )

5173 SCIPdebugMsg

(

"analyze overload within time window [%d,%d) capacity %d\n"

, begin, end, capacity);

5183

conshdlrdata->usebdwidening, explanation) );

5185

(*initialized) =

;

5197 if

( ubenergy > 0 && freeenergy < ubenergy )

5203

duration = durations[ubcand];

5204

assert(duration > 0);

5212

newub = begin - duration + (int)(energy / demands[ubcand]);

5214 if

( newub < ect - duration )

5223

relaxedbd = ect - duration - 1.0;

5230

conshdlrdata->usebdwidening, explanation) );

5232

(*initialized) =

;

5238 else if

( newub < newubs[ubcand] )

5247

newubs[ubcand] = newub;

5252 if

( minavailable > freeenergy )

5254

minavailable = freeenergy;

5257

assert(minavailable >= 0);

5293 int

* coreEnergyAfterEst;

5294 int

* coreEnergyAfterLct;

5315 if

( !conshdlrdata->ttefcheck )

5336 for

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

5340

lbinferinfos[v] = 0;

5341

ubinferinfos[v] = 0;

5345 collectDataTTEF

(

, nvars, vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);

5358

newlbs, newubs, lbinferinfos, ubinferinfos, lsts, flexenergies,

5359

permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );

5363

newlbs, newubs, lbinferinfos, ubinferinfos, ects, flexenergies,

5364

permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );

5367 for

( v = 0; v < nvars && !(*cutoff); ++v )

5375 TRUE

, &infeasible, &tightened) );

5383

assert(!infeasible);

5396 TRUE

, &infeasible, &tightened) );

5420

assert(var !=

);

5431

assert(begin < end);

5439

conshdlrdata->usebdwidening, explanation) );

5441

(*initialized) =

;

5507

assert(cons !=

);

5508

assert(cutoff !=

);

5515 if

( !conshdlrdata->ttinfer )

5518

assert(*initialized ==

);

5520 SCIPdebugMsg

(

"propagate cores of cumulative condition of constraint <%s>[%d,%d) <= %d\n"

5523

infeasible =

;

5530 for

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

5541

assert(var !=

);

5543

duration = durations[v];

5544

assert(duration > 0);

5555 if

( lst + duration <= hmin || est >= hmax )

5559

begin =

(hmin, lst);

5560

end =

(hmax, est + duration);

5562

demand = demands[v];

5568 SCIPdebugMsg

(

"variable <%s>[%g,%g] (duration %d, demand %d): remove core [%d,%d)\n"

5576

profile, v, nchgbds, conshdlrdata->usebdwidening, initialized, explanation, cutoff) );

5583

profile, v, nchgbds) );

5593

begin =

(hmin, lst);

5594

end =

(hmax, est + duration);

5601 SCIPdebugMsg

(

"variable <%s>[%d,%d] (duration %d, demand %d): add core [%d,%d)\n"

5610

var, duration, demand,

SCIPprofileGetTime

(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );

5612 if

( explanation !=

)

5613

explanation[v] =

;

5663 SCIPdebugMsg

(

"update envelop starting from node <%p>\n"

, (

void

*)node);

5668 while

( node !=

)

5676

assert(left !=

);

5678

assert(leftdata !=

);

5682

assert(right !=

);

5684

assert(rightdata !=

);

5687 if

( leftdata->enveloptheta >= 0 )

5689

assert(rightdata->energytheta != -1);

5690 nodedata

->enveloptheta =

(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta);

5693 nodedata

->enveloptheta = rightdata->enveloptheta;

5695

assert(leftdata->energytheta != -1);

5696

assert(rightdata->energytheta != -1);

5697 nodedata

->energytheta = leftdata->energytheta + rightdata->energytheta;

5699 if

( leftdata->enveloplambda >= 0 )

5701

assert(rightdata->energytheta != -1);

5702 nodedata

->enveloplambda =

(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda);

5705 nodedata

->enveloplambda = rightdata->enveloplambda;

5707 if

( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0 )

5708 nodedata

->enveloplambda =

(

->enveloplambda, leftdata->enveloptheta + rightdata->energylambda);

5712 if

( leftdata->energylambda >= 0 && rightdata->energylambda >= 0 )

5714

assert(rightdata->energytheta != -1);

5715

assert(leftdata->energytheta != -1);

5716 nodedata

->energylambda =

(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda);

5718 else if

( rightdata->energylambda >= 0 )

5720

assert(leftdata->energytheta != -1);

5721 nodedata

->energylambda = leftdata->energytheta + rightdata->energylambda;

5723 else if

( leftdata->energylambda >= 0 )

5725

assert(rightdata->energytheta != -1);

5726 nodedata

->energylambda = leftdata->energylambda + rightdata->energytheta;

5745

assert(node !=

);

5752

assert(parent !=

);

5783

assert(tree !=

);

5784

assert(node !=

);

5792

assert(parent !=

);

5803

assert(sibling !=

);

5807 if

( grandparent !=

)

5854

assert(tree !=

);

5855

assert(node !=

);

5862

assert(

->enveloptheta != -1);

5863

assert(

->energytheta != -1);

5864

assert(

->enveloplambda == -1);

5865

assert(

->energylambda == -1);

5905

assert(leaf !=

);

5908

assert(leafdata !=

);

5917 if

(

->key < leafdata->key )

5923

assert(leafdata !=

);

5926

assert(leaf !=

);

5927

assert(leaf != node);

5930

newnodedata = &nodedatas[*nnodedatas];

5931

nodedataidx[*nnodedatas] = *nnodedatas;

5935

newnodedata->var =

;

5937

newnodedata->est = INT_MIN;

5938

newnodedata->lct = INT_MAX;

5939

newnodedata->duration = 0;

5940

newnodedata->demand = 0;

5941

newnodedata->enveloptheta = -1;

5942

newnodedata->energytheta = 0;

5943

newnodedata->enveloplambda = -1;

5944

newnodedata->energylambda = -1;

5945

newnodedata->idx = -1;

5946

newnodedata->intheta =

;

5950

assert(newnode !=

);

5954 if

( parent !=

)

5971 if

(

->key < leafdata->key )

5983

newnodedata->key = leafdata->key;

6008

assert(node !=

);

6021

assert(left !=

);

6024

assert(leftdata !=

);

6027

assert(right !=

);

6030

assert(rightdata !=

);

6032

assert(

->energylambda != -1);

6033

assert(rightdata->energytheta != -1);

6035 if

( leftdata->energylambda >= 0 &&

->energylambda == leftdata->energylambda + rightdata->energytheta )

6038

assert(leftdata->energytheta != -1);

6039

assert(rightdata->energylambda != -1);

6040

assert(

->energylambda == leftdata->energytheta + rightdata->energylambda);

6057

assert(node !=

);

6070

assert(left !=

);

6073

assert(leftdata !=

);

6076

assert(right !=

);

6079

assert(rightdata !=

);

6081

assert(

->enveloplambda != -1);

6082

assert(rightdata->energytheta != -1);

6085 if

( leftdata->enveloplambda >= 0 &&

->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )

6087 else if

( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0

6088

->enveloplambda == leftdata->enveloptheta + rightdata->energylambda )

6091

assert(rightdata->enveloplambda != -1);

6092

assert(

->enveloplambda == rightdata->enveloplambda);

6124

omegaset[*nelements] = node;

6144

assert(node !=

);

6162

assert(left !=

);

6165

assert(leftdata !=

);

6168

assert(right !=

);

6171

assert(rightdata !=

);

6176

assert(

->enveloptheta != -1);

6177

assert(rightdata->energytheta != -1);

6179 if

( leftdata->enveloptheta >= 0 &&

->enveloptheta == leftdata->enveloptheta + rightdata->energytheta )

6186

assert(rightdata->enveloptheta != -1);

6187

assert(

->enveloptheta == rightdata->enveloptheta);

6210

assert(node !=

);

6220

assert(left !=

);

6223

assert(leftdata !=

);

6226

assert(right !=

);

6229

assert(rightdata !=

);

6231

assert(

->energylambda != -1);

6232

assert(rightdata->energytheta != -1);

6234 if

( leftdata->energylambda >= 0 &&

->energylambda == leftdata->energylambda + rightdata->energytheta )

6241

assert(leftdata->energytheta != -1);

6242

assert(rightdata->energylambda != -1);

6243

assert(

->energylambda == leftdata->energytheta + rightdata->energylambda);

6267

assert(node !=

);

6280

assert(left !=

);

6283

assert(leftdata !=

);

6286

assert(right !=

);

6289

assert(rightdata !=

);

6291

assert(

->enveloplambda != -1);

6292

assert(rightdata->energytheta != -1);

6294 if

( leftdata->enveloplambda >= 0 &&

->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )

6301 if

( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0

6302

->enveloplambda == leftdata->enveloptheta + rightdata->energylambda )

6309

assert(rightdata->enveloplambda != -1);

6310

assert(

->enveloplambda == rightdata->enveloplambda);

6330

assert(duration > 0);

6332 SCIPdebugMessage

(

"variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n"

6337 return nodedata

->demand * duration;

6350 return

(est1 - est2);

6360 return

(nodedatas[ind1].lct - nodedatas[ind2].lct);

6391 SCIPdebugMsg

(

"est=%d, lct=%d, propest %u, reportedenergy %d, shift %d\n"

, est, lct, propest, reportedenergy, shift);

6402 for

( j = 0; j < nleaves && reportedenergy <= energy; ++j )

6418

assert(reportedenergy > energy);

6446 for

( j = nleaves-1; j >= 0; --j )

6455 if

( usebdwidening )

6466 if

( explanation !=

)

6470

(*initialized) =

;

6535

assert(rootdata !=

);

6538 for

( j = ncands-1; j >= 0 && !(*cutoff); --j )

6564

assert(leaf !=

);

6568

assert(leafdata !=

);

6569

assert(!leafdata->intheta);

6570

assert(leafdata->duration > 0);

6571

assert(leafdata->est >= 0);

6574 if

( leafdata->est + leafdata->duration >=

->lct )

6580

assert(rootdata !=

);

6595

assert(nelements > 0);

6596

assert(nelements < ncands);

6603 SCIPdebugMsg

(

"an overload was detected duration edge-finder propagattion\n"

);

6607

conshdlrdata->usebdwidening, initialized, explanation) );

6613 else if

( newest > 0 )

6635 TRUE

, &infeasible, &tightened) );

6657 TRUE

, &infeasible, &tightened) );

6667

leafdata->est = newest;

6686 if

( explanation !=

)

6687

explanation[leafdata->idx] =

;

6690 for

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

6698 if

( explanation !=

)

6702

(*initialized) =

;

6720

assert(rootdata !=

);

6770

assert(cons !=

);

6771

assert(initialized !=

);

6772

assert(cutoff !=

);

6773

assert(*cutoff ==

);

6796 for

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

6801

shift =

(shift, lct);

6808 for

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

6820

assert(var !=

);

6822

duration = durations[j];

6823

assert(duration > 0);

6834 if

( conshdlrdata->useadjustedjobs )

6838

leftadjust = (hmin - est);

6843

rightadjust = (lct - hmax);

6850 if

( duration - leftadjust - rightadjust <= 0 )

6853 else if

( est < hmin || lct > hmax )

6856

energy = demands[j] * (duration - leftadjust - rightadjust);

6859

totalenergy += energy;

6882

nodedataidx[ncands] = ncands;

6887 nodedata

->key = est + j / (2.0 * nvars);

6893 nodedata

->leftadjust = leftadjust;

6894 nodedata

->rightadjust = rightadjust;

6909

nnodedatas = ncands;

6912 SCIPsortInd

(nodedataidx, compNodedataLct, (

void

*)nodedatas, ncands);

6919 for

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

6924

idx = nodedataidx[j];

6929 if

( ((

) nodedatas[idx].lct - nodedatas[idx].est) * capacity >= totalenergy )

6932

nodedatas[idx].est = -1;

6941

assert(nnodedatas <= 2*nvars);

6944

leaves[ninsertcands] = leaf;

6949

assert(rootdata !=

);

6952 if

( rootdata->enveloptheta > (

) capacity * nodedatas[idx].lct )

6954 SCIPdebugMsg

(

"detects cutoff due to overload in time window [?,%d) (ncands %d)\n"

, nodedatas[idx].lct, j);

6973

est = nodedatas[idx].est;

6974

lct = nodedatas[idx].lct;

6979 for

( j = j+1; j < ncands; ++j )

6986

idx = nodedataidx[j];

6998

duration -= (est - glbest);

7001

duration -= (glblct - lct);

7005

glbenery +=

->demand * duration;

7007 if

( explanation !=

)

7014

conshdlrdata->usebdwidening, initialized, explanation) );

7016 else if

( ninsertcands > 1 && conshdlrdata->efinfer )

7020

propest, shift, initialized, explanation, nchgbds, cutoff) );

7063 if

( !conshdlrdata->efcheck )

7068

cons,

, initialized, explanation, nchgbds, cutoff) );

7075 if

( !conshdlrdata->efinfer )

7080

cons,

, initialized, explanation, nchgbds, cutoff) );

7117

assert(redundant !=

);

7119

(*redundant) =

;

7125

assert(vars !=

);

7135 for

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

7137

assert(durations[j] > 0);

7138

assert(demands[j] > 0);

7141

assert(var !=

);

7147 if

( lb >= hmax || ub + durations[j] <= hmin )

7150

starttimes[njobs] =

(lb, hmin);

7151

startindices[njobs] = j;

7153

endtimes[njobs] =

(ub + durations[j], hmax);

7154

endindices[njobs] = j;

7155

assert(starttimes[njobs] <= endtimes[njobs]);

7164

freecapacity = capacity;

7167 for

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

7169

curtime = starttimes[j];

7172 if

( curtime >= hmax )

7176

freecapacity -= demands[startindices[j]];

7177 while

( j+1 < njobs && starttimes[j+1] == curtime )

7180

freecapacity -= demands[startindices[j]];

7184 while

( endtimes[endindex] <= curtime )

7186

freecapacity += demands[endindices[endindex]];

7189

assert(freecapacity <= capacity);

7192 if

( freecapacity < 0 && curtime >= hmin )

7194

(*redundant) =

;

7231 for

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

7244

assert(var !=

);

7248

duration = durations[v];

7249

assert(duration > 0);

7251

demand = demands[v];

7259 if

( lst + duration <= hmin || est >= hmax )

7263

begin =

(hmin, lst);

7264

end =

(hmax, est + duration);

7270 SCIPdebugMsg

(

"variable <%s>[%d,%d] (duration %d, demand %d): add core [%d,%d)\n"

7284

var, duration, demand,

SCIPprofileGetTime

(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );

7286 if

( explanation !=

)

7287

explanation[v] =

;

7326

assert(nchgbds !=

);

7327

assert(initialized !=

);

7328

assert(cutoff !=

);

7343 SCIP_CALL_TERMINATE

( retcode,

createCoreProfile

(

, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax,

7344

initialized, explanation, cutoff), TERMINATE );

7349 SCIP_CALL_TERMINATE

( retcode,

propagateTimetable

(

, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, cons,

7350

nchgbds, initialized, explanation, cutoff), TERMINATE );

7356 SCIP_CALL_TERMINATE

( retcode,

propagateEdgeFinding

(

, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,

7357

cons, initialized, explanation, nchgbds, cutoff), TERMINATE );

7363 SCIP_CALL_TERMINATE

( retcode,

propagateTTEF

(

, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, cons,

7364

nchgbds, initialized, explanation, cutoff), TERMINATE );

7391

assert(cons !=

);

7394

assert(consdata !=

);

7396

oldnchgbds = *nchgbds;

7397

initialized =

;

7411

consdata->nvars, consdata->vars, consdata->durations, consdata->demands, consdata->capacity,

7412

consdata->hmin, consdata->hmax, cons,

7413

nchgbds, &redundant, &initialized,

, cutoff) );

7417 SCIPdebugMsg

(

"%s deletes cumulative constraint <%s> since it is redundant\n"

7431

assert(*cutoff ==

);

7437 if

( *cutoff || *nchgbds > oldnchgbds )

7444

consdata->propagated =

;

7479

assert(probingpos >= 0);

7480

assert(probingpos < nvars);

7481

assert(success !=

);

7482

assert(cutoff !=

);

7484

var = vars[probingpos];

7485

assert(var !=

);

7491

(*success) =

;

7498

leftimpllbs, leftimplubs, leftproplbs, leftpropubs, cutoff) );

7533

rightimpllbs, rightimplubs, rightproplbs, rightpropubs, cutoff) );

7563

assert(roundable !=

);

7580

assert(scalar != 0);

7596

*roundable =

;

7612

assert(roundable !=

);

7629

assert(scalar != 0);

7645

*roundable =

;

7661 int

* alternativelbs,

7662 int

* alternativeubs,

7671 for

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

7680

assert(cons !=

);

7687

assert(consdata !=

);

7688

assert(consdata->nvars > 1);

7713

hmin = consdata->hmin;

7714

hmax = consdata->hmax;

7718

assert(consdata !=

);

7720

nvars = consdata->nvars;

7722 for

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

7728

var = consdata->vars[v];

7729

assert(var !=

);

7743 if

( consdata->downlocks[v] )

7750

ect = est + consdata->durations[v];

7752 if

( ect <= hmin || hmin >= hmax )

7754 else if

( est < hmin && alternativelbs[idx] >= (hmin + 1 - constant) / scalar )

7756

alternativelbs[idx] = (hmin + 1 - constant) / scalar;

7762 if

( consdata->uplocks[v] )

7768

duration = consdata->durations[v];

7772

lct = lst + duration;

7774 if

( lst >= hmax || hmin >= hmax )

7776 else if

( lct > hmax && alternativeubs[idx] <= ((hmax - 1 - constant) / scalar) - duration )

7778

alternativeubs[idx] = ((hmax - 1 - constant) / scalar) - duration;

7794 int

* alternativelbs,

7795 int

* alternativeubs,

7822 for

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

7832

assert(var !=

);

7835 if

( alternativelbs[v] == INT_MAX && alternativeubs[v] == INT_MIN )

7851 if

( alternativelbs[v] > ub )

7854

assert(!infeasible);

7873

downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,

7874

nfixedvars, &success, cutoff) );

7897 if

( alternativeubs[v] < lb )

7900

assert(!infeasible);

7919

downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,

7920

nfixedvars, &success, cutoff) );

7959 int

* alternativelbs;

7960 int

* alternativeubs;

7969

oldnfixedvars = *nfixedvars;

7978 for

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

7982

alternativelbs[v] = INT_MAX;

7983

alternativeubs[v] = INT_MIN;

7991

nfixedvars, cutoff) );

7993 if

( !(*cutoff) && oldnfixedvars == *nfixedvars && branched !=

)

8040

assert(cons !=

);

8044

assert(consdata !=

);

8046

nvars = consdata->nvars;

8053

remainingcap = consdata->capacity;

8056 for

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

8063 if

( startvalues[j] <= time && ub + consdata->durations[j] > time )

8066 if

( startvalues[j] == ub )

8068

remainingcap -= consdata->demands[j];

8072

demands[nflexible] = consdata->demands[j];

8073

flexibleids[nflexible] = j;

8078

assert(remainingcap >= 0);

8094 while

( j < nflexible && sumdemand <= remainingcap )

8096

sumdemand += demands[j];

8102

assert(sumdemand > remainingcap);

8103

assert(bigcoversize < nflexible);

8115 for

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

8127

idx = flexibleids[j];

8131

assert(nbinvars != 0);

8134

assert(vals !=

);

8140

start = time - consdata->durations[idx] + 1;

8141

end =

(time, ub);

8144 for

(

= 0;

< nbinvars; ++

)

8146 if

( vals[

] < start || vals[

] < lb )

8149 if

( vals[

] > end )

8152

assert(binvars[

] !=

);

8160 if

( consdata->bcoverrowssize == 0 )

8162

consdata->bcoverrowssize = 10;

8165 if

( consdata->nbcoverrows == consdata->bcoverrowssize )

8167

consdata->bcoverrowssize *= 2;

8171

consdata->bcoverrows[consdata->nbcoverrows] = row;

8172

consdata->nbcoverrows++;

8182 while

( sumdemand <= remainingcap )

8185

sumdemand += demands[j];

8189

smallcoversize = nflexible - (j + 1) - 1;

8190 while

( j > 0 && demands[j] == demands[nflexible-1] )

8193

assert(smallcoversize < nflexible);

8195 if

( smallcoversize != 1 || smallcoversize != nflexible - (j + 1) - 1 )

8204 for

( j = j + 1; j < nflexible; ++j )

8216

idx = flexibleids[j];

8220

assert(nbinvars != 0);

8223

assert(vals !=

);

8229

start = time - consdata->durations[idx] + 1;

8230

end =

(time, ub);

8233 for

(

= 0;

< nbinvars; ++

)

8235 if

( vals[

] < start || vals[

] < lb )

8238 if

( vals[

] > end )

8241

assert(binvars[

] !=

);

8248 if

( consdata->scoverrowssize == 0 )

8250

consdata->scoverrowssize = 10;

8253 if

( consdata->nscoverrows == consdata->scoverrowssize )

8255

consdata->scoverrowssize *= 2;

8259

consdata->scoverrows[consdata->nscoverrows] = row;

8260

consdata->nscoverrows++;

8281 int

* startvaluessorted;

8282 int

* endvaluessorted;

8298

assert(cons !=

);

8301

assert(consdata !=

);

8304 if

( consdata->vars ==

)

8307

nvars = consdata->nvars;

8308

hmin = consdata->hmin;

8309

hmax = consdata->hmax;

8319 for

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

8322

startvaluessorted[j] = startvalues[j];

8325

endvaluessorted[j] = endvalues[j];

8327

startindices[j] = j;

8337

freecapacity = consdata->capacity;

8340 for

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

8342

curtime = startvaluessorted[j];

8343 if

( curtime >= hmax )

8347

freecapacity -= consdata->demands[startindices[j]];

8349 while

( j+1 < nvars && startvaluessorted[j+1] == curtime )

8352

freecapacity -= consdata->demands[startindices[j]];

8356 while

( endidx < nvars && curtime >= endvaluessorted[endidx] )

8358

freecapacity += consdata->demands[endindices[endidx]];

8362

assert(freecapacity <= consdata->capacity);

8363

assert(endidx <= nvars);

8372 if

( freecapacity < 0 && curtime >= hmin )

8374 int

nextprofilechange;

8378

nextprofilechange =

( startvaluessorted[j+1], endvaluessorted[endidx] );

8380

nextprofilechange = endvaluessorted[endidx];

8382

nextprofilechange =

(nextprofilechange, hmax);

8384 for

( t = curtime; t < nextprofilechange; ++t )

8394

consdata->covercuts =

;

8429

assert(nstarted > nfinished);

8432

assert(consdata !=

);

8433

assert(consdata->nvars > 0);

8435

capacity = consdata->capacity;

8436

assert(capacity > 0);

8452 for

(

= 0;

< nbinvars; ++

)

8468 for

(

= 0;

< nbinvars; ++

)

8476 if

( consdata->demandrowssize == 0 )

8478

consdata->demandrowssize = 10;

8481 if

( consdata->ndemandrows == consdata->demandrowssize )

8483

consdata->demandrowssize *= 2;

8487

consdata->demandrows[consdata->ndemandrows] = row;

8488

consdata->ndemandrows++;

8525

assert(cons !=

);

8528

assert(consdata !=

);

8530

nvars = consdata->nvars;

8536

assert(consdata->vars !=

);

8543 SCIPdebugMsg

(

"create sorted event points for cumulative constraint <%s> with %d jobs\n"

8548

starttimes, endtimes, startindices, endindices,

);

8551

freecapacity = consdata->capacity;

8552

hmin = consdata->hmin;

8553

hmax = consdata->hmax;

8556 for

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

8558

curtime = starttimes[j];

8561 if

( curtime >= hmax )

8568 addEndingJobDemands

(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);

8570

assert(freecapacity <= consdata->capacity);

8571

assert(endindex <= nvars);

8577 if

( freecapacity < 0 && curtime >= hmin )

8584

nextstarttime = starttimes[j+1];

8586

nextstarttime = endtimes[nvars-1];

8588

nextstarttime =

(nextstarttime, hmax);

8595 for

( t = curtime+1 ; t < nextstarttime; ++t )

8600 if

( freecapacity < 0 )

8641

assert(consdata !=

);

8642

assert(consdata->demandrows ==

);

8643

assert(consdata->ndemandrows == 0);

8646 if

( consdata->linkingconss ==

)

8686

assert(consdata !=

);

8688 if

( consdata->demandrows ==

)

8690

assert(consdata->ndemandrows == 0);

8697 for

(

= 0;

< consdata->ndemandrows && !(*infeasible); ++

)

8701

assert(consdata->demandrows[

] !=

);

8724

assert(cons !=

);

8725

assert(separated !=

);

8726

assert(cutoff !=

);

8728

*separated =

;

8732

assert(consdata !=

);

8736 if

( consdata->demandrows ==

)

8738

assert(consdata->ndemandrows == 0);

8748 for

(

= 0;

< consdata->ndemandrows; ++

)

8779

(*separated) =

;

8801

assert(cons !=

);

8802

assert(separated !=

);

8803

assert(cutoff !=

);

8805

*separated =

;

8809

assert(consdata !=

);

8814 if

( consdata->linkingconss ==

)

8819 if

( !consdata->covercuts )

8828 for

(

= 0;

< consdata->nscoverrows; ++

)

8834

assert(consdata->scoverrows[

] !=

);

8840 if

( minfeasibility > feasibility )

8842

minfeasibility = feasibility;

8843

row = consdata->scoverrows[

];

8852 SCIPdebugMsg

(

"cumulative constraint <%s> separated 1 cover cut with feasibility %g\n"

8859

(*separated) =

;

8866 for

(

= 0;

< consdata->nbcoverrows; ++

)

8872

assert(consdata->bcoverrows[

] !=

);

8878 if

( minfeasibility > feasibility )

8880

minfeasibility = feasibility;

8881

row = consdata->bcoverrows[

];

8890 SCIPdebugMsg

(

"cumulative constraint <%s> separated 1 cover cut with feasibility %g\n"

8893

assert(row !=

);

8898

(*separated) =

;

8926

assert(nstarted > nfinished);

8929

assert(consdata !=

);

8930

assert(consdata->nvars > 0);

8952 for

( v = 0; v < nstarted - nfinished; ++v )

8998

assert(cons !=

);

9001

assert(consdata !=

);

9003

nvars = consdata->nvars;

9009

assert(consdata->vars !=

);

9016 SCIPdebugMsg

(

"create sorted event points for cumulative constraint <%s> with %d jobs\n"

9025

freecapacity = consdata->capacity;

9026

hmin = consdata->hmin;

9027

hmax = consdata->hmax;

9030 for

( j = 0; j < nvars && !(*cutoff); ++j )

9032

curtime = starttimes[j];

9034 if

( curtime >= hmax )

9041 addEndingJobDemands

(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);

9043

assert(freecapacity <= consdata->capacity);

9044

assert(endindex <= nvars);

9050 if

( freecapacity < 0 && curtime >= hmin)

9091

assert(cons !=

);

9094

assert(consdata !=

);

9096

nvars = consdata->nvars;

9102

assert(consdata->vars !=

);

9103

capacity = consdata->capacity;

9106 for

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

9108 if

( consdata->demands[j] > capacity )

9131

assert(cons !=

);

9134

assert(consdata !=

);

9136 if

( consdata->nvars == 0 )

9143 else if

( consdata->nvars == 1 )

9145 if

( consdata->demands[0] > consdata->capacity )

9179

assert(cons !=

);

9182

assert(consdata !=

);

9184

hmin = consdata->hmin;

9185

hmax = consdata->hmax;

9187 SCIPdebugMsg

(

"check for irrelevant jobs within cumulative constraint <%s>[%d,%d)\n"

9190 for

( j = consdata->nvars-1; j >= 0; --j )

9192

var = consdata->vars[j];

9193

demand = consdata->demands[j];

9194

duration = consdata->durations[j];

9200 if

( demand == 0 || duration == 0 )

9209 else if

( est >= hmax || lct <= hmin )

9211 SCIPdebugMsg

(

" remove variable <%s>[%d,%d] with duration <%d>\n"

9245

assert(consdata->durations[pos] > 0);

9246

assert(consdata->demands[pos] > 0);

9248

var = consdata->vars[pos];

9249

assert(var !=

);

9250

duration = consdata->durations[pos];

9253 SCIPdebugMsg

(

" variable <%s>: demand <%d> is larger than the capacity <%d>\n"

9254 SCIPvarGetName

(var), consdata->demands[pos], consdata->capacity);

9261 if

( ect - duration >= consdata->hmax || lst + duration <= consdata->hmin)

9264 if

( ect > consdata->hmin && lst < consdata->hmax )

9269 else if

( lst < consdata->hmax )

9277 else if

( ect > consdata->hmin )

9302

leftbound = consdata->hmin - duration;

9303

rightbound = consdata->hmax;

9309

boundtuple[1] = (

)rightbound;

9347

assert(consdata !=

);

9353

capacity = consdata->capacity;

9355 for

( j = consdata->nvars-1; j >= 0 && !(*cutoff); --j )

9357 if

( consdata->demands[j] > capacity )

9394

assert(uplock ==

|| uplock ==

);

9395

assert((

int

)

== 1);

9396

assert((

int

)

== 0);

9413

assert(!infeasible);

9446

assert(downlock ==

|| downlock ==

);

9447

assert((

int

)

== 1);

9448

assert((

int

)

== 0);

9460

assert(!infeasible);

9487 if

( *capacity == 1 || nvars <= 1 )

9490

assert(demands[nvars-1] <= *capacity);

9491

assert(demands[nvars-2] <= *capacity);

9494

mindemand1 =

(demands[nvars-1], demands[nvars-2]);

9495

mindemand2 =

(demands[nvars-1], demands[nvars-2]);

9497 for

( v = nvars-2; v >= 0 && (gcd >= 2 || mindemand1 + mindemand2 > *capacity); --v )

9499

assert(mindemand1 <= mindemand2);

9500

assert(demands[v] <= *capacity);

9504 if

( mindemand1 > demands[v] )

9506

mindemand2 = mindemand1;

9507

mindemand1 = demands[v];

9509 else if

( mindemand2 > demands[v] )

9510

mindemand2 = demands[v];

9513 if

( mindemand1 + mindemand2 > *capacity )

9515 SCIPdebugMsg

(

"update cumulative condition (%d + %d > %d) to unary cumulative condition\n"

, mindemand1, mindemand2, *capacity);

9517 for

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

9522

(*nchgcoefs) += nvars;

9525 else if

( gcd >= 2 )

9529 for

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

9530

demands[v] /= (

int

) gcd;

9532

(*capacity) /= (int) gcd;

9534

(*nchgcoefs) += nvars;

9554

assert(nchgcoefs !=

);

9555

assert(nchgsides !=

);

9559

assert(consdata !=

);

9561 if

( consdata->normalized )

9564

capacity = consdata->capacity;

9570

consdata->normalized =

;

9572 if

( capacity > consdata->capacity )

9573

consdata->varbounds =

;

9629 for

( t = 0; t < ntimepoints; ++t )

9632 if

( timepoints[t] <= *hmin )

9636 if

( timepoints[t] >= *hmax )

9642 if

( loads[t] <= capacity )

9644

(*split) = timepoints[t];

9697

initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );

9726

assert(consdata !=

);

9728 if

( consdata->nvars <= 1 )

9732

consdata->durations, consdata->demands, consdata->capacity, &hmin, &hmax, &split) );

9735 if

( consdata->hmin < hmin )

9739

consdata->hmin = hmin;

9744 if

( consdata->hmax > hmax )

9747

consdata->hmax = hmax;

9752 if

( consdata->hmax <= consdata->hmin )

9754 SCIPdebugMsg

(

"constraint <%s> is redundant since hmax(%d) <= hmin(%d)\n"

9760 else if

( consdata->hmin < split && split < consdata->hmax )

9765 SCIPdebugMsg

(

"split cumulative constraint <%s>[%d,%d) with %d jobs at time point %d\n"

9766 SCIPconsGetName

(cons), consdata->hmin, consdata->hmax, consdata->nvars, split);

9768

assert(split < consdata->hmax);

9772

consdata->durations, consdata->demands, consdata->capacity, split, consdata->hmax,

9777

consdata->hmax = split;

9779

assert(consdata->hmin < consdata->hmax);

9857

assert(cons !=

);

9859 SCIPdebugMsg

(

"check for irrelevant variable for cumulative condition (hmin %d) w.r.t. earlier start time\n"

, hmin);

9861

firstminect = INT_MAX;

9862

secondminect = INT_MAX;

9865 for

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

9871 if

( ect < firstminect )

9873

secondminect = firstminect;

9876 else if

( ect < secondminect )

9881 for

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

9894

assert(var !=

);

9896

duration = durations[v];

9897

assert(duration > 0);

9903

ect = est + duration;

9905

lct = lst + duration;

9908 if

( ect == firstminect )

9909

minect = secondminect;

9911

minect = firstminect;

9914

alternativelb =

(hmin+1, minect);

9915

alternativelb =

(alternativelb, hmax);

9922 SCIPdebugMsg

(

" variable <%s>[%g,%g] with duration <%d> is irrelevant\n"

9926

irrelevants[v] =

;

9937

assert(downlocks !=

);

9938

assert(uplocks !=

);

9949 SCIPdebugMsg

(

" variables <%s>[%d,%d] (duration <%d>) is irrelevant due to no up lock\n"

9953

irrelevants[v] =

;

9961 SCIPdebugMsg

(

" remove down lock of variable <%s>[%g,%g] with duration <%d>\n"

9965

downlocks[v] =

;

9972 else if

( ect <= hmin )

9990 SCIPdebugMsg

(

" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt EST\n"

9997

irrelevants[v] =

;

10005

assert(downlocks !=

);

10020 if

( alternativelb > lst )

10026

assert(!infeasible);

10045

downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,

10046

nfixedvars, &success, cutoff) );

10057 SCIPdebugMsg

(

"********* check variable <%s>[%g,%g] with duration <%d> (hmin %d)\n"

10142

assert(cons !=

);

10144 SCIPdebugMsg

(

"check for irrelevant variable for cumulative condition (hmax %d) w.r.t. latest completion time\n"

, hmax);

10146

firstmaxlst = INT_MIN;

10147

secondmaxlst = INT_MIN;

10150 for

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

10156 if

( lst > firstmaxlst )

10158

secondmaxlst = firstmaxlst;

10161 else if

( lst > secondmaxlst )

10162

secondmaxlst = lst;

10166 for

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

10178

assert(var !=

);

10180

duration = durations[v];

10181

assert(duration > 0);

10187

ect = est + duration;

10191 if

( lst == firstmaxlst )

10192

maxlst = secondmaxlst;

10194

maxlst = firstmaxlst;

10197

alternativeub =

(hmax - 1, maxlst) - duration;

10198

alternativeub =

(alternativeub, hmin);

10205 SCIPdebugMsg

(

" variable <%s>[%g,%g] with duration <%d> is irrelevant\n"

10209

irrelevants[v] =

;

10216

assert(downlocks !=

);

10217

assert(uplocks !=

);

10223 if

( !downlocks[v] )

10229 SCIPdebugMsg

(

" variables <%s>[%d,%d] with duration <%d> is irrelevant due to no down lock\n"

10233

irrelevants[v] =

;

10241 SCIPdebugMsg

(

" remove up lock of variable <%s>[%g,%g] with duration <%d>\n"

10245

uplocks[v] =

;

10252 else if

( lst >= hmax )

10270 SCIPdebugMsg

(

" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt LCT\n"

10277

irrelevants[v] =

;

10285

assert(uplocks !=

);

10300 if

( alternativeub < est )

10306

assert(!infeasible);

10325

downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,

10326

nfixedvars, &success, cutoff) );

10368

assert(cons !=

);

10369

assert(!(*cutoff));

10372

assert(consdata !=

);

10374

nvars = consdata->nvars;

10384

consdata->hmin, consdata->hmax, consdata->downlocks, consdata->uplocks, cons,

10385

irrelevants, nfixedvars, nchgsides, cutoff) );

10389

consdata->hmin, consdata->hmax, consdata->downlocks, consdata->uplocks, cons,

10390

irrelevants, nfixedvars, nchgsides, cutoff) );

10395 for

( v = nvars-1; v >= 0; --v )

10397 if

( irrelevants[v] )

10403

var = consdata->vars[v];

10404

assert(var !=

);

10410 if

( lst <= consdata->hmin && ect >= consdata->hmax )

10412 if

( consdata->capacity < consdata->demands[v] )

10418

consdata->capacity -= consdata->demands[v];

10419

consdata->varbounds =

;

10437 int

* startindices,

10448

assert(demands !=

);

10449

assert(ndemands !=

);

10452

startindex = nstarted - 1;

10457 while

( nstarted - nfinished > ncountedvars )

10464

varidx = startindices[startindex];

10465

assert(varidx >= 0 && varidx < consdata->nvars);

10467

var = consdata->vars[varidx];

10468

assert(var !=

);

10473 if

( endtime > curtime )

10475 if

( consdata->demands[varidx] < consdata->capacity )

10477

(*demands)[*ndemands] = consdata->demands[varidx];

10494 int

* startindices,

10509

assert(nstarted > nfinished);

10512

assert(consdata !=

);

10513

assert(consdata->nvars > 0);

10514

assert(consdata->capacity > 0);

10520 collectDemands

(

, consdata, startindices, curtime, nstarted, nfinished, &demands, &ndemands);

10525 for

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

10562 int

* startindices;

10575

assert(cons !=

);

10576

assert(nchgsides !=

);

10579

assert(consdata !=

);

10581

nvars = consdata->nvars;

10584 if

( nvars <= 1 || consdata->capacity <= 1 )

10587

assert(consdata->vars !=

);

10589 SCIPdebugMsg

(

"try to tighten capacity for cumulative constraint <%s> with capacity %d\n"

10599

starttimes, endtimes, startindices, endindices,

);

10603

freecapacity = consdata->capacity;

10606 for

( j = 0; j < nvars && bestcapacity < consdata->capacity; ++j )

10608

curtime = starttimes[j];

10615 addEndingJobDemands

(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);

10617

assert(freecapacity <= consdata->capacity);

10618

assert(endindex <= nvars);

10624 if

( freecapacity < 0 )

10634

bestcapacity =

(bestcapacity, newcapacity);

10635 SCIPdebugMsg

(

"after highest cap usage: bestcapacity = %d\n"

, bestcapacity);

10639 if

( freecapacity > 0 && freecapacity != consdata->capacity )

10641

bestcapacity =

(bestcapacity, consdata->capacity - freecapacity);

10642 SCIPdebugMsg

(

"after peak < cap: bestcapacity = %d\n"

, bestcapacity);

10646 if

( freecapacity == 0 && consdata->demands[startindices[j]] < consdata->capacity)

10649 SCIPdebugMsg

(

"--> cannot decrease capacity since sum equals capacity\n"

);

10650

bestcapacity = consdata->capacity;

10662 if

( bestcapacity < consdata->capacity )

10664 SCIPdebug

(

int

oldnchgcoefs = *nchgcoefs; )

10666 SCIPdebugMsg

(

"+-+-+-+-+-+ --> CHANGE capacity of cons<%s> from %d to %d\n"

10669 for

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

10671 if

( consdata->demands[j] == consdata->capacity )

10673

consdata->demands[j] = bestcapacity;

10678

consdata->capacity = bestcapacity;

10683

consdata->varbounds =

;

10707

assert(cons !=

);

10708

assert(nchgcoefs !=

);

10712

assert(consdata !=

);

10714

nvars = consdata->nvars;

10715

oldnchgcoefs = *nchgcoefs;

10724

mindemand = consdata->demands[0];

10725 for

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

10727

mindemand =

(mindemand, consdata->demands[j]);

10731 for

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

10733 if

( mindemand + consdata->demands[j] > consdata->capacity && consdata->demands[j] < consdata->capacity )

10736

consdata->demands[j], consdata->capacity);

10737

consdata->demands[j] = consdata->capacity;

10746 for

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

10753

assert(consdata->demands[j] <= consdata->capacity);

10755 if

( consdata->demands[j] == consdata->capacity )

10763 for

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

10774 if

( est_i >= lct_j || est_j >= lct_i )

10777 if

( consdata->demands[j] + consdata->demands[i] <= consdata->capacity )

10787

consdata->demands[j], consdata->capacity);

10788

consdata->demands[j] = consdata->capacity;

10793 if

( (*nchgcoefs) > oldnchgcoefs )

10795 SCIPdebugMsg

(

"+-+-+-+-+-+changed %d coefficients of variables of cumulative constraint<%s>\n"

10802#ifdef SCIP_DISABLED_CODE 10820

assert(cons !=

);

10822

nvars = consdata->nvars;

10825

hmin = consdata->hmin;

10826

hmax = consdata->hmax;

10827

assert(hmin < hmax);

10829 for

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

10838

var = consdata->vars[v];

10839

assert(var !=

);

10841

duration = consdata->durations[v];

10844

ect = est + duration;

10846

lct = lst + duration;

10849

assert(lst > hmin || ect < hmax);

10851 if

( lst <= hmin && est < hmin - lct +

(hmin, ect) )

10860

shift = est - (hmin - lct +

(hmin, ect));

10863

duration = hmin - lct;

10874

assert(!infeasible);

10875

assert(!redundant);

10876

assert(aggregated);

10879

consdata->durations[v] = duration;

10880

consdata->vars[v] = aggrvar;

10915

assert(consdata !=

);

10917

capacity = consdata->capacity;

10919 if

( capacity == 1 )

10926

halfcapacity = capacity / 2;

10927

mindemand = consdata->capacity;

10931 for

( v = 0; v < consdata->nvars; ++v )

10933 if

( consdata->demands[v] > halfcapacity )

10935

vars[nvars] = consdata->vars[v];

10936

demands[nvars] = 1;

10937

durations[nvars] = consdata->durations[v];

10940

mindemand =

(mindemand, consdata->demands[v]);

10949 for

( v = 0; v < consdata->nvars; ++v )

10951 if

( consdata->demands[v] > halfcapacity )

10954 if

( mindemand + consdata->demands[v] > capacity )

10956

demands[nvars] = 1;

10957

durations[nvars] = consdata->durations[v];

10958

vars[nvars] = consdata->vars[v];

11031 if

( conshdlrdata->normalize )

11043 if

( conshdlrdata->coeftightening )

11054#ifdef SCIP_DISABLED_CODE 11068struct

TCLIQUE_Graph

11086

assert(tcliquegraph !=

);

11088 return

tcliquegraph->nnodes;

11095

assert(tcliquegraph !=

);

11097 return

tcliquegraph->weights;

11104

assert(tcliquegraph !=

);

11105

assert(0 <= node1 && node1 < tcliquegraph->

);

11106

assert(0 <= node2 && node2 < tcliquegraph->

);

11109 if

( tcliquegraph->precedencematrix[node1][node2] || tcliquegraph->precedencematrix[node2][node1] )

11113 if

( tcliquegraph->demandmatrix[node1][node2] )

11128

assert(tcliquegraph !=

);

11129

assert(0 <= node && node < tcliquegraph->

);

11131

assert(adjnodes !=

);

11135 for

( i = 0; i <

; i++ )

11138

assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);

11139

assert(i == 0 || nodes[i-1] < nodes[i]);

11142 if

( tcliqueIsedgeClique(tcliquegraph, node, nodes[i]) )

11145

adjnodes[nadjnodes] = nodes[i];

11191 bound

= (duration - vlbcoef) / (vlbcoef - 1.0);

11238

vlbcoef = 1.0 / vubcoef;

11239

vlbconst = -vubconst / vubcoef;

11257 if

( (*idx) == -1 )

11271 if

( tcliquegraph->size == tcliquegraph->nnodes )

11276

tcliquegraph->size = size;

11284 for

( v = 0; v < tcliquegraph->nnodes; ++v )

11290

assert(tcliquegraph->nnodes < tcliquegraph->size);

11292

pos = tcliquegraph->nnodes;

11295

tcliquegraph->durations[pos] = 0;

11296

tcliquegraph->weights[pos] = 0;

11297

tcliquegraph->vars[pos] = var;

11307

tcliquegraph->nnodes++;

11309 for

( v = 0; v < tcliquegraph->nnodes; ++v )

11311

tcliquegraph->precedencematrix[v][pos] = 0;

11312

tcliquegraph->demandmatrix[v][pos] = 0;

11315

(*idx) = tcliquegraph->nnodes;

11352 for

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

11363

assert(var !=

);

11368 if

( tcliquegraph->durations[idx1] == 0 )

11376 for

(

= 0;

< nvbdvars; ++

)

11383 if

( tcliquegraph->durations[idx2] == 0 )

11387

tcliquegraph->precedencematrix[idx2][idx1] =

;

11395 for

(

= 0;

< nvbdvars; ++

)

11402 if

( tcliquegraph->durations[idx2] == 0 )

11406

tcliquegraph->precedencematrix[idx1][idx2] =

;

11409 for

(

= v+1;

< nvars; ++

)

11416 if

( tcliquegraph->durations[idx2] == 0 )

11421

tcliquegraph->precedencematrix[idx1][idx2] =

;

11425

tcliquegraph->precedencematrix[idx2][idx1] =

;

11445 for

( i = 0; i <

; ++i )

11447 for

( j = 0; j <

; ++j )

11449 if

( adjmatrix[i][j] )

11454 for

( k = 0; k <

; ++k )

11456 if

( adjmatrix[j][k] )

11457

adjmatrix[i][k] =

;

11476 for

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

11486

assert(consdata !=

);

11488

vars = consdata->vars;

11489

demands = consdata->demands;

11491

nvars = consdata->nvars;

11492

capacity = consdata->capacity;

11497 for

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

11505 if

( tcliquegraph->durations[idx1] == 0 || tcliquegraph->durations[idx1] > consdata->durations[i] )

11508 for

( j = i+1; j < nvars; ++j )

11510

assert(consdata->durations[j] > 0);

11512 if

( demands[i] + demands[j] > capacity )

11525 if

( est1 < consdata->hmin && est2 < consdata->hmin )

11532 if

( lct1 > consdata->hmax && lct2 > consdata->hmax )

11537

assert(idx1 != idx2);

11539 if

( tcliquegraph->durations[idx2] == 0 || tcliquegraph->durations[idx2] > consdata->durations[j] )

11544

assert(tcliquegraph->durations[idx1] > 0);

11545

assert(tcliquegraph->durations[idx2] > 0);

11547

tcliquegraph->demandmatrix[idx1][idx2] =

;

11548

tcliquegraph->demandmatrix[idx2][idx1] =

;

11569

assert(tcliquegraph !=

);

11575 transitiveClosure

(tcliquegraph->precedencematrix, tcliquegraph->ninarcs, tcliquegraph->noutarcs, tcliquegraph->nnodes);

11606 for

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

11608

durations[v] = tcliquegraph->durations[cliquenodes[v]];

11609

assert(durations[v] > 0);

11611

vars[v] = tcliquegraph->vars[cliquenodes[v]];

11651 nnodes

= tcliquegraph->nnodes;

11655 for

( v = 0; v <

; ++v )

11657

tcliquegraph->weights[v] = tcliquegraph->durations[v];

11668

SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,

) );

11677 if

( tcliquegraph->durations[v] == 0 )

11687 for

( c = 0; c <

; ++c )

11689

precedencerow[c] = tcliquegraph->precedencematrix[v][c];

11690

precedencecol[c] = tcliquegraph->precedencematrix[c][v];

11692

demandrow[c] = tcliquegraph->demandmatrix[v][c];

11693

demandcol[c] = tcliquegraph->demandmatrix[c][v];

11695

tcliquegraph->precedencematrix[c][v] =

;

11696

tcliquegraph->precedencematrix[v][c] =

;

11700 tcliqueMaxClique

(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,

11701

tcliquegraph, tcliqueNewsolClique,

11702

cliquenodes, &ncliquenodes, &cliqueweight, 1, 1,

11703

10000, 1000, 1000, v, &ntreenodes, &tcliquestatus);

11705 SCIPdebugMsg

(

"tree nodes %d clique size %d (weight %d, status %d)\n"

, ntreenodes, ncliquenodes, cliqueweight, tcliquestatus);

11707 if

( ncliquenodes == 1 )

11717 for

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

11723 for

( c = 0; c <

; ++c )

11725

tcliquegraph->precedencematrix[v][c] = precedencerow[c];

11726

tcliquegraph->precedencematrix[c][v] = precedencecol[c];

11728

tcliquegraph->demandmatrix[v][c] = demandrow[c];

11729

tcliquegraph->demandmatrix[c][v] = demandcol[c];

11741

(*naddconss) += nconss;

11797 if

( !tcliquegraph->precedencematrix[source][sink] )

11800 nnodes

= tcliquegraph->nnodes;

11801

vars = tcliquegraph->vars;

11811 for

( i = 0; i <

; ++i )

11817

assert(var !=

);

11819

duration = tcliquegraph->durations[i];

11821 if

( i == source || i == sink )

11824

tcliquegraph->weights[i] = 0;

11826 else if

( tcliquegraph->precedencematrix[source][i] && tcliquegraph->precedencematrix[i][sink] )

11829

tcliquegraph->weights[i] = duration;

11835

tcliquegraph->weights[i] = duration;

11838

tcliquegraph->weights[i] = 0;

11844 tcliqueMaxClique

(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,

11845

tcliquegraph, tcliqueNewsolClique,

11846

cliquenodes, &ncliquenodes, &cliqueweight, 1, 1,

11847

10000, 1000, 1000, -1, &ntreenodes, &tcliquestatus);

11849 if

( ncliquenodes > 1 )

11860

distance = cliqueweight + tcliquegraph->durations[source];

11891 nnodes

= tcliquegraph->nnodes;

11901 for

( i = 0; i <

; ++i )

11903 if

( tcliquegraph->ninarcs[i] == 0 )

11905

sources[nsources] = i;

11909 if

( tcliquegraph->ninarcs[i] == 0 )

11932

(*naddconss) += nconss;

11955 for

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

11963

assert(consdata !=

);

11965

vars = consdata->vars;

11966

nvars = consdata->nvars;

11968 for

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

11979

tcliquegraph->durations[idx] =

(tcliquegraph->durations[idx], consdata->durations[v]);

11980

assert(tcliquegraph->durations[idx] > 0);

12037 for

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

12042

assert(var !=

);

12055

(*tcliquegraph)->nnodes = nvars;

12056

(*tcliquegraph)->varmap = varmap;

12057

(*tcliquegraph)->precedencematrix = precedencematrix;

12058

(*tcliquegraph)->demandmatrix = demandmatrix;

12059

(*tcliquegraph)->weights = weights;

12060

(*tcliquegraph)->ninarcs = ninarcs;

12061

(*tcliquegraph)->noutarcs = noutarcs;

12062

(*tcliquegraph)->durations = durations;

12063

(*tcliquegraph)->size = nvars;

12077 for

( v = (*tcliquegraph)->nnodes-1; v >= 0; --v )

12119 if

( conshdlrdata->detectvarbounds )

12125 if

( conshdlrdata->detectdisjunctive )

12146 if

( consdata->validsignature )

12149

vars = consdata->vars;

12150

nvars = consdata->nvars;

12152 for

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

12154

consdata->signature |= ((

unsigned

int)1 << ((

unsigned int

)

SCIPvarGetIndex

(vars[v]) % (

sizeof

(

unsigned

int) * 8)));

12157

consdata->validsignature =

;

12166

assert(consdata !=

);

12167

assert(0 <= ind1 && ind1 < consdata->nvars);

12168

assert(0 <= ind2 && ind2 < consdata->nvars);

12170 return SCIPvarCompare

(consdata->vars[ind1], consdata->vars[ind2]);

12185 for

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

12191

assert(cons0 !=

);

12194

assert(consdata0 !=

);

12197

assert(consdata0->validsignature);

12199 for

( j = i+1; j < nconss; ++j )

12205

assert(cons1 !=

);

12208

assert(consdata1 !=

);

12210 if

( consdata0->capacity != consdata1->capacity )

12214

assert(consdata1->validsignature);

12216 if

( (consdata1->signature & (~consdata0->signature)) == 0 )

12220

assert((consdata0->signature & (~consdata1->signature)) == 0);

12223 if

( (consdata0->signature & (~consdata1->signature)) == 0 )

12230 if

( consdata0->nvars > consdata1->nvars )

12233 if

( consdata0->hmin < consdata1->hmin )

12236 if

( consdata0->hmax > consdata1->hmax )

12243 SCIPsort

(perm0, consdataCompVar, (

void

*)consdata0, consdata0->nvars);

12244 SCIPsort

(perm1, consdataCompVar, (

void

*)consdata1, consdata1->nvars);

12246 for

( v0 = 0, v1 = 0; v0 < consdata0->nvars && v1 < consdata1->nvars; )

12257

var0 = consdata0->vars[idx0];

12259

var1 = consdata1->vars[idx1];

12270

demand0 = consdata0->demands[idx0];

12271

duration0 = consdata0->durations[idx0];

12273

demand1 = consdata1->demands[idx1];

12274

duration1 = consdata1->durations[idx1];

12276 if

( demand0 != demand1 )

12279 if

( duration0 != duration1 )

12285 else if

( comp > 0 )

12291 if

( v0 == consdata0->nvars )

12333

assert(consdata !=

);

12336 if

( consdata->varbounds )

12339

vars = consdata->vars;

12340

durations = consdata->durations;

12341

demands = consdata->demands;

12342

capacity = consdata->capacity;

12343

nvars = consdata->nvars;

12357

var = consdata->vars[i];

12358

assert(var !=

);

12365 for

(

= 0;

< nvbdvars; ++

)

12371 for

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

12373 if

( vars[j] == vbdvars[

] )

12394

assert(!infeasible);

12396

(*nchgbds) += nlocalbdchgs;

12403

(*naddconss) += nconss;

12405

consdata->varbounds =

;

12425

assert(conshdlr !=

);

12427

assert(nconss == 0 || conss !=

);

12428

assert(result !=

);

12430 if

( solinfeasible )

12436 SCIPdebugMsg

(

"constraint enforcing %d useful cumulative constraints of %d constraints for %s solution\n"

, nusefulconss, nconss,

12437

sol ==

"LP"

"relaxation"

);

12440

assert(conshdlrdata !=

);

12444 if

( conshdlrdata->usebinvars )

12450

separated =

;

12453 for

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

12459

assert(cons !=

);

12474 for

( ; c < nconss && !separated; ++c )

12480

assert(cons !=

);

12519

assert(conshdlr !=

);

12538

assert(conshdlr !=

);

12542

assert(conshdlrdata !=

);

12544#ifdef SCIP_STATISTIC 12545 if

( !conshdlrdata->iscopy )

12549

conshdlrdata->nlbtimetable, conshdlrdata->nubtimetable, conshdlrdata->ncutofftimetable);

12551

conshdlrdata->nlbedgefinder, conshdlrdata->nubedgefinder, conshdlrdata->ncutoffedgefinder);

12553

conshdlrdata->ncutoffoverload, conshdlrdata->ncutoffoverloadTTEF);

12573

assert(conshdlrdata !=

);

12575

conshdlrdata->detectedredundant =

;

12577 for

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

12590#ifdef SCIP_STATISTIC 12598

assert(conshdlrdata !=

);

12600 for

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

12604#ifdef SCIP_DISABLED_CODE 12609 if

( !conshdlrdata->iscopy )

12611 SCIPstatisticPrintf

(

"@11 added variables bounds constraints %d\n"

, conshdlrdata->naddedvarbounds);

12612 SCIPstatisticPrintf

(

"@22 added disjunctive constraints %d\n"

, conshdlrdata->naddeddisjunctives);

12634

assert(conshdlr !=

);

12638 for

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

12641

assert(consdata !=

);

12654

assert(conshdlr !=

);

12656

assert(consdata !=

);

12657

assert(*consdata !=

);

12665

assert(conshdlrdata !=

);

12684

assert(conshdlr !=

);

12686

assert(sourcecons !=

);

12687

assert(targetcons !=

);

12690

assert(sourcedata !=

);

12691

assert(sourcedata->demandrows ==

);

12697

assert(conshdlrdata !=

);

12698

assert(conshdlrdata->eventhdlr !=

);

12702

sourcedata->durations, sourcedata->demands, sourcedata->nvars, sourcedata->capacity,

12726

assert(conshdlr !=

);

12728

assert(conshdlrdata !=

);

12730

*infeasible =

;

12732 SCIPdebugMsg

(

"initialize LP relaxation for %d cumulative constraints\n"

, nconss);

12734 if

( conshdlrdata->usebinvars )

12737 for

( c = 0; c < nconss && !(*infeasible); ++c )

12742 if

( conshdlrdata->cutsasconss )

12766

assert(conshdlr !=

);

12768

assert(nconss == 0 || conss !=

);

12769

assert(result !=

);

12771

assert(conshdlrdata !=

);

12773 SCIPdebugMsg

(

"separating %d/%d cumulative constraints\n"

, nusefulconss, nconss);

12776

separated =

;

12784 if

( conshdlrdata->usebinvars )

12787 for

( c = 0; c < nusefulconss && !cutoff; ++c )

12792 if

( !cutoff && conshdlrdata->usecovercuts )

12794 for

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

12801 if

( conshdlrdata->sepaold )

12804 for

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

12813 else if

( separated )

12828

assert(conshdlr !=

);

12830

assert(nconss == 0 || conss !=

);

12831

assert(result !=

);

12834

assert(conshdlrdata !=

);

12839 SCIPdebugMsg

(

"separating %d/%d cumulative constraints\n"

, nusefulconss, nconss);

12842

separated =

;

12845 if

( conshdlrdata->usebinvars )

12848 for

( c = 0; c < nusefulconss && !cutoff; ++c )

12853 if

( !cutoff && conshdlrdata->usecovercuts )

12855 for

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

12861 if

( conshdlrdata->sepaold )

12864 for

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

12873 else if

( separated )

12905

assert(conshdlr !=

);

12907

assert(nconss == 0 || conss !=

);

12908

assert(result !=

);

12910 if

( objinfeasible )

12919

assert(conshdlrdata !=

);

12932

assert(conshdlr !=

);

12934

assert(nconss == 0 || conss !=

);

12935

assert(result !=

);

12941 for

( c = 0; c < nconss && (*result ==

SCIP_FEASIBLE

|| completely); ++c )

12964 SCIPdebugMsg

(

"propagate %d of %d useful cumulative constraints\n"

, nusefulconss, nconss);

12966

assert(conshdlr !=

);

12968

assert(nconss == 0 || conss !=

);

12969

assert(result !=

);

12972

assert(conshdlrdata !=

);

12980 for

( c = 0; c < nusefulconss && !cutoff; ++c )

12985

assert(cons !=

);

12990

&nchgbds, &nchgbds, &ndelconss, &nchgbds, &nchgbds, &nchgbds, &cutoff, &cutoff) );

13002 if

( !cutoff && nchgbds == 0 )

13005 for

( c = nusefulconss; c < nconss && !cutoff; ++c )

13016 else if

( nchgbds > 0 )

13018 SCIPdebugMsg

(

"delete (locally) %d constraints and changed %d variable bounds\n"

, ndelconss, nchgbds);

13044

assert(conshdlr !=

);

13047

assert(result !=

);

13052

assert(conshdlrdata !=

);

13056

oldnfixedvars = *nfixedvars;

13057

oldnchgbds = *nchgbds;

13058

oldnchgsides = *nchgsides;

13059

oldnchgcoefs = *nchgcoefs;

13060

oldnupgdconss = *nupgdconss;

13061

oldndelconss = *ndelconss;

13062

oldnaddconss = *naddconss;

13064

unbounded =

;

13067 for

( c = 0; c < nconss && !cutoff; ++c )

13079

nfixedvars, nchgbds, ndelconss, naddconss, nchgcoefs, nchgsides, &cutoff, &unbounded) );

13081 if

( cutoff || unbounded )

13089 if

( nrounds == 1 &&

SCIPgetNRuns

(

) == 1 && conshdlrdata->disjunctive )

13111 if

( !cutoff &&

SCIPgetNRuns

(

) == 1 && !conshdlrdata->detectedredundant

13112

&& (conshdlrdata->detectvarbounds || conshdlrdata->detectdisjunctive)

13119

conshdlrdata->detectedredundant =

;

13127 SCIPdebugMsg

(

"delete %d constraints and changed %d variable bounds (cutoff %u)\n"

13128

*ndelconss - oldndelconss, *nchgbds - oldnchgbds, cutoff);

13132 else if

( unbounded )

13134 else if

( *nchgbds > oldnchgbds || *nfixedvars > oldnfixedvars || *nchgsides > oldnchgsides

13135

|| *nchgcoefs > oldnchgcoefs || *nupgdconss > oldnupgdconss || *ndelconss > oldndelconss || *naddconss > oldnaddconss )

13150

assert(conshdlr !=

);

13153

assert(result !=

);

13154

assert(infervar !=

);

13155

assert(bdchgidx !=

);

13158

assert(conshdlrdata !=

);

13161

assert(cons !=

);

13164

assert(consdata !=

);

13166 SCIPdebugMsg

(

"resolve propagation: variable <%s>, cumulative constraint <%s> (capacity %d, propagation %d, H=[%d,%d))\n"

13171

consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,

13172

infervar,

intToInferInfo

(inferinfo), boundtype, bdchgidx, relaxedbd, conshdlrdata->usebdwidening,

, result) );

13188

assert(cons !=

);

13192

assert(consdata !=

);

13194

vars = consdata->vars;

13195

assert(vars !=

);

13197 for

( v = 0; v < consdata->nvars; ++v )

13199 if

( consdata->downlocks[v] && consdata->uplocks[v] )

13204 else if

( consdata->downlocks[v] )

13208 else if

( consdata->uplocks[v] )

13223

assert(conshdlr !=

);

13224

assert(cons !=

);

13238 const char

* consname;

13244

assert(sourceconsdata !=

);

13247

nvars = sourceconsdata->nvars;

13248

sourcevars = sourceconsdata->vars;

13258 for

( v = 0; v < nvars && *valid; ++v )

13261

assert(!(*valid) || vars[v] !=

);

13267 if

( name !=

)

13274

sourceconsdata->durations, sourceconsdata->demands, sourceconsdata->capacity,

13275

initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );

13278 if

( sourceconsdata->hmin > 0 )

13284 if

( sourceconsdata->hmax < INT_MAX )

13338

endptr = strchr(endptr,

')'

);

13340 if

( endptr ==

)

13350

duration = atoi(strvalue);

13354

demand = atoi(strvalue);

13360

demands[nvars] = demand;

13361

durations[nvars] = duration;

13364 while

( *str !=

')'

);

13370

hmin = atoi(strvalue);

13375

hmax = (int)(value);

13383

capacity = (int)value;

13387

initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );

13411

assert(consdata !=

);

13413 if

( varssize < consdata->nvars )

13414

(*success) =

;

13417

assert(vars !=

);

13420

(*success) =

;

13433

assert(consdata !=

);

13435

(*nvars) = consdata->nvars;

13436

(*success) =

;

13456

assert(eventhdlr !=

);

13457

assert(eventdata !=

);

13459

assert(event !=

);

13462

assert(consdata !=

);

13465

consdata->propagated =

;

13494

consEnfolpCumulative, consEnfopsCumulative, consCheckCumulative, consLockCumulative,

13497

assert(conshdlr !=

);

13502#ifdef SCIP_STATISTIC 13526 "should time-table (core-times) propagator be used to infer bounds?"

13530 "should edge-finding be used to detect an overload?"

13534 "should edge-finding be used to infer bounds?"

13537 "constraints/" CONSHDLR_NAME "/useadjustedjobs"

"should edge-finding be executed?"

13541 "should time-table edge-finding be used to detect an overload?"

13545 "should time-table edge-finding be used to infer bounds?"

13549 "constraints/" CONSHDLR_NAME "/usebinvars"

"should the binary representation be used?"

13552 "constraints/" CONSHDLR_NAME "/localcuts"

"should cuts be added only locally?"

13555 "constraints/" CONSHDLR_NAME "/usecovercuts"

"should covering cuts be added every node?"

13559 "should the cumulative constraint create cuts as knapsack constraints?"

13563 "shall old sepa algo be applied?"

13567 "constraints/" CONSHDLR_NAME "/fillbranchcands"

"should branching candidates be added to storage?"

13572 "constraints/" CONSHDLR_NAME "/dualpresolve"

"should dual presolving be applied?"

13575 "constraints/" CONSHDLR_NAME "/coeftightening"

"should coefficient tightening be applied?"

13578 "constraints/" CONSHDLR_NAME "/normalize"

"should demands and capacity be normalized?"

13582 "should pairwise constraint comparison be performed in presolving?"

13585 "constraints/" CONSHDLR_NAME "/disjunctive"

"extract disjunctive constraints?"

13590 "number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)?"

13593 "constraints/" CONSHDLR_NAME "/detectdisjunctive"

"search for conflict set via maximal cliques to detect disjunctive constraints"

13596 "constraints/" CONSHDLR_NAME "/detectvarbounds"

"search for conflict set via maximal cliques to detect variable bound constraints"

13601 "constraints/" CONSHDLR_NAME "/usebdwidening"

"should bound widening be used during the conflict analysis?"

13649 if

( conshdlr ==

)

13655 SCIPdebugMsg

(

"create cumulative constraint <%s> with %d jobs\n"

, name, nvars);

13658 SCIP_CALL

(

consdataCreate

(

, &consdata, vars,

, durations, demands, nvars, capacity, 0, INT_MAX, check) );

13662

initial, separate, enforce, check, propagate,

13663

local, modifiable, dynamic, removable, stickingatnode) );

13671

assert(conshdlrdata !=

);

13672

assert(conshdlrdata->eventhdlr !=

);

13723

assert(consdata !=

);

13725

assert(hmin <= consdata->hmax);

13727

consdata->hmin = hmin;

13747

assert(consdata !=

);

13749 return

consdata->hmin;

13768

assert(consdata !=

);

13769

assert(hmax >= consdata->hmin);

13771

consdata->hmax = hmax;

13791

assert(consdata !=

);

13793 return

consdata->hmax;

13812

assert(consdata !=

);

13814 return

consdata->vars;

13833

assert(consdata !=

);

13835 return

consdata->nvars;

13854

assert(consdata !=

);

13856 return

consdata->capacity;

13875

assert(consdata !=

);

13877 return

consdata->durations;

13896

assert(consdata !=

);

13898 return

consdata->demands;

13920

assert(violated !=

);

13923

violated, cons, printreason) );

13959

hmin, hmax, split) );

13986

irrelevants, nfixedvars, nchgsides, cutoff) );

13990

irrelevants, nfixedvars, nchgsides, cutoff) );

14018

assert(cons !=

);

14019

assert(initialized !=

);

14020

assert(*initialized ==

);

14021

assert(cutoff !=

);

14022

assert(*cutoff ==

);

14026 if

( conshdlr ==

)

14033

assert(conshdlrdata !=

);

14035

redundant =

;

14038

nvars, vars, durations, demands, capacity, hmin, hmax, cons,

14039

nchgbds, &redundant, initialized, explanation, cutoff) );

14064

infervar,

intToInferInfo

(inferinfo), boundtype, bdchgidx, relaxedbd,

, explanation, result) );

14087

file = fopen(filename,

"w"

);

14090 if

( file ==

)

14098

assert(consdata !=

);

14100

nvars = consdata->nvars;

14103

SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,

), TERMINATE );

14108 for

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

14112

var = consdata->vars[v];

14113

assert(var !=

);

14119 else if

( !consdata->downlocks[v] || !consdata->uplocks[v] )

14127 for

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

14133

var = consdata->vars[v];

14134

assert(var !=

);

14139 for

(

= 0;

< nvbdvars; ++

)

14147#ifdef SCIP_MORE_OUTPUT 14152 for

(

= 0;

< nvbdvars; ++

)

14184 if

( conshdlr ==

)

14191

assert(conshdlrdata !=

);

14228

(*infeasible) =

;

14229

(*unbounded) =

;

14237 if

( conshdlr ==

)

14245

assert(conshdlrdata !=

);

14248 if

( timelimit > 0.0 && memorylimit > 10 )

14250 SCIP_CALL

( conshdlrdata->solveCumulative(njobs, ests, lsts, objvals, durations, demands, capacity,

14251

hmin, hmax, timelimit, memorylimit, maxnodes, solved, infeasible, unbounded, error) );

14287 for

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

14289

copydemands[v] = demands[v];

14295 for

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

14300

assert(idx >= 0 && idx < nvars);

14303

assert(var !=