[Couenne] Couenne error - integer programming with binomial probabilities

Mon Aug 23 22:31:47 EDT 2021

Dear Pietro,
Will BONMIN be able to solve my problem which is nonconvex, nonlinear integer programming (it involves binomial probabilities)?
Thanks,
Ravi
________________________________
From: Ravi Varadhan <ravi.varadhan at jhu.edu>
Sent: Saturday, June 26, 2021 6:35 PM
To: Pietro Belotti <pbelotti at gmx.com>
Cc: couenne at list.coin-or.org <couenne at list.coin-or.org>
Subject: Re: [Couenne] Couenne error - integer programming with binomial probabilities

Thank you, Pietro.

Linus Schrage showed me how to solve this problem in Lindo, using it as a stand-alone solver (not through AMPL).

Best regards,
Ravi

________________________________
From: Pietro Belotti <pbelotti at gmx.com>
Sent: Saturday, June 26, 2021 6:13 PM
To: Ravi Varadhan <ravi.varadhan at jhu.edu>
Cc: couenne at list.coin-or.org <couenne at list.coin-or.org>
Subject: Re: [Couenne] Couenne error - integer programming with binomial probabilities

      External Email - Use Caution

Hi Ravi,

I forgot to answer the second question. I'm not sure about solvers in NEOS that can solve your problem, but you're looking for a solver that can handle both black-box functions (as specified in the dll) and integer variables. I believe you could try a few in the section "nonlinearly constrainted optimization", as some of them do allow for both black-box functions and integer variables. Note however that you won't get a guarantee of global optimality due to the black-box functions, while the guarantee is given by solvers of factorable problems.

If you decided to go for my reformulation tricks, note that this will work for K small enough so that K! is less than 10^14, as otherwise the involved constraints may trigger some numerical problems in Couenne.

Regards,
Pietro

Sent: Friday, June 25, 2021 at 5:53 PM
From: "Ravi Varadhan" <ravi.varadhan at jhu.edu>
To: "Pietro Belotti" <pbelotti at gmx.com>
Cc: "couenne at list.coin-or.org" <couenne at list.coin-or.org>
Subject: Re: [Couenne] Couenne error - integer programming with binomial probabilities
Dear Pietro,
Thank you for this useful advice.  This is a relatively painful fix but might temporarily provide a way out.  May I ask when couenne is likely to have more comprehensive functionality such as being able to handle more complex mathematical functions?

Are there other integer programming solvers (connected to AMPL or in NEOS) that can help solve my problem with binomial probabilities?

Thanks again,
Ravi

________________________________
From: Pietro Belotti <pbelotti at gmx.com>
Sent: Friday, June 25, 2021 10:18 AM
To: Ravi Varadhan <ravi.varadhan at jhu.edu>
Cc: couenne at list.coin-or.org <couenne at list.coin-or.org>
Subject: Re: [Couenne] Couenne error - integer programming with binomial probabilities

      External Email - Use Caution

Dear Ravi,

as far as I know the gamma and the beta functions don't admit a closed form for general real arguments, so I'm afraid Couenne would not be able to solve problems to optimality.

However, in your model all variables are integer, so the gamma and beta reduce to functions that *could* be reduced to factorable form, although not so easily. First, for the gamma function, which is Gamma(n) = (n-1)! for an integer n, the AMPL expression would be (if I remember AMPL notation well)

prod{i=1..n-1} (n-i)

but this can't be input in AMPL because n is an AMPL variable and can't be in the {...} part. If you know of a valid upper bound on n, say you know n can't be above K, what you could do is

prod{i=1..K} max(1, n-i).

This would solve one problem, but unfortunately max() is not yet implemented in Couenne. You should therefore reformulate it yourself, for instance by adding binary variables y[i] so that the gamma function is written as

sum{i=1..K} F[i-1] * y[i]

with the extra constraint

sum{i=1..K} y[i] = 1;

and where F[i] are parameters that are set to the factorial of i:

param F {i=0..K} := if i<=1 then 1 else prod {j=2..i} j;

The Beta function can then be calculated from the Gamma function, but be aware that if you have more than one integer variable n you'll need as many sets of variables y.

Hope this helps. Regards,
Pietro

Sent: Thursday, June 24, 2021 at 11:25 PM
From: "Ravi Varadhan" <ravi.varadhan at jhu.edu>
To: "Pietro Belotti" <pbelotti at gmx.com>
Cc: "couenne at list.coin-or.org" <couenne at list.coin-or.org>
Subject: Re: [Couenne] Couenne error - integer programming with binomial probabilities
Dear Pietro,
Thank you. I was afraid that this might be the case.

