[SCIP] Problem with disjunct of conjuncts with variable dependency
Levinson, Richard J. (ARC-TI)[SGT, INC]
richard.j.levinson at nasa.gov
Wed Apr 12 02:25:18 CEST 2017
Hello Gerald,
Indeed SCIP does find the right solution using the interactive shell (as you found) but it fails when I run it through the C-API with default plugins. Seems like the C-API is stopping after finding only 1 solution while the shell finds 2 solutions (and the 2nd is the right answer).
I copied the original problem description directly from the "Statistics" output from my C-API trace, into a file and read that file into the interactive shell and it works as expected, finding 2 solutions, and the second one is optimal (objective is 61).
However, when I solve the problem using the C-API, then it stops after finding 1 solution with objective 71, but it also says that is optimal.
I don't understand why the C-API is stopping after finding only one solution, and I also don't understand why it calls the solution "optimal" with objective 71, when in fact the interactive shell finds a better solution with objective 61.
I added SCIPresetParameters() to my C code right before calling SCIPsolve(), but that doesn't change the result.
I'm attaching the log.txt file produced by my C-API and also the output from the interactive shell.
All SCIP limits/params are set to default in my C-API, but I do notice at the top of the log.txt file (from the C-API) it does seem to list the following non-default separating params. Could this be causing it to stop after only one solution?
# minimal orthogonality for a cut to enter the LP in the root node
# [type: real, range: [0,1], default: 0.5]
separating/minorthoroot = 0.1
# maximal number of separation rounds in the root node of a subsequent run (-1: unlimited)
# [type: int, range: [-1,2147483647], default: 1]
separating/maxroundsrootsubrun = 5
# maximal additional number of separation rounds in subsequent price-and-cut loops (-1: no additional restriction)
# [type: int, range: [-1,2147483647], default: 1]
separating/maxaddrounds = 5
# maximal number of separated cuts at the root node (0: disable root node separation)
# [type: int, range: [0,2147483647], default: 2000]
separating/maxcutsroot = 5000
# separation frequency for the global cut pool (-1: disable global cut pool, 0: only separate pool at the root)
# [type: int, range: [-1,2147483647], default: 0]
separating/poolfreq = 10
________________________________________
From: Scip [scip-bounces at zib.de] on behalf of Gerald Gamrath [gamrath at zib.de]
Sent: Monday, April 10, 2017 2:45 PM
To: scip at zib.de
Subject: Re: [SCIP] Problem with disjunct of conjuncts with variable dependency
Hi Richard,
updating to 4.0 would be good, but I'm actually also finding the
solution with objective 61 when using SCIP 3.2.1. Could you send me the
log file of your run, best including the output of SCIPprintStatistics()?
Best,
Gerald
Am 10.04.2017 um 21:29 schrieb 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
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
_______________________________________________
Scip mailing list
Scip at zib.de
https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: log.txt
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170412/feeeb215/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: log_interactive_shell.txt
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170412/feeeb215/attachment-0001.txt>
More information about the Scip
mailing list