[SCIP] Problem with disjunct of conjuncts with variable dependency

Sat Apr 8 00:02:24 CEST 2017

Hello,

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.

Scenario:
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.

SCIP problem printout is shown below but here's the story:

I have a disjunct constraint that says "A must start AND stop within window 1" OR "A must start and stop within window 2".

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.

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.  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.

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.  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.

Here are the SCIP printouts of the original and transformed problems. I made these printouts just now at 04/07/2017 02:10:09 PM. I am using the C-API with default plugins and I do not have any other plugins.

ORIGINAL PROBLEM:

<t_A>[I]STATISTICS

  Problem name     : MIP

  Variables        : 3 (1 binary, 2 integer, 0 implicit integer, 0 continuous)

  Constraints      : 2 initial, 2 maximal

OBJECTIVE

  Sense            : minimize

VARIABLES

  [binary] <one>: obj=1, original bounds=[1,1]

  [integer] <A>: obj=1, original bounds=[6,40]

  [integer] <Aend>: obj=1, original bounds=[6,40]

CONSTRAINTS

  [linear] <Aend=start+duration_cons>: <A>[I] +10<one>[B] -<Aend>[I] == 0;

  [disjunction] <Awindow-disjunction>: disjunction(

[conjunction] <AisInW0conjunction>: conjunction(

[linear] <AstartsInW0>: 6 <= <A>[I] <= 12,

[linear] <AendsInw0>: 6 <= <Aend>[I] <= 12),

[conjunction] <AisInW1conjunction>: conjunction(

[linear] <AstartsInW1>: 25 <= <A>[I] <= 40,

  [linear] <AendsInw1>: 25 <= <Aend>[I] <= 40));

END

--------------------------------

TRANSFORMED PROBLEM:

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):

STATISTICS

  Problem name     : t_MIP

  Variables        : 1 (0 binary, 1 integer, 0 implicit integer, 0 continuous)

  Constraints      : 1 initial, 3 maximal

OBJECTIVE

  Sense            : minimize

  Offset           : -4.5

  Scale            : 2

VARIABLES

  [integer] <t_Aend>: obj=1, global bounds=[16,22], local bounds=[16,22]

FIXED

  [binary] <t_one>: obj=0, global bounds=[1,1], local bounds=[1,1], fixed:1

  [integer] <t_A>: obj=0, global bounds=[6,12], local bounds=[6,12], aggregated: -10 +1<t_Aend>

CONSTRAINTS

  [linear] <AstartsInW1>: 35 <= <t_Aend>[I] <= 50;

  [linear] <AendsInw1>: 25 <= <t_Aend>[I] <= 40;

END

MIPSolver.printAllSolutions() 10

objective value:                                   71

one                                                 1 (obj:1)

A                                                  30 (obj:1)

Aend                                               40 (obj:1)

ORIGINAL: 71

TRNSFRMD: 40

Thank you for any feedback you may have.

- Rich
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170407/c7c4eb6a/attachment.html>