Can couenne calculate gamma and beta functions? If so, I can define binomial probabilities in terms of these functions.

Thanks,
Ravi

________________________________
From: Pietro Belotti <pbelotti at gmx.com>
Sent: Thursday, June 24, 2021 3:31 PM
To: Ravi Varadhan <ravi.varadhan at jhu.edu>
Cc: couenne at list.coin-or.org <couenne at list.coin-or.org>
Subject: Re: [Couenne] Couenne error - integer programming with binomial probabilities

      External Email - Use Caution

Hi Ravi,

note that the mailing list will be soon discontinued; issues and discussions should be posted on the Couenne Github page:

https://github.com/coin-or/Couenne/<https://nam02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fcoin-or%2FCouenne%2F&data=04%7C01%7Cravi.varadhan%40jhu.edu%7C50c56998214b45cded0708d938efa551%7C9fa4f438b1e6473b803f86f8aedf0dec%7C0%7C0%7C637603424811866490%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=dB8KS7XtpsOlJX58SyGOVaJSSKsTtOhmdUOsLFjU%2F18%3D&reserved=0>

About your question: Couenne can only solve MINLP that are factorable, i.e. all expressions can be composed from a finite set of operators and these must be known: +, -, *, /, ^, log, sin, etc. Your functions gsl_cdf_binomial_P and gsl_cdf_binomial_Q are called from within a .dll and Couenne doesn't know their expression. Couenne needs these functions to be explicitly written in the constraints, therefore you'd have to drop the amplgsl.dll dependency and write these binomial cdf in closed form, or at least provide a good-enough approximation via a factorable expression.

Hope it helps. Regards,
Pietro

Sent: Thursday, June 24, 2021 at 8:43 PM
From: "Ravi Varadhan" <ravi.varadhan at jhu.edu>
To: "couenne at list.coin-or.org" <couenne at list.coin-or.org>
Subject: [Couenne] Couenne error - integer programming with binomial probabilities
Hi,
I am trying to solve a simple integer programming problem that involves binomial probabilities.  I have loaded the gsl DLL for binomial probability calculations.  I am calling couenne through AMPL (I am using AMPLE IDE on windows).  Here is my model (.mod) file:

reset;
option solver couenne;
option randseed 1234;

load amplgsl.dll;

var r >= 0 integer;
var n >= 0 integer;

function gsl_cdf_binomial_P;
function gsl_cdf_binomial_Q;

param p0 := 0.2;
param p1 := 0.4;
param alpha := 0.05;
param beta := 0.1;

  minimize obj:  n;
  subject to c1: gsl_cdf_binomial_Q(r,p0,n) <= alpha;
  subject to c2: gsl_cdf_binomial_P(r,p1,n) <= beta;
  subject to s1: n - r >= 0;

solve;
display r, n;

When I run this, I get the following error message:

Couenne 0.5.7 -- an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: cou... at list.coin-or.org<https://nam02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgroups.google.com%2F&data=04%7C01%7Cravi.varadhan%40jhu.edu%7C50c56998214b45cded0708d938efa551%7C9fa4f438b1e6473b803f86f8aedf0dec%7C0%7C0%7C637603424811876450%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=7z9qhlr4RefEvBLwwvb6rwTI%2FPW9dWWH%2F4sul%2Bf3XL8%3D&reserved=0>
Instructions: http://www.coin-or.org/Couenne<https://nam02.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.coin-or.org%2FCouenne&data=04%7C01%7Cravi.varadhan%40jhu.edu%7C50c56998214b45cded0708d938efa551%7C9fa4f438b1e6473b803f86f8aedf0dec%7C0%7C0%7C637603424811876450%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=C%2FK%2BxKX7CLCSqYzan0yrLWxEf4y7joUlwTotciaojzY%3D&reserved=0>
couenne:
ANALYSIS TEST: *** Error: function call not implemented
exit value 18446744073709551615
<BREAK>

I would appreciate any help as to what the problem is and how to address it.

Thank you,
Ravi
_______________________________________________ Couenne mailing list Couenne at list.coin-or.org https://list.coin-or.org/mailman/listinfo/couenne<https://nam02.safelinks.protection.outlook.com/?url=https%3A%2F%2Flist.coin-or.org%2Fmailman%2Flistinfo%2Fcouenne&data=04%7C01%7Cravi.varadhan%40jhu.edu%7C50c56998214b45cded0708d938efa551%7C9fa4f438b1e6473b803f86f8aedf0dec%7C0%7C0%7C637603424811886403%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=jC8sfvx4VmgSYMEGoI8aql%2FiwYSusthxfFwb1fdRysI%3D&reserved=0>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/couenne/attachments/20210824/70230643/attachment.html>