Optimum solution not found

Sheida

unread,

Aug 15, 2020, 9:47:01 PM8/15/20

to YALMIP

Dear,

I have a simple optimization problem and I tried to solve it directly using YALMIP, but the optimum solution is not found. Could you please help me to figure it out.

The optimization problem and the code are attached.

Thanks.

Main_test.m

Optimization problem.png

opt.m

Johan Löfberg

unread,

Aug 16, 2020, 1:37:33 AM8/16/20

to YALMIP

you would have to explain and show what happens, not just what does not happen

works here

* Starting YALMIP global branch & bound.
* Upper solver     : fmincon
* Lower solver     : GUROBI
* LP solver        : GUROBI
* -Extracting bounds from model
* -Perfoming root-node bound propagation
* -Calling upper solver (found a solution!)
* -Branch-variables : 4
* -More root-node bound-propagation
* -Performing LP-based bound-propagation 
* -And some more root-node bound-propagation
* Starting the b&b process
 Node       Upper      Gap(%)       Lower    Open   Time
    1 :   -4.285E+01    81.94     -1.037E+02    2     0s    
    2 :   -4.285E+01    81.94     -1.037E+02    3     1s    
    3 :   -4.285E+01    62.48     -8.269E+01    4     1s    
    4 :   -4.285E+01    62.48     -8.269E+01    5     2s    
    5 :   -4.285E+01    62.48     -8.269E+01    6     3s    
    6 :   -4.285E+01    62.48     -8.269E+01    7     4s    
    7 :   -4.285E+01    39.68     -6.455E+01    8     5s    
    8 :   -4.285E+01    39.68     -6.455E+01    9     6s    
    9 :   -4.285E+01    39.68     -6.455E+01   10     6s    
   10 :   -4.285E+01    39.68     -6.455E+01   11     7s    
   11 :   -4.285E+01    35.74     -6.193E+01   12     8s    
   12 :   -4.285E+01    35.74     -6.193E+01   13     9s    
   13 :   -4.285E+01    35.74     -6.193E+01   14     9s    
   14 :   -4.285E+01    35.74     -6.193E+01   15    10s    
   15 :   -4.285E+01    17.95     -5.149E+01   16    11s    
   16 :   -4.285E+01    17.95     -5.149E+01   17    11s    
   17 :   -4.285E+01    17.95     -5.149E+01   18    11s    
   18 :   -4.285E+01    17.95     -5.149E+01   19    12s    
   19 :   -4.285E+01    14.00     -4.944E+01   20    12s    
   20 :   -4.285E+01    14.00     -4.944E+01   21    12s    
   21 :   -4.285E+01    13.99     -4.944E+01   22    13s    
   22 :   -4.285E+01    13.99     -4.944E+01   23    13s    
   23 :   -4.285E+01    13.78     -4.933E+01   24    14s    
   24 :   -4.285E+01    13.78     -4.933E+01   25    14s    
   25 :   -4.285E+01    13.77     -4.933E+01   26    15s    
   26 :   -4.285E+01    13.77     -4.933E+01   27    16s    
   27 :   -4.285E+01    12.74     -4.881E+01   28    16s    
   28 :   -4.285E+01    12.74     -4.881E+01   29    17s    
   29 :   -4.285E+01    12.73     -4.881E+01   30    18s    
   30 :   -4.285E+01    12.73     -4.881E+01   31    19s    
   31 :   -4.285E+01     5.72     -4.543E+01   32    20s    
   32 :   -4.285E+01     5.72     -4.543E+01   33    20s    
   33 :   -4.285E+01     5.72     -4.543E+01   34    21s    
   34 :   -4.285E+01     5.72     -4.543E+01   35    22s    
   35 :   -4.285E+01     4.19     -4.472E+01   36    22s    
   36 :   -4.285E+01     4.19     -4.472E+01   37    23s    
   37 :   -4.285E+01     4.19     -4.472E+01   38    23s    
   38 :   -4.285E+01     4.19     -4.472E+01   39    24s    
   39 :   -4.285E+01     4.08     -4.467E+01   40    24s    
   40 :   -4.285E+01     4.08     -4.467E+01   41    24s    
   41 :   -4.285E+01     4.08     -4.467E+01   42    24s    
   42 :   -4.285E+01     4.08     -4.467E+01   43    25s    
   43 :   -4.285E+01     3.56     -4.444E+01   44    25s    
   44 :   -4.285E+01     3.56     -4.444E+01   45    25s    
   45 :   -4.285E+01     3.56     -4.444E+01   46    25s    
   46 :   -4.285E+01     3.56     -4.444E+01   47    26s    
   47 :   -4.285E+01     2.21     -4.383E+01   48    26s    
   48 :   -4.285E+01     2.21     -4.383E+01   49    26s    
   49 :   -4.285E+01     2.21     -4.383E+01   50    26s    
   50 :   -4.285E+01     2.21     -4.383E+01   51    27s    
   51 :   -4.285E+01     2.15     -4.380E+01   52    27s    
   52 :   -4.285E+01     2.15     -4.380E+01   53    27s    
   53 :   -4.285E+01     2.15     -4.380E+01   54    27s    
   54 :   -4.285E+01     2.15     -4.380E+01   55    28s    
   55 :   -4.285E+01     1.55     -4.353E+01   56    28s    
   56 :   -4.285E+01     1.55     -4.353E+01   57    29s    
   57 :   -4.285E+01     1.55     -4.353E+01   58    29s    
   58 :   -4.285E+01     1.55     -4.353E+01   59    29s    
   59 :   -4.285E+01     1.53     -4.352E+01   60    30s    
   60 :   -4.285E+01     1.53     -4.352E+01   61    30s    
   61 :   -4.285E+01     1.53     -4.352E+01   62    30s    
   62 :   -4.285E+01     1.53     -4.352E+01   63    31s    
   63 :   -4.285E+01     1.50     -4.351E+01   64    31s    
   64 :   -4.285E+01     1.50     -4.351E+01   65    31s    
   65 :   -4.285E+01     1.50     -4.351E+01   66    32s    
   66 :   -4.285E+01     1.50     -4.351E+01   67    32s    
   67 :   -4.285E+01     1.48     -4.350E+01   68    32s    
   68 :   -4.285E+01     1.48     -4.350E+01   69    32s    
   69 :   -4.285E+01     1.48     -4.350E+01   70    33s    
   70 :   -4.285E+01     1.48     -4.350E+01   71    33s    
   71 :   -4.285E+01     1.42     -4.347E+01   72    33s    
   72 :   -4.285E+01     1.42     -4.347E+01   73    33s    
   73 :   -4.285E+01     1.42     -4.347E+01   74    33s    
   74 :   -4.285E+01     1.42     -4.347E+01   75    34s    
   75 :   -4.285E+01     1.39     -4.346E+01   76    34s    
   76 :   -4.285E+01     1.39     -4.346E+01   77    35s    
   77 :   -4.285E+01     1.39     -4.346E+01   78    35s    
   78 :   -4.285E+01     1.39     -4.346E+01   79    35s    
   79 :   -4.285E+01     1.29     -4.342E+01   80    37s    
   80 :   -4.285E+01     1.29     -4.342E+01   81    38s    
   81 :   -4.285E+01     1.29     -4.342E+01   82    38s    
   82 :   -4.285E+01     1.29     -4.342E+01   83    39s    
   83 :   -4.285E+01     1.23     -4.339E+01   84    39s    
   84 :   -4.285E+01     1.23     -4.339E+01   85    39s    
   85 :   -4.285E+01     1.23     -4.339E+01   86    40s    
   86 :   -4.285E+01     1.23     -4.339E+01   87    40s    
   87 :   -4.285E+01     1.20     -4.338E+01   88    40s    
   88 :   -4.285E+01     1.20     -4.338E+01   89    40s    
   89 :   -4.285E+01     1.20     -4.338E+01   90    40s    
   90 :   -4.285E+01     1.20     -4.338E+01   91    41s    
   91 :   -4.285E+01     0.89     -4.324E+01   92    41s    
