[Bonmin] another unexpected infeasible problem !

Mon Sep 17 04:34:08 EDT 2007

Hi Pierre,

Yes, you are absolutely right, I will surely find in the documentation
many the answers I am looking for...  At least there is no better starting
point, isn't there ? :)

And regarding RealPaver, I think it indeed "does the three". I give you a
link the homepage 
http://www.sciences.univ-nantes.fr/info/perso/permanents/granvil/realpaver/main.html
though it has not been updated for a long time.

Nicolas

> Dear Nicolas,
> You should refer to the documentation of Bonmin. This software is not
> currently designed at giving global optima of non-convex problems
> (problems
> which have a non-convex continuous relaxation) and the default algorithm
> is
> particularly not designed at non-convex problem.
> The least you should do if you want to try to solve a non-convex problem
> is
> to set the option
>
> bonmin.algorithm B-BB
>
> (If I do that on your problem, bonmin finds a feasible solution).
>
> For more options, you could look at the documentation, there are a few
> extra
> tricks we can play to try to be lucky with finding good solution of
> non-convex problems. For instance you can find it here:
> http://www.coin-or.org/Bonmin/options_set/index.html#sec:opt_nonconv
>
> I am very happy to learn that RealPlayer (isn't that name already taken by
> somebody?)  solves gear4.
> I have a question. I see that you are using a modeling language different
> than ampl. Does your code come with a modeling language for Non-linear
> problems? Is it able to compute derivative? Is it free?
> If it does the three it might be of interest to us sometime.
>
> Cheers,
> Pierre
> On 9/12/07, Nicolas BERGER <Nicolas.Berger at univ-nantes.fr> wrote:
>>
>> Bonjour à nouveau,
>>
>>
>> I am trying to solve the following problem (it is an optimisation
>> problem
>> --"gear4"-- from MINLPlib which I have changed into a simple constraint
>> satisfaction problem) :
>>
>> ----------------------------------------------------------------
>> param best_value := 1.643428;
>> param eps        := 1;          #= max(1, 1% x best_value)
>>
>> var i1 integer >= 10 <= 25 ; #solu=19.0000000000,
>> var i2 integer >= 0 <= 20 ;  #solu=16.0000000000,
>> var i3 integer >= 37 <= 50 ; #solu=43.0000000000,
>> var i4 integer >= 45 <= 55 ; #solu=49.0000000000,
>> var x6 >= 0 <= 100 ; #solu=,
>> var x7 >= 0 <= 100 ; #solu=1.64342800000;
>>
>>
>> subject to
>>     cons1:-1.0e6*i1*i2/(i3*i4)-x6+x7=-144279.32477276;
>>     obj1:-x6-x7-(0) >= - best_value - eps;
>>     obj2:-x6-x7-(0) <= - best_value + eps;
>>
>> option solver bonmin ;
>>
>> solve ;
>> display i1,i2,i3,i4,x6,x7;
>> ----------------------------------------------------------------
>>
>>
>>
>>
>> Here is what I get from Ampl :
>>
>> -----------------------------------------------------------------
>> WARNING: Tried to set option "expect_infeasible_problem" to a value of
>> "yes",
>>          but the previous value is set to disallow clobbering.
>>          The setting will remain as: "expect_infeasible_problem no"
>> WARNING: Tried to set option "mu_strategy" to a value of "adaptive",
>>          but the previous value is set to disallow clobbering.
>>          The setting will remain as: "mu_strategy monotone"
>> WARNING: Tried to set option "mu_oracle" to a value of "probing",
>>          but the previous value is set to disallow clobbering.
>>          The setting will remain as: "mu_oracle quality-function"
>> bonmin:
>>
>>
>> ******************************************************************************
>> This program contains Ipopt, a library for large-scale nonlinear
>> optimization.
>> Ipopt is released as open source code under the Common Public License
>> (CPL).
>>          For more information visit http://projects.coin-or.org/Ipopt
>>
>> ******************************************************************************
>>
>> Error in an AMPL evaluation. Run with "halt_on_ampl_error yes" to see
>> details.
>> IpOp0008I
>>               Num      Status      Obj             It       time
>> IpOp0009I     1        OPT         0              17       0.012001
>> Cbc0013I At root node, 0 cuts changed objective from 0 to 0 in 1 passes
>> Cbc0014I Cut generator 0 (Outer Approximation Supporting Hyperplanes for
>> NLP optimum) - 0 row cuts (0 active), 0 column cuts
>> Cbc0014I Cut generator 1 (GMI) - 1 row cuts (0 active), 0 column cuts
>> Cbc0014I Cut generator 2 (Probing) - 0 row cuts (0 active), 1 column
>> cuts
>> Cbc0014I Cut generator 3 (covers) - 0 row cuts (0 active), 0 column cuts
>> Cbc0014I Cut generator 4 (MIR) - 0 row cuts (0 active), 0 column cuts
>> Cbc0014I Cut generator 5 (Outer Approximation local enumerator) - 0 row
>> cuts (0 active), 0 column cuts
>> Cbc0014I Cut generator 6 (Outer Approximation feasibility checker) - 0
>> row
>> cuts (0 active), 0 column cuts
>> Cbc0001I Search completed - best objective 1e+50, took 1 iterations and
>> 0
>> nodes (0.42 seconds)
>>
>>         "Finished"
>> Finished
>>
>> bonmin: Infeasible problem
>> i1 = 0
>> i2 = 0
>> i3 = 0
>> i4 = 0
>> x6 = 0
>> x7 = 0
>> ----------------------------------------------------------------
>>
>>
>>
>>
>> This problem is said to be infeasible, but it *DOES* have a solution
>> when
>> I use my constraint satisfaction tool (RealPaver) :
>>
>> -------------------------------------------------------------------
>> problem pb_gear4 /*MINLPlib*/
>>   num
>>     best_value := 1.643428,
>>     eps        := 1;
>>
>>   var
>>     i1 : int ~ [10, 25] /*19.0000000000*/,
>>     i2 : int ~ [0, 20] /*16.0000000000*/,
>>     i3 : int ~ [37, 50] /*43.0000000000*/,
>>     i4 : int ~ [45, 55] /*49.0000000000*/,
>>     x6 : real ~ [0, 100] /**/,
>>     x7 : real ~ [0, 100] /*1.64342800000*/;
>>
>>
>>
>>   ctr
>>     -1.0e6*i1*i2/(i3*i4)-x6+x7=-144279.32477276,
>>     -x6-x7-(0) >= - best_value - eps,
>>     -x6-x7-(0) <= - best_value + eps;
>>
>>
>>
>>   solve * ;
>> end ;
>> -------------------------------------------------------------------
>>
>>
>>
>> Solving this CSP by RealPaver gives me the following output :
>>
>> -------------------------------------------------------------------
>> Box 0 [11340 ms] [width 8.3528e-09] [vol 0]
>> i1 = 16
>> i2 = 19
>> i3 = 43
>> i4 = 49
>> x6 ~ [0..8.352799341082573e-09]
>> x7 ~ [1.643428473966196..1.643428482318996]
>>
>> Solving in 11340ms
>> 1 solution(s)
>> 379903 split(s)
>> 29 box(es) created in memory
>> -------------------------------------------------------------------
>>
>>
>>
>> I need an explanation... :(
>>
>>
>> Nicolas
>>
>>
>> _______________________________________________
>> Bonmin mailing list
>> Bonmin at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/bonmin
>>
>