[Couenne] Lower/Upper bounds variables

Thu Jun 4 10:34:05 EDT 2015

Hi Luca,
the bound is given by the worst of the active nodes when you interrupt
the enumeration. I am not aware of any solver that provides the
corresponding solution; I am afraid you would have to implement it
yourself, by looping through all the active nodes and solving the
corresponding LPs.

Maybe a relatively easy way to do this is to "stop" branching (i.e.
stop generating new nodes) instead of "exiting" couenne when the limit
is hit. Then, whatever nodes are left on the tree are the ones you
need to look at; and if you are using a best bound exploration
strategy it may not be too hard to do what you are looking for.

Giacomo

On Thu, Jun 4, 2015 at 10:22 PM, Luca Mencarelli
<mencarelli at lix.polytechnique.fr> wrote:
> Dear Pietro,
>
> Thanks for the answer. Yes, I agree with you. Maybe I didn't explain
> myself well,
> but the point is that I will like to retrieve the values corresponding to
> -283,
> since I'm developing a feasibility recovering heuristic based on the DUAL
> bound.
>
> Best,
> Luca
>
> --
> Luca Mencarelli
> PhD Candidate at LIX, Ecole Polytechnique
> 91128 Palaiseau CEDEX, France
> Office: 2072 (Bâtiment Alan Turing, second floor)
> LIX e-mail address: mencarelli at lix.polytechnique.fr
> INRIA e-mail address:  luca.mencarelli at inria.fr
>
>
>> Dear Luca,
>>
>> I tried the following AMPL script:
>>
>> model nonlinear_w_cont.mod
>> data mnck_instance_0.dat
>> write gdis;
>> option solver couenne;
>> solve;
>> display sigmoid_p;
>>
>> The output I get from the script shows a DUAL bound of -283 and a
>> PRiMAL bound of -214 when stopping couenne after 20 seconds. The dual
>> bound does not refer to a solution as it is simply a lower bound on
>> the optimal solution. The primal bound instead refers to a feasible
>> solution. Indeed when printing the only variables appearing in the
>> objective, their sum seems roughly equal to 214.
>>
>> Since Couenne generally refers to minimization problems, the lower
>> bound is the dual bound and the upper bound the primal one. in the
>> case of a maximization (which you correctly reformulate as a min
>> problem) the upper bound is a dual and the lower bound is a primal
>> bound. Hence Couenne reports the solution found that refers to the
>> primal bound.
>>
>> When re-running Couenne on the dis.nl saved by the script, the same
>> thing happens, then the dis.sol file contains, from lines 39 onward,
>> the same solution found by the script, which again sums up to about
>> 214. I'm running stable/0.4, but it really seems like I can't
>> reproduce your problem. What solution are you getting?
>>
>> Regards,
>> Pietro
>>
>>
>>
>>
>>
>> On Wed, Jun 3, 2015 at 5:23 PM, Luca Mencarelli
>> <mencarelli at lix.polytechnique.fr> wrote:
>>> Dear Pietro,
>>>
>>> I've done other experiments with the code, but I cannot retrieve
>>> the values of the decision variables corresponding to the Upper Bound
>>> provided by Couenne.
>>>
>>> Thanks very much. Best regards,
>>> Luca
>>>
>>>> Dear Pietro,
>>>>
>>>> I attach the model and the output files. I get an upper_bound =
>>>> -210.89,
>>>> while the upper bound provided by Couenne (version 0.4.8) is -286.95.
>>>> The original problem is a maximization one.
>>>>
>>>> Thanks again. Best,
>>>> Luca
>>>>
>>>> --
>>>> Luca Mencarelli
>>>> PhD Candidate at LIX, Ecole Polytechnique
>>>> 91128 Palaiseau CEDEX, France
>>>> Office: 2072 (Bâtiment Alan Turing, second floor)
>>>> LIX e-mail address: mencarelli at lix.polytechnique.fr
>>>> INRIA e-mail address:  luca.mencarelli at inria.fr
>>>>
>>>>
>>>>
>>>>> Hi Luca,
>>>>>
>>>>> this should not happen, it might be a bug. Can you send me the model
>>>>> (a .nl file should suffice)? I suspect the constant term of the
>>>>> objective function might be ignored. Also, what version of Couenne are
>>>>> you using?
>>>>>
>>>>> Pietro
>>>>>
>>>>> On Mon, May 18, 2015 at 4:55 PM, Luca Mencarelli
>>>>> <mencarelli at lix.polytechnique.fr> wrote:
>>>>>> Dear Pietro,
>>>>>>
>>>>>> First of thanks very much for the answer. However in the .sol file I
>>>>>> found
>>>>>> the same values as the one I obtain via the display command. But when
>>>>>> I
>>>>>> recompute
>>>>>> the objective function with these values, it is less than the upper
>>>>>> bound
>>>>>> provided
>>>>>> by Couenne.
>>>>>>
>>>>>> Best,
>>>>>> Luca
>>>>>>
>>>>>> --
>>>>>>
>>>>>> Luca Mencarelli
>>>>>> PhD Candidate at LIX, Ecole Polytechnique
>>>>>> 91128 Palaiseau CEDEX, France
>>>>>> Office: 2072 (Bâtiment Alan Turing, second floor)
>>>>>> LIX e-mail address: mencarelli at lix.polytechnique.fr
>>>>>> INRIA e-mail address:  luca.mencarelli at inria.fr
>>>>>>
>>>>>>
>>>>>>
>>>>>>> Hi Luca,
>>>>>>>
>>>>>>> when Couenne stops before closing the gap, the best feasible MINLP
>>>>>>> solution found (if any) is saved in a file with the same name as the
>>>>>>> input file but with extension .sol (which is the format read by
>>>>>>> AMPL).
>>>>>>> So the answer is yes for the upper bound if at least one solution is
>>>>>>> found.
>>>>>>>
>>>>>>> However, this does not make much sense for the lower bound, given
>>>>>>> that
>>>>>>> it's obtained by a relaxation of the MINLP (and would hence be
>>>>>>> infeasible) and is related to the whole branch-and-bound search tree
>>>>>>> rather than a specific subproblem. Hence no solution is available
>>>>>>> for
>>>>>>> the lower bound.
>>>>>>>
>>>>>>> Hope this helps,
>>>>>>> Pietro
>>>>>>>
>>>>>>>
>>>>>>> On Mon, May 18, 2015 at 11:05 AM, Luca Mencarelli
>>>>>>> <mencarelli at lix.polytechnique.fr> wrote:
>>>>>>>> Hi,
>>>>>>>>
>>>>>>>> If Couenne did not succeed in solving a problem to optimality, it's
>>>>>>>> possible to
>>>>>>>> retrieve the values of the decision variables corresponding to the
>>>>>>>> lower
>>>>>>>> and to
>>>>>>>> the upper bounds provided by the solver?
>>>>>>>>
>>>>>>>> Thanks. Best,
>>>>>>>> Luca
>>>>>>>>
>>>>>>>> --
>>>>>>>> Luca Mencarelli
>>>>>>>> PhD Candidate at LIX, Ecole Polytechnique
>>>>>>>> 91128 Palaiseau CEDEX, France
>>>>>>>> Office: 2072 (Bâtiment Alan Turing, second floor)
>>>>>>>> E-mail address: mencarelli at lix.polytechnique.fr
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> Couenne mailing list
>>>>>>>> Couenne at list.coin-or.org
>>>>>>>> http://list.coin-or.org/mailman/listinfo/couenne
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>> _______________________________________________
>>>> Couenne mailing list
>>>> Couenne at list.coin-or.org
>>>> http://list.coin-or.org/mailman/listinfo/couenne
>>>
>>>
>>
>
>
> _______________________________________________
> Couenne mailing list
> Couenne at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/couenne