* Finished.  Cost: -42.8457 Gap: 0.8878%
* Termination with relative gap satisfied 
* Timing: 45% spent in upper solver (92 problems solved)
*         2% spent in lower solver (91 problems solved)
*         44% spent in LP-based domain reduction (3064 problems solved)
*         2% spent in upper heuristics (3113 candidates tried)

sol = 

  struct with fields:

    yalmipversion: '20200116'
    matlabversion: '9.1.0.441655 (R2016b)'
       yalmiptime: 1.2070
       solvertime: 29.2820
             info: 'Successfully solved (BMIBNB)'
          problem: 0

Sheida

unread,

Aug 16, 2020, 2:08:11 PM8/16/20

to YALMIP

Dear,

Thanks for your response. The output of my code is attached. It is my first time using YALMIP. Could you let me know why this error happens? Thanks.

Error.png

Sheida

unread,

Aug 16, 2020, 2:32:43 PM8/16/20

to YALMIP

I removed the warning and the following is the output.

Linear scalar (real, 1 variable)
Coefficients range: 1 to 1

* Starting YALMIP global branch & bound.

* Branch-variables : 4
* Upper solver : fmincon
* Lower solver : LINPROG
* LP solver : LINPROG

Node Upper Gap(%) Lower Open

1 : -4.285E+01 82.03 -1.038E+02 2 Improved solution
2 : -4.285E+01 82.03 -1.038E+02 3
3 : -4.285E+01 51.97 -7.363E+01 4
4 : -4.285E+01 51.97 -7.363E+01 5
5 : -4.285E+01 51.97 -7.363E+01 6
6 : -4.285E+01 51.97 -7.363E+01 7
7 : -4.285E+01 22.19 -5.379E+01 8
8 : -4.285E+01 22.19 -5.379E+01 9
9 : -4.285E+01 22.19 -5.379E+01 10
10 : -4.285E+01 22.19 -5.379E+01 11
11 : -4.285E+01 22.00 -5.368E+01 12
12 : -4.285E+01 22.00 -5.368E+01 13
13 : -4.285E+01 22.00 -5.368E+01 14
14 : -4.285E+01 22.00 -5.368E+01 15
15 : -4.285E+01 17.73 -5.137E+01 16
16 : -4.285E+01 17.73 -5.137E+01 17
17 : -4.285E+01 17.73 -5.137E+01 18
18 : -4.285E+01 17.73 -5.137E+01 19
19 : -4.285E+01 16.48 -5.072E+01 20
20 : -4.285E+01 16.48 -5.072E+01 21
21 : -4.285E+01 16.48 -5.072E+01 20 Infeasible
22 : -4.285E+01 16.48 -5.072E+01 19 Infeasible
23 : -4.285E+01 13.97 -4.943E+01 20
24 : -4.285E+01 13.97 -4.943E+01 21
25 : -4.285E+01 13.97 -4.943E+01 22
26 : -4.285E+01 13.97 -4.943E+01 23
27 : -4.285E+01 9.15 -4.705E+01 24
28 : -4.285E+01 9.15 -4.705E+01 25
29 : -4.285E+01 9.15 -4.705E+01 24 Infeasible
30 : -4.285E+01 9.15 -4.705E+01 23 Infeasible
31 : -4.285E+01 7.65 -4.633E+01 24
32 : -4.285E+01 7.65 -4.633E+01 25
33 : -4.285E+01 7.65 -4.633E+01 26
34 : -4.285E+01 7.65 -4.633E+01 27
35 : -4.285E+01 6.55 -4.582E+01 28
36 : -4.285E+01 6.55 -4.582E+01 29
37 : -4.285E+01 6.55 -4.582E+01 30
38 : -4.285E+01 6.55 -4.582E+01 31
39 : -4.285E+01 6.33 -4.571E+01 32
40 : -4.285E+01 6.33 -4.571E+01 33
41 : -4.285E+01 6.33 -4.571E+01 34
42 : -4.285E+01 6.33 -4.571E+01 35
43 : -4.285E+01 5.25 -4.521E+01 36
44 : -4.285E+01 5.25 -4.521E+01 37
45 : -4.285E+01 5.25 -4.521E+01 38
46 : -4.285E+01 5.25 -4.521E+01 39
47 : -4.285E+01 4.40 -4.482E+01 40
48 : -4.285E+01 4.40 -4.482E+01 41
49 : -4.285E+01 4.40 -4.482E+01 42
50 : -4.285E+01 4.40 -4.482E+01 43
51 : -4.285E+01 3.98 -4.463E+01 44
52 : -4.285E+01 3.98 -4.463E+01 45
53 : -4.285E+01 3.98 -4.463E+01 44 Infeasible
54 : -4.285E+01 3.98 -4.463E+01 43 Infeasible
55 : -4.285E+01 3.20 -4.427E+01 44
56 : -4.285E+01 3.20 -4.427E+01 45
57 : -4.285E+01 3.20 -4.427E+01 46
58 : -4.285E+01 3.20 -4.427E+01 47
59 : -4.285E+01 2.55 -4.398E+01 48
60 : -4.285E+01 2.55 -4.398E+01 49
61 : -4.285E+01 2.55 -4.398E+01 50
62 : -4.285E+01 2.55 -4.398E+01 51
63 : -4.285E+01 2.55 -4.398E+01 52
64 : -4.285E+01 2.55 -4.398E+01 53
65 : -4.285E+01 2.55 -4.398E+01 54
66 : -4.285E+01 2.55 -4.398E+01 55
67 : -4.285E+01 1.81 -4.365E+01 56
68 : -4.285E+01 1.81 -4.365E+01 57
69 : -4.285E+01 1.81 -4.365E+01 58
70 : -4.285E+01 1.81 -4.365E+01 59
71 : -4.285E+01 1.79 -4.364E+01 60
72 : -4.285E+01 1.79 -4.364E+01 59 Infeasible
73 : -4.285E+01 1.79 -4.364E+01 60
74 : -4.285E+01 1.79 -4.364E+01 61
75 : -4.285E+01 1.51 -4.351E+01 60 Infeasible
76 : -4.285E+01 1.51 -4.351E+01 61
77 : -4.285E+01 1.51 -4.351E+01 62
78 : -4.285E+01 1.51 -4.351E+01 63
79 : -4.285E+01 1.39 -4.346E+01 64
80 : -4.285E+01 1.39 -4.346E+01 65
81 : -4.285E+01 1.39 -4.346E+01 64 Infeasible
82 : -4.285E+01 1.39 -4.346E+01 63 Infeasible
83 : -4.285E+01 1.28 -4.341E+01 64
84 : -4.285E+01 1.28 -4.341E+01 65
85 : -4.285E+01 1.28 -4.341E+01 66
86 : -4.285E+01 1.28 -4.341E+01 67
87 : -4.285E+01 1.22 -4.338E+01 68
88 : -4.285E+01 1.22 -4.338E+01 69
89 : -4.285E+01 1.22 -4.338E+01 70
90 : -4.285E+01 1.22 -4.338E+01 71
91 : -4.285E+01 1.08 -4.332E+01 72
92 : -4.285E+01 1.08 -4.332E+01 73
93 : -4.285E+01 1.08 -4.332E+01 74
94 : -4.285E+01 1.08 -4.332E+01 75
95 : -4.285E+01 1.04 -4.330E+01 76
96 : -4.285E+01 1.04 -4.330E+01 77
97 : -4.285E+01 1.04 -4.330E+01 78
98 : -4.285E+01 1.04 -4.330E+01 79
99 : -4.285E+01 1.01 -4.329E+01 80
100 : -4.285E+01 1.01 -4.329E+01 81
* Finished. Cost: -42.8457 Gap: 1.0058
* Termination due to iteration limit
* Timing: 23% spent in upper solver (90 problems solved)
* 3% spent in lower solver (98 problems solved)
* 70% spent in LP-based domain reduction (2712 problems solved)

