[SCIP] Problem with disjunct of conjuncts with variable dependency
Ambros Gleixner
gleixner at zib.de
Wed Apr 12 09:02:49 CEST 2017
Hi Richard,
This is indeed strange behavior. The separating parameters should not
affect correctness, but given that you use SCIPresetParameters() it is
already strange they take a non-default value.
Before we continue, can you use valgrind to check for potential memory
errors and upgrade to SCIP 4.0?
Best,
Ambros
On 12.04.2017 02:25, Levinson, Richard J. (ARC-TI)[SGT, INC] wrote:
> 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
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
--
Ambros Gleixner, Zuse Institute Berlin, http://www.zib.de/gleixner
More information about the Scip
mailing list