[SCIP] Problem with disjunct of conjuncts with variable dependency

[Levinson, Richard J. (ARC-TI)[SGT, INC]]

I have verified that I am calling SCIPgetBestSol() but still not getting the optimal solution. I am using SCIP opt suite 3.2.1 and you mentioned you got different results with SCIP 4.0.  Should I update to 4.0?

- Rich
________________________________________
From: Scip [scip-bounces at zib.de] on behalf of Ambros Gleixner [gleixner at zib.de]
Sent: Saturday, April 08, 2017 4:46 AM
To: scip at zib.de
Subject: Re: [SCIP] Problem with disjunct of conjuncts with variable dependency

Hi Richard,

My first guess would be that you are accessing all solutions found by
SCIP during the solving process and thereby also inspect suboptimal
solutions.  For these it must not hold that A is scheduled as early as
possible.  So make sure you only access the best solution via
SCIPgetBestSol(), which is optimal unless you hit some limits on gap,
running time, nodes, etc.

If I solve the CIP you sent with SCIP 4.0 then I get an optimal solution
with objective function value 61, which has A = 25 as expected.

The first feasible solution that SCIP finds during the solving process
has objective value 71.  This is probably the one you reported in your
e-mail.  This is produced by the "trivial" heuristic, and by the name
you might already guess that it doesn't do anything too fancy.  But in
general it helps to have such suboptimal solutions early to reach the
optimal one quicker.

Happy SCIPing,
Ambros







On 08.04.2017 00:02, Levinson, Richard J. (ARC-TI)[SGT, INC] wrote:
> 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
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>

--
Ambros Gleixner, Zuse Institute Berlin, http://www.zib.de/gleixner
_______________________________________________
Scip mailing list
Scip at zib.de
https://listserv.zib.de/mailman/listinfo/scip