sol =

struct with fields:

yalmipversion: '20200116'

yalmiptime: 0.7760
solvertime: 35.7290
info: 'Maximum iterations or time limit exceeded (BMIBNB)'
problem: 3

Johan Löfberg

unread,

Aug 16, 2020, 2:48:23 PM8/16/20

to YALMIP

you will have to increase bmibnb.maxiter to avoid early termination

btw, you should install a better lp solver for better performance

Sheida

unread,

Aug 16, 2020, 11:47:39 PM8/16/20

to YALMIP

Dear Professor,

Thanks for the useful comments.

I applied your comments. Could you please let me know why my output is not the same as yours. I have some infeasible points, however the problem is solved successfully. Do the infeasible points have negative impact on the final result?

options = sdpsettings('solver','bmibnb','bmibnb.maxiter',1e5,'bmibnb.uppersolver','fmincon');

Here is the output:

Linear scalar (real, 1 variable)

Coefficients range: 1 to 1

* Starting YALMIP global branch & bound.

* Branch-variables : 4

* Upper solver : fmincon

* Lower solver : GUROBI

* LP solver : GUROBI

Node Upper Gap(%) Lower Open

1 : -4.285E+01 82.03 -1.038E+02 2 Improved solution

2 : -4.285E+01 82.03 -1.038E+02 3

