[Cbc] Cbc Digest, Vol 95, Issue 7
John Forrest
john.forrest at fastercoin.com
Sun May 31 10:36:46 EDT 2015
Alexis,
It was just good luck that it worked.
The partial solution in solini.txt does not seem to be a valid
solution. If I fix those variables the problem is infeasible (the same
is true if I just fix a's or u's). It looks as if the problem is very
sensitive to exacat values and that printed values were not good enough.
The code as-is fixes other variables to zero, finds problem is
infeasible and then says - OK lets free up all non-integer variables to
see if that works i.e. free all variables. It then gets root solution -
which in this case is valid.
I have modified code (on a compile time option) so that it will fix all
variables in solini.txt and then do a mini branch and bound - that
should work if solini.txt had a valid solution.
Your best bet is to code your own version - fix some to known value and
do branch and bound on easier problem stopping at first solution and
then passing that in without loss of accuracy. It looks as if fixing
l_xx_xx to zero is much more forgiving that fixing u. Have you got
something I could test on?
John
On 27/05/15 19:14, Alexis wrote:
> Hi John,
>
> I managed to implement something and it seems to work (?).
>
> Here is what I have done is somewhat pseudocode:
>
> OsiClpSolverInterface mySolver;
> Set Variables, Constraints and SOS2 Constraints in mySolver (see
> Sample.lp file for the output)
> CbcModel myModel(mySolver);
> const char * argv2[] = { "cbc", "-directory", mydirectory,
> "-mipStart", "solini.txt", "-solve", "-quit" }; where solini.txt is a
> valid (partial) initial solution
> CbcMain1(7, argv2, myModel);
>
> I am saying it seems to work because the function
> computeCompleteSolution(...) in CbcMipStartIO.cpp is successfully
> called (returns 0) and the following code
> is called (in CbcSolver.cpp)
>
> int status = computeCompleteSolution( babModel_,
> colNames, mipStart, &x[0], obj );
> if (!status) {
> babModel_->setBestSolution( &x[0],
> static_cast<int>(x.size()), obj, false );
> babModel_->setSolutionCount(1);
> }
>
> Now a few words about the problem. Here is a typical SOS2 constraints
> (see Sample.lp file)
>
> SOS2CONS1: S2:: l_1_1:1 l_1_2:2 l_1_3:3 l_1_4:4 l_1_5:5 l_1_6:6
> l_1_7:7 l_1_8:8 l_1_9:9 l_1_10:10 l_1_11:11 l_1_12:12 l_1_13:13
> l_1_14:14 l_1_15:15 l_1_16:16 l_1_17:17 l_1_18:18 l_1_19:19 l_1_20:20
> l_1_21:21 l_1_22:22 l_1_23:23 l_1_24:24 l_1_25:25 l_1_26:26 l_1_27:27
> l_1_28:28 l_1_29:29 l_1_30:30 l_1_31:31 l_1_32:32 l_1_33:33 l_1_34:34
>
> together with
>
> COVER_1: l_1_1 + l_1_2 + l_1_3 + l_1_4 + l_1_5 + l_1_6 + l_1_7 +
> l_1_8 + l_1_9 + l_1_10
> + l_1_11 + l_1_12 + l_1_13 + l_1_14 + l_1_15 + l_1_16 + l_1_17 +
> l_1_18 + l_1_19 + l_1_20
> + l_1_21 + l_1_22 + l_1_23 + l_1_24 + l_1_25 + l_1_26 + l_1_27 +
> l_1_28 + l_1_29 + l_1_30
> + l_1_31 + l_1_32 + l_1_33 + l_1_34 = 1
>
> and
>
> INTER_1: - u_1 -10.44566 l_1_1 -9.82066 l_1_2 -9.19566 l_1_3 -8.57066
> l_1_4 -7.94566 l_1_5 -7.32066 l_1_6 -6.69566 l_1_7 -6.07066 l_1_8
> -5.44566 l_1_9
> -4.82066 l_1_10 -4.19566 l_1_11 -3.57066 l_1_12 -2.94566 l_1_13
> -2.32066 l_1_14 -2.25232 l_1_15 -1.69566 l_1_16 -1.07066 l_1_17
> -0.61982 l_1_18 -0.44566 l_1_19
> + 0.17934 l_1_20 + 0.26541 l_1_21 + 0.80434 l_1_22 + 1.42934 l_1_23 +
> 2.05434 l_1_24 + 2.67934 l_1_25 + 3.30434 l_1_26 + 3.92934 l_1_27 +
> 4.55434 l_1_28 + 5.17934 l_1_29
> + 5.80434 l_1_30 + 6.42934 l_1_31 + 7.05434 l_1_32 + 7.67934 l_1_33 +
> 8.30434 l_1_34 = 0
>
> In "solini.txt", the value for u_1 is given so that sets the l_1_i
> variables.
>
> Am I on the right track? I am still not sure 100% about what mipStart
> does. Is it just calculating and setting up a feasible solution (and
> an upper bound) for the B&B?
>
> Thanks again, I will keep you posted about my investigations.
>
> Alexis
>
> On 2015-05-20 7:27 AM, cbc-request at list.coin-or.org wrote:
>> Send Cbc mailing list submissions to
>> cbc at list.coin-or.org
>>
>> To subscribe or unsubscribe via the World Wide Web, visit
>> http://list.coin-or.org/mailman/listinfo/cbc
>> or, via email, send a message with subject or body 'help' to
>> cbc-request at list.coin-or.org
>>
>> You can reach the person managing the list at
>> cbc-owner at list.coin-or.org
>>
>> When replying, please edit your Subject line so it is more specific
>> than "Re: Contents of Cbc digest..."
>>
>>
>> Today's Topics:
>>
>> 1. Re: Cbc Digest, Vol 95, Issue 6 (Alexis)
>> 2. Re: Cbc Digest, Vol 95, Issue 6 (John Forrest)
>> 3. Re: Cbc Digest, Vol 95, Issue 6 (Haroldo Gambini Santos)
>>
>>
>> ----------------------------------------------------------------------
>>
>> Message: 1
>> Date: Tue, 19 May 2015 12:56:16 -0600
>> From: Alexis<aguigue at softree.com>
>> To:cbc at list.coin-or.org
>> Subject: Re: [Cbc] Cbc Digest, Vol 95, Issue 6
>> Message-ID:<555B8750.3010300 at softree.com>
>> Content-Type: text/plain; charset="windows-1252"; Format="flowed"
>>
>> Thanks John
>>
>> I have done preliminary testing of mipStart using standalone cbc. It
>> looks promising.
>> However, our real problems have a bunch of SOS2 constraints. I checked
>> but it does not
>> seems that cbc v2.9.0 can import/read such files yet, am I correct? The
>> other
>> thing I was wondering is that whether mipStart would work with SOS2
>> constraints?
>> Say we have a lp problem with binary variables and some SOS2
>> constraints, would
>> mipStart work by, again, just providing the values of the binary
>> variables, and
>> leaving the variables in the SOS2 constraints to be decided?
>>
>> Also, is there some doc/pub about Haroldo implementation/method?
>>
>> Thanks in advance
>>
>> Alexis
>>
>> On 2015-05-13 10:00 AM,cbc-request at list.coin-or.org wrote:
>>> Send Cbc mailing list submissions to
>>> cbc at list.coin-or.org
>>>
>>> To subscribe or unsubscribe via the World Wide Web, visit
>>> http://list.coin-or.org/mailman/listinfo/cbc
>>> or, via email, send a message with subject or body 'help' to
>>> cbc-request at list.coin-or.org
>>>
>>> You can reach the person managing the list at
>>> cbc-owner at list.coin-or.org
>>>
>>> When replying, please edit your Subject line so it is more specific
>>> than "Re: Contents of Cbc digest..."
>>>
>>>
>>> Today's Topics:
>>>
>>> 1. Re: Cbc Digest, Vol 95, Issue 5 (Alexis)
>>> 2. Re: Cbc Digest, Vol 95, Issue 5 (John Forrest)
>>>
>>>
>>> ----------------------------------------------------------------------
>>>
>>> Message: 1
>>> Date: Tue, 12 May 2015 11:09:58 -0600
>>> From: Alexis<aguigue at softree.com>
>>> To:cbc at list.coin-or.org
>>> Subject: Re: [Cbc] Cbc Digest, Vol 95, Issue 5
>>> Message-ID:<555233E6.8030501 at softree.com>
>>> Content-Type: text/plain; charset="windows-1252"; Format="flowed"
>>>
>>> Thanks John.
>>>
>>> I am actually using the API. I found this example
>>>
>>> https://projects.coin-or.org/Cbc/browser/trunk/Cbc/examples/hotstart.cpp
>>>
>>> I will try it. Is the example you were referring to?
>>>
>>> On 2015-05-12 10:00 AM,cbc-request at list.coin-or.org wrote:
>>>> Send Cbc mailing list submissions to
>>>> cbc at list.coin-or.org
>>>>
>>>> To subscribe or unsubscribe via the World Wide Web, visit
>>>> http://list.coin-or.org/mailman/listinfo/cbc
>>>> or, via email, send a message with subject or body 'help' to
>>>> cbc-request at list.coin-or.org
>>>>
>>>> You can reach the person managing the list at
>>>> cbc-owner at list.coin-or.org
>>>>
>>>> When replying, please edit your Subject line so it is more specific
>>>> than "Re: Contents of Cbc digest..."
>>>>
>>>>
>>>> Today's Topics:
>>>>
>>>> 1. Hot Start for MIP (Alexis)
>>>> 2. Re: Hot Start for MIP (John Forrest)
>>>>
>>>>
>>>> ----------------------------------------------------------------------
>>>>
>>>> Message: 1
>>>> Date: Mon, 11 May 2015 11:07:35 -0600
>>>> From: Alexis<aguigue at softree.com>
>>>> To:cbc at list.coin-or.org
>>>> Subject: [Cbc] Hot Start for MIP
>>>> Message-ID:<5550E1D7.8030902 at softree.com>
>>>> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>>>>
>>>> I have got a large MIP to solve for which I would like to implement a
>>>> hot start strategy.
>>>>
>>>> My understanding is that I should use the function
>>>> CbcModel::setHotstartSolution(const double *solution, const int
>>>> *priorities=NULL),
>>>> where solution assumes the same ''order'' of variables as defined for
>>>> the model itself. I am not so sure to understand the meaning of
>>>> the pointer priorities though. The hotstart solution I intend to give is
>>>> an actual feasible solution to the MIP.
>>>>
>>>> Am I on the right track?
>>>>
>>>> Thanks in advance for the help
>>>>
>
>
> --
> Alexis Guigue, E.I.T., B.Eng., M.A.Sc., Ph.D.
> Software Engineer/Research Engineer
> aguigue at softree.com
> 604-519-6222, ext. 3
>
> Softree Technical Systems Inc. <http://www.softree.com>
> Engineering an Easier Way
>
> Softree News & Updates <http://http://eepurl.com/XJT-z>
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20150531/890bd549/attachment.html>
More information about the Cbc
mailing list