<html dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" id="owaParaStyle"></style>
</head>
<body fpstyle="1" ocsi="0">
<div style="direction: ltr;font-family: Tahoma;color: #000000;font-size: 10pt;">Hello,
<div><br>
</div>
<div>
<div>I am having difficulty with a disjunct of conjuncts where one of the conjuncts has an inferred variable End which should be dependent on another variable Start but it seems to get the dependencies backward, and pins down End and then infers Start from
that. </div>
<div><br>
</div>
<div>Scenario:</div>
<div>I want to schedule a Job A to start at a time between 6 and 40, but it must start and end within one of two time windows [6,12] or [25,40]. If A duration <= 6 then it should fit into window 1, but when duration > 6, it must schedule it in the second time
window. I expect it to schedule it to start at 25 (the earliest time in window 2) but it doesn't. </div>
<div><br>
</div>
<div>SCIP problem printout is shown below but here's the story:</div>
<div><br>
</div>
<div>I have a disjunct constraint that says "A must start AND stop within window 1" OR "A must start and stop within window 2". </div>
<div><br>
</div>
<div><span style="font-size: 10pt;">I have a constraint to enforce that the end time of A = the start time of A + the duration of A. Assuming A is the start time for Job A, then A_end = A + A_duration. </span></div>
<div><span style="font-size: 10pt;"><br>
</span></div>
<div><span style="font-size: 10pt;">The problem is that that SCIP seems to always assign A_end to its upper bound and then inferring A (start time), but I need it to do the opposite: solve for A and then inferr A_end from that. </span><span style="font-size: 10pt;">So
if the valid time window for A is [20,40] and A duration is 10, then it produces solution A=30 (A = A_end - 10), but I want it to set A = 20 and infer A_end = 20 + 10. </span></div>
<div><br>
</div>
<div>If I initialize A_end with upper bound of 100, then SCIP fails to find a solution at all because it infers A =100-10 = 90 which is not a valid window for A. <span style="font-size: 10pt;">When I set A_end upper bound to 40 (same as A_start), then it sets
A = 30 = 40 -10. When I set A_end upper bound to 35, then it sets A = 25 = 35 - 10. </span></div>
<div><br>
</div>
<div>Here are the SCIP printouts of the original and transformed problems. I made these printouts just now at<font size="2"> 04/07/2017 02:10:09 PM. I am using the C-API with default plugins and I do not have any other plugins.</font></div>
<div><font face="Menlo"><span style="font-size: 11px;"><br>
</span></font></div>
<div>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
ORIGINAL PROBLEM:</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;">
<br>
</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<t_A>[I]STATISTICS</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Problem name : MIP</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Variables : 3 (1 binary, 2 integer, 0 implicit integer, 0 continuous)</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Constraints : 2 initial, 2 maximal</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
OBJECTIVE</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Sense : minimize</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
VARIABLES</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[binary] <one>: obj=1, original bounds=[1,1]</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[integer] <A>: obj=1, original bounds=[6,40]</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[integer] <Aend>: obj=1, original bounds=[6,40]</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
CONSTRAINTS</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[linear] <Aend=start+duration_cons>: <A>[I] +10<one>[B] -<Aend>[I] == 0;</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[disjunction] <Awindow-disjunction>: disjunction( </p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<span class="Apple-tab-span" style="white-space: pre;"></span><span class="Apple-tab-span" style="white-space:pre"></span>[conjunction] <AisInW0conjunction>: conjunction( </p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<span class="Apple-tab-span" style="white-space: pre;"></span><span class="Apple-tab-span" style="white-space:pre"></span>[linear] <AstartsInW0>: 6 <= <A>[I] <= 12, </p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<span class="Apple-tab-span" style="white-space: pre;"></span><span class="Apple-tab-span" style="white-space:pre"></span>[linear] <AendsInw0>: 6 <= <Aend>[I] <= 12), </p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<span class="Apple-tab-span" style="white-space:pre"></span>[conjunction] <AisInW1conjunction>: conjunction( </p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<span class="Apple-tab-span" style="white-space:pre"></span>[linear] <AstartsInW1>: 25 <= <A>[I] <= 40, </p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<span class="Apple-tab-span" style="white-space:pre"></span> <span class="Apple-tab-span" style="white-space:pre">
</span>[linear] <AendsInw1>: 25 <= <Aend>[I] <= 40));</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
END</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
--------------------------------</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<br>
</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
TRANSFORMED PROBLEM:</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Here is the transformed problem and solution below.Notice that it shows A as fixed and Aend as variable and that the transformed constraints only include Aend (no mention of A start time in the constraints at all):</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
<br>
</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
STATISTICS</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Problem name : t_MIP</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Variables : 1 (0 binary, 1 integer, 0 implicit integer, 0 continuous)</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Constraints : 1 initial, 3 maximal</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
OBJECTIVE</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Sense : minimize</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Offset : -4.5</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Scale : 2</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
VARIABLES</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[integer] <t_Aend>: obj=1, global bounds=[16,22], local bounds=[16,22]</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
FIXED</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[binary] <t_one>: obj=0, global bounds=[1,1], local bounds=[1,1], fixed:1</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[integer] <t_A>: obj=0, global bounds=[6,12], local bounds=[6,12], aggregated: -10 +1<t_Aend></p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
CONSTRAINTS</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[linear] <AstartsInW1>: 35 <= <t_Aend>[I] <= 50;</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
[linear] <AendsInw1>: 25 <= <t_Aend>[I] <= 40;</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
END</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;">
</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
MIPSolver.printAllSolutions() 10</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
objective value: 71</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
one 1 <span class="Apple-tab-span" style="white-space: pre;"></span>(obj:1)</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
A 30 <span class="Apple-tab-span" style="white-space: pre;"></span>(obj:1)</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
Aend 40 <span class="Apple-tab-span" style="white-space: pre;"></span>(obj:1)</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
ORIGINAL: 71</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
</p>
<p style="margin-right: 0px; margin-left: 0px; font-size: 11px; line-height: normal; font-family: Menlo;">
TRNSFRMD: 40</p>
</div>
</div>
<div><br>
</div>
<div>Thank you for any feedback you may have.</div>
<div><br>
</div>
<div>- Rich</div>
</div>
</body>
</html>