3 : -4.285E+01 62.40 -8.262E+01 4

4 : -4.285E+01 62.40 -8.262E+01 5

5 : -4.285E+01 62.40 -8.262E+01 6

6 : -4.285E+01 62.40 -8.262E+01 7

7 : -4.285E+01 44.27 -6.777E+01 8

8 : -4.285E+01 44.27 -6.777E+01 9

9 : -4.285E+01 44.27 -6.777E+01 10

10 : -4.285E+01 44.27 -6.777E+01 11

11 : -4.285E+01 34.68 -6.124E+01 12

12 : -4.285E+01 34.68 -6.124E+01 13

13 : -4.285E+01 34.68 -6.124E+01 14

14 : -4.285E+01 34.68 -6.124E+01 15

15 : -4.285E+01 17.35 -5.118E+01 16

16 : -4.285E+01 17.35 -5.118E+01 17

17 : -4.285E+01 16.60 -5.078E+01 18

18 : -4.285E+01 16.60 -5.078E+01 19

19 : -4.285E+01 15.61 -5.027E+01 20

20 : -4.285E+01 15.61 -5.027E+01 21

21 : -4.285E+01 15.61 -5.027E+01 22

22 : -4.285E+01 15.61 -5.027E+01 23

23 : -4.285E+01 15.40 -5.016E+01 24

