[Couenne] Need Help: Couenne Cannot solve my MINLP problem

Yifan Guan yfguan at umich.edu
Fri Jun 19 00:04:29 EDT 2020 

Hi Pietro,

First of all, thank you very much!

All variables are nonnegative integers.
After three days, the output of Couene is shown below:
[image: Screen Shot 2020-06-18 at 8.12.41 PM.png]

I agree with this:
'''
Probably the quickest solution is the following: given that all w variables
are integer, there are only 22 values for the denominator that's in common
to all expressions (unless I'm missing something from the problem). That
means you can solve 22 problems (all of them MIPs, i.e. linear with
integrality constraints) and choose the best solution out of these 22.
Given the size of the problem, Cbc should solve all of these 22 problems
quite fast (definitely less than three days).
'''

However, the previous example I showed is one easy special case. A more
general case would have different denominators.
For a tiny example,
Objective function:
Minimize
abs((w0 + w1 + w2)*/*(w0 + w1 + w2 + w3 + w4 + w5) - 0.7413793103448276)
+ abs((w0 + w1 + w2)*/*(w0 + w1 + w2 + w6) - 0.54455432443)
+ abs((w2 + w3)*/*(w0 + w2 + w3 + w4 + w7) - 0.345453456)

Constraints:
(1) all variables are nonnegative integers

(2) 50 <= w0 + w1 + w2 + w3 + w4 + w5

(3) w0 + w1 + w2 + w3 + w4 + w5 <= 60

(4) 30 <= w0 + w1 + w2 + w6

(5) w0 + w1 + w2 + w6 <= 40

(6) 25 <= w0 + w2 + w3 + w4 + w7

(7) w0 + w2 + w3 + w4 + w7 <= 30

Can I still follow your logic to convert this problem into MIPs?
To be more precise, enumerate every value in denominators' constraints.
This would result in (60 - 50 + 1) * (40 - 30 + 1) * (30 - 25 + 1) = 726
MIPs.
And I choose the minimal objective value among those 726 MIPs.

Please correct me if I'm wrong.
The only thing I'm concerned about is dependencies between denominators.
For example, (w0 + w1 + w2 + w3 + w4 + w5) and (w0 + w1 + w2 + w6) both
contain (w0 + w1 + w2).

I really appreciate your valuable help!

Best,

Yifan


On Thu, Jun 18, 2020 at 11:19 PM Yifan Guan <yfguan at umich.edu> wrote:

> Hi Pietro,
>
> First of all, thank you very much!
>
> All variables are nonnegative integers.
> After three days, the output of Couene is shown below:
> [image: Screen Shot 2020-06-18 at 8.12.41 PM.png]
>
> I agree with this:
> '''
> Probably the quickest solution is the following: given that all w
> variables are integer, there are only 22 values for the denominator that's
> in common to all expressions (unless I'm missing something from the
> problem). That means you can solve 22 problems (all of them MIPs, i.e.
> linear with integrality constraints) and choose the best solution out of
> these 22. Given the size of the problem, Cbc should solve all of these 22
> problems quite fast (definitely less than three days).
> '''
>
> However, this is one easy special case I showed. A more general case would
> have different denominators.
> For example,
> Objective function:
> abs((w0 + w1 + w2)*/*(w0 + w1 + w2 + w3 + w4 + w5) - 0.7413793103448276)
> + abs((w0 + w1 + w2)*/*(w0 + w1 + w2 + w3 + w4 + w5) - 0.7413793103448276)
> + abs((w0 + w1 + w2)*/*(w0 + w1 + w2 + w3 + w4 + w5) - 0.7413793103448276)
>
> Constraints:
> (1) all variables are nonnegative integers
>
> (2) 500.0 <= w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 + w10 + w11 +
> w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22 + w23 + w24
> + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 + w35 + w36 +
> w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47 + w48 + w49
> + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57
>
> (3) w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 + w10 + w11 + w12 +
> w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22 + w23 + w24 + w25
> + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 + w35 + w36 + w37 +
> w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47 + w48 + w49 + w50
> + w51 + w52 + w53 + w54 + w55 + w56 + w57 <= 521.0
>
> Can I still follow your logic to convert this problem into MIPs?
> To be more precise,
>
> Please correct me if I'm wrong.
>
> Best,
>
> Yifan
>
> On Thu, Jun 18, 2020 at 4:43 PM Pietro Belotti <pbelotti at gmx.com> wrote:
>
>> Hi Yifan,
>>
>> this looks like a small problem w.r.t. variables and constraints, but the
>> objective function is complicated. The reason why Couenne hanged is
>> probably that after three days there was too much memory used (for instance
>> in the branch-and-bound tree). Are all variables only integer or are they
>> nonnegative?
>>
>> In any case, there might be some options to try but I would need the .nl
>> file used to feed Couenne.
>>
>> What is the gap after three days? How much is the best solution and the
>> lower bound? This might be useful.
>>
>> Probably the quickest solution is the following: given that all w
>> variables are integer, there are only 22 values for the denominator that's
>> in common to all expressions (unless I'm missing something from the
>> problem). That means you can solve 22 problems (all of them MIPs, i.e.
>> linear with integrality constraints) and choose the best solution out of
>> these 22. Given the size of the problem, Cbc should solve all of these 22
>> problems quite fast (definitely less than three days).
>>
>> Hope this helps,
>> Pietro
>>
>> *Sent:* Monday, June 15, 2020 at 12:23 AM
>> *From:* "Yifan Guan" <yfguan at umich.edu>
>> *To:* couenne at list.coin-or.org
>> *Subject:* [Couenne] Need Help: Couenne Cannot solve my MINLP problem
>> Hi all,
>>
>> Couenne cannot solve my MINLP problem.
>> Couenne ran for about three days and hanged.
>> I'm not sure why this problem occurred.
>> It might be a problem with my optimization problem formulation.
>> I hope you can give me some insightful suggestions.
>>
>> An overview of my objective function: a sum of the absolute value of
>> probability difference.
>> In each absolute value, one probability is a numeric value.
>> And the other probability is represented by variables I want to optimize
>> (both numerator and denominator are formed by the sum of some(or all)
>> variables).
>>
>> Totally, 58 variables, 1 objective, and 2 constraints are declared as
>> followed.
>>
>> My objective function:
>> minimize :
>> abs((w0 + w1 + w2 + w3 + w4 + w6 + w8 + w10 + w11 + w12 + w13 + w14 + w17
>> + w18 + w19 + w20 + w21 + w22 + w23 + w24 + w25 + w26 + w29 + w30 + w31 +
>> w33 + w35 + w36 + w37 + w38 + w39 + w41 + w42 + w43 + w45 + w46 + w48 + w49
>> + w50 + w51 + w53 + w55 + w57)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7
>> + w8 + w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20
>> + w21 + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 +
>> w33 + w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45
>> + w46 + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.7413793103448276)
>> + abs((w5 + w7 + w9 + w15 + w16 + w27 + w28 + w32 + w34 + w40 + w44 + w47
>> + w52 + w54 + w56)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 +
>> w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22
>> + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 +
>> w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47
>> + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.25862068965517243)
>> + abs((w0 + w2 + w3 + w7 + w11 + w18 + w19 + w28 + w34 + w37 + w49 + w50
>> + w51 + w54 + w56 + w57)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 +
>> w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21
>> + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 +
>> w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46
>> + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.27586206896551724)
>> + abs((w1 + w24 + w26 + w31 + w33 + w39 + w40 + w44 + w47)*/*(w0 + w1 +
>> w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 + w10 + w11 + w12 + w13 + w14 + w15 +
>> w16 + w17 + w18 + w19 + w20 + w21 + w22 + w23 + w24 + w25 + w26 + w27 + w28
>> + w29 + w30 + w31 + w32 + w33 + w34 + w35 + w36 + w37 + w38 + w39 + w40 +
>> w41 + w42 + w43 + w44 + w45 + w46 + w47 + w48 + w49 + w50 + w51 + w52 + w53
>> + w54 + w55 + w56 + w57) - 0.15517241379310345)
>> + abs((w4 + w5 + w6 + w8 + w9 + w10 + w12 + w13 + w14 + w15 + w16 + w17 +
>> w20 + w21 + w22 + w23 + w25 + w27 + w29 + w30 + w32 + w35 + w38 + w41 + w42
>> + w45 + w46 + w48 + w52 + w53 + w55)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6
>> + w7 + w8 + w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19
>> + w20 + w21 + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 +
>> w32 + w33 + w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44
>> + w45 + w46 + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 +
>> w57) - 0.5344827586206896)
>> + abs((w36 + w43)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 +
>> w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22
>> + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 +
>> w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47
>> + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.034482758620689655)
>> + abs((w19 + w37 + w42)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 +
>> w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21
>> + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 +
>> w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46
>> + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.05172413793103448)
>> + abs((w0 + w1 + w5 + w8 + w9 + w11 + w13 + w15 + w24 + w26 + w31 + w36 +
>> w38 + w44 + w47 + w52 + w54)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 +
>> w8 + w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 +
>> w21 + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33
>> + w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 +
>> w46 + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.29310344827586204)
>> + abs((w2 + w6 + w28)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9
>> + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 +
>> w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34
>> + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 +
>> w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.05172413793103448)
>> + abs((w17 + w21 + w33 + w41 + w49 + w51)*/*(w0 + w1 + w2 + w3 + w4 + w5
>> + w6 + w7 + w8 + w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 +
>> w19 + w20 + w21 + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31
>> + w32 + w33 + w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 +
>> w44 + w45 + w46 + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56
>> + w57) - 0.10344827586206896)
>> + abs((w32 + w34 + w39 + w40)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 +
>> w8 + w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 +
>> w21 + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33
>> + w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 +
>> w46 + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.06896551724137931)
>> + abs((w27 + w29 + w50)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 +
>> w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21
>> + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 +
>> w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46
>> + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.05172413793103448)
>> + abs((w7 + w10 + w12 + w16 + w20 + w22 + w23 + w25 + w30 + w35 + w43 +
>> w46 + w48 + w55 + w56)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 +
>> w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21
>> + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 +
>> w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46
>> + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.25862068965517243)
>> + abs((w3 + w57)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 +
>> w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22
>> + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 +
>> w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47
>> + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.034482758620689655)
>> + abs((w45 + w53)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 +
>> w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22
>> + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 +
>> w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47
>> + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.034482758620689655)
>> + abs((w4 + w14 + w18)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 +
>> w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21
>> + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 +
>> w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46
>> + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) -
>> 0.05172413793103448)
>> + abs((w0 + w3 + w4 + w9 + w11 + w12 + w14 + w17 + w20 + w22 + w24 + w27
>> + w28 + w29 + w30 + w33 + w34 + w35 + w37 + w38 + w40 + w41 + w45 + w46 +
>> w53 + w55)*/*(w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 + w10 +
>> w11 + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22 + w23
>> + w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 + w35 +
>> w36 + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47 + w48
>> + w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57) - 0.4482758620689655)
>> + abs((w1 + w2 + w5 + w6 + w7 + w8 + w10 + w13 + w15 + w16 + w18 + w19 +
>> w21 + w23 + w25 + w26 + w31 + w32 + w36 + w39 + w42 + w43 + w44 + w47 + w48
>> + w49 + w50 + w51 + w52 + w54 + w56 + w57)*/*(w0 + w1 + w2 + w3 + w4 +
>> w5 + w6 + w7 + w8 + w9 + w10 + w11 + w12 + w13 + w14 + w15 + w16 + w17 +
>> w18 + w19 + w20 + w21 + w22 + w23 + w24 + w25 + w26 + w27 + w28 + w29 + w30
>> + w31 + w32 + w33 + w34 + w35 + w36 + w37 + w38 + w39 + w40 + w41 + w42 +
>> w43 + w44 + w45 + w46 + w47 + w48 + w49 + w50 + w51 + w52 + w53 + w54 + w55
>> + w56 + w57) - 0.5517241379310345)
>>
>> Constraints:
>> (1) all variables are integer
>>
>> (2) 500.0 <= w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 + w10 + w11
>> + w12 + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22 + w23 +
>> w24 + w25 + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 + w35 + w36
>> + w37 + w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47 + w48 +
>> w49 + w50 + w51 + w52 + w53 + w54 + w55 + w56 + w57
>>
>> (3) w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 + w10 + w11 + w12 +
>> w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22 + w23 + w24 + w25
>> + w26 + w27 + w28 + w29 + w30 + w31 + w32 + w33 + w34 + w35 + w36 + w37 +
>> w38 + w39 + w40 + w41 + w42 + w43 + w44 + w45 + w46 + w47 + w48 + w49 + w50
>> + w51 + w52 + w53 + w54 + w55 + w56 + w57 <= 521.0
>>
>>
>> Thank you for your time and help! I really appreciate any comments!
>>
>> Best,
>>
>> Yifan
>>
>> --
>> *Yifan Guan*
>> Computer Science Engineering
>> Undergraduate University of Michigan Class of 2019
>> Rackham Master University of Michigan Class of 2021
>> Website: https://yifanguan.github.io/
>> _______________________________________________ Couenne mailing list
>> Couenne at list.coin-or.org
>> https://list.coin-or.org/mailman/listinfo/couenne
>>
>
>
> --
> *Yifan Guan*
> Computer Science Engineering
> Undergraduate University of Michigan Class of 2019
> Rackham Master University of Michigan Class of 2021
> Website: https://yifanguan.github.io/
>


-- 
*Yifan Guan*
Computer Science Engineering
Undergraduate University of Michigan Class of 2019
Rackham Master University of Michigan Class of 2021
Website: https://yifanguan.github.io/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/couenne/attachments/20200619/93ae1f55/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screen Shot 2020-06-18 at 8.12.41 PM.png
Type: image/png
Size: 257695 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/couenne/attachments/20200619/93ae1f55/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example.nl
Type: application/octet-stream
Size: 16498 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/couenne/attachments/20200619/93ae1f55/attachment-0001.obj>

More information about the Couenne mailing list