24 : -4.285E+01 15.40 -5.016E+01 25

25 : -4.285E+01 9.89 -4.741E+01 26

26 : -4.285E+01 9.89 -4.741E+01 27

27 : -4.285E+01 7.62 -4.632E+01 26 Infeasible

28 : -4.285E+01 7.62 -4.632E+01 27

29 : -4.285E+01 6.83 -4.595E+01 28

30 : -4.285E+01 6.83 -4.595E+01 29

31 : -4.285E+01 6.28 -4.569E+01 30

32 : -4.285E+01 6.28 -4.569E+01 31

33 : -4.285E+01 5.29 -4.523E+01 32

34 : -4.285E+01 5.29 -4.523E+01 33

35 : -4.285E+01 5.29 -4.523E+01 34

36 : -4.285E+01 5.29 -4.523E+01 35

37 : -4.285E+01 5.09 -4.514E+01 36

38 : -4.285E+01 5.09 -4.514E+01 35 Infeasible

39 : -4.285E+01 4.37 -4.480E+01 36

40 : -4.285E+01 4.37 -4.480E+01 37

41 : -4.285E+01 4.28 -4.476E+01 38

42 : -4.285E+01 4.28 -4.476E+01 39

43 : -4.285E+01 3.09 -4.422E+01 40

44 : -4.285E+01 3.09 -4.422E+01 41

45 : -4.285E+01 3.09 -4.422E+01 42

46 : -4.285E+01 3.09 -4.422E+01 43

47 : -4.285E+01 3.08 -4.422E+01 44

48 : -4.285E+01 3.08 -4.422E+01 45

49 : -4.285E+01 3.08 -4.422E+01 46

50 : -4.285E+01 3.08 -4.422E+01 47

51 : -4.285E+01 3.08 -4.422E+01 48

52 : -4.285E+01 3.08 -4.422E+01 49

53 : -4.285E+01 2.31 -4.387E+01 50

54 : -4.285E+01 2.31 -4.387E+01 51

55 : -4.285E+01 2.29 -4.386E+01 52

56 : -4.285E+01 2.29 -4.386E+01 53

57 : -4.285E+01 2.20 -4.382E+01 54

58 : -4.285E+01 2.20 -4.382E+01 55

59 : -4.285E+01 2.20 -4.382E+01 56

60 : -4.285E+01 2.20 -4.382E+01 57

61 : -4.285E+01 2.20 -4.382E+01 58

62 : -4.285E+01 2.20 -4.382E+01 59

63 : -4.285E+01 2.08 -4.377E+01 60

64 : -4.285E+01 2.08 -4.377E+01 61

65 : -4.285E+01 2.08 -4.377E+01 62

66 : -4.285E+01 2.08 -4.377E+01 63

67 : -4.285E+01 1.82 -4.365E+01 64

68 : -4.285E+01 1.82 -4.365E+01 65

69 : -4.285E+01 1.70 -4.360E+01 66

70 : -4.285E+01 1.70 -4.360E+01 67

71 : -4.285E+01 1.52 -4.352E+01 68

72 : -4.285E+01 1.52 -4.352E+01 69

73 : -4.285E+01 1.44 -4.348E+01 70

74 : -4.285E+01 1.44 -4.348E+01 71

75 : -4.285E+01 1.37 -4.345E+01 72

76 : -4.285E+01 1.37 -4.345E+01 73

77 : -4.285E+01 1.36 -4.345E+01 74

78 : -4.285E+01 1.36 -4.345E+01 75

79 : -4.285E+01 1.32 -4.343E+01 74 Infeasible

80 : -4.285E+01 1.32 -4.343E+01 75

81 : -4.285E+01 1.32 -4.343E+01 76

82 : -4.285E+01 1.32 -4.343E+01 77

83 : -4.285E+01 1.28 -4.341E+01 78

84 : -4.285E+01 1.28 -4.341E+01 79

85 : -4.285E+01 1.20 -4.338E+01 80

86 : -4.285E+01 1.20 -4.338E+01 81

87 : -4.285E+01 1.20 -4.338E+01 82

88 : -4.285E+01 1.20 -4.338E+01 83

89 : -4.285E+01 1.19 -4.337E+01 84

90 : -4.285E+01 1.19 -4.337E+01 85

91 : -4.285E+01 1.19 -4.337E+01 86

92 : -4.285E+01 1.19 -4.337E+01 87

93 : -4.285E+01 1.16 -4.336E+01 88

94 : -4.285E+01 1.16 -4.336E+01 89

95 : -4.285E+01 1.11 -4.334E+01 90

96 : -4.285E+01 1.11 -4.334E+01 89 Infeasible

97 : -4.285E+01 1.00 -4.329E+01 90

98 : -4.285E+01 1.00 -4.329E+01 91

99 : -4.285E+01 1.00 -4.329E+01 92

100 : -4.285E+01 1.00 -4.329E+01 93

101 : -4.285E+01 0.98 -4.328E+01 94

* Finished. Cost: -42.8457 Gap: 0.98064

* Termination with relative gap satisfied

* Timing: 38% spent in upper solver (97 problems solved)

* 2% spent in lower solver (105 problems solved)

* 54% spent in LP-based domain reduction (3346 problems solved)

sol =

struct with fields:

yalmipversion: '20200116'

yalmiptime: 0.7370

solvertime: 17.6560

info: 'Successfully solved (BMIBNB)'

problem: 0

Johan Löfberg

unread,

Aug 17, 2020, 2:25:06 AM8/17/20

to YALMIP

you're using a different version/computer/os/..

it has been successfully solved within specified tolerances

Reply all

Reply to author

Forward