Solver not finding solution for simple MINLP formulation of the original MILP problem

GAMSPy
,
1

Hi everyone,

I have an MIP problem with several binary, positive, and variable constraints. The MILP formulation of the problem with a linear constraint is solved very easily, even with a model size of 100k+ equations. The objective function looks like this
Z = a + b, where a and b are the sum of binary variables set elsewhere in the model.

The MINLP formulation objective function is a simple change, turning the objective function into Z = a/b. Now, this model is solved relatively easily (using XPRESS) in small model sizes and in large model sizes when constraints are not tight.

However, in some cases where the constraints are tight, the MINLP fails to solve for any solution (declared infeasible), while the same problem in MILP solves for many different solutions under the same parameters/constraints.

I’m not sure if this forum provides advice on the model itself, but I wanted to see if there are any specific solver settings that I might have to play around with to force the MINLP version of the solver to come up with a solution.

Thanks,

Sarang

2

Here is some output data. This exact same setup solves perfectly well in an MILP formulation with the exact constraints.

Presolved problem size
   linear:    57846 rows, 48044 columns, 197024 linear coefficients
   nonlinear: 1 coefficients, 3 tokens
              1 mul             0 div         0 sqrt
Problem is nonlinear presolved
FICO Xpress v9.4.0, Hyper, solve started 11:36:32, Feb 18, 2025
Control settings used:
LPITERLIMIT = 2147483647
RANDOMSEED = 293
MIPADDCUTOFF = 0
MIPRELCUTOFF = 0
MIPABSSTOP = 0
MIPRELSTOP = .0001
ELIMTOL = .01
TIMELIMIT = 300
LOCALSOLVER = 0
MULTISTART_THREADS = -1
NLPMAXTIME = 0
XSLP_ECHOXPRSMESSAGES = 1
NLPCALCTHREADS = -1
NLPTHREADS = -1
XSLP_OBJSENSE = -1
Maximum expanded nl-formula size: 3  (row 'R101950')
Total tokens: 3
  12  parallel calculation threads
  Jacobian: symbolic differentiation
           1 base AD formula, 3 average complexity
           2 in the Jacobian, 1 average complexity
Initial point integer infeasible:         1.0000
 ------------------- Calling global solver ----------------- 
FICO Xpress v9.4.0, Hyper, solve started 11:36:32, Feb 18, 2025
Heap usage: 24MB (peak 24MB, 21MB system)
Maximizing Nonconvex-MIQCP b1 using up to 12 threads and up to 24GB memory
Original problem has:
     57846 rows        48044 cols       197024 elements     23520 entities
Presolved problem has:
     57846 rows        47064 cols       192125 elements     23520 entities
LP relaxation tightened
Presolve finished in 0 seconds
Heap usage: 42MB (peak 82MB, 21MB system)
Coefficient range                    original                 solved        
  Coefficients   [min,max] : [ 5.00e-07,  2.15e+06] / [ 9.06e-03,  2.62e+02]
  RHS and bounds [min,max] : [ 1.00e-07,  4.42e+09] / [ 1.22e-11,  3.24e+07]
  Objective      [min,max] : [ 1.00e+00,  1.00e+00] / [ 1.00e+00,  1.00e+00]
Autoscaling applied Curtis-Reid scaling
Will try to keep branch and bound tree memory usage below 22.7GB
Starting concurrent solve with dual (1 thread) and barrier (11 threads)
              Concurrent-Solve,   0s
            Dual                      Barrier      
    objective   dual inf                           
 D   .0000000  1.0000000 |                         
                         |                         
------ unbounded ------- | ----- interrupted ------
Concurrent statistics:
           Dual: 0 simplex iterations, 0.01s
        Barrier: 0 barrier and 0 simplex iterations, 0.04s
            Barrier used 11 threads 11 cores
Problem is dual infeasible
 *** Search completed ***
Problem is unbounded
Uncrunching matrix

*** Problem unbounded, attempting to regularise original variables***
 ------------------- Calling global solver ----------------- 
FICO Xpress v9.4.0, Hyper, solve started 11:36:33, Feb 18, 2025
Heap usage: 24MB (peak 24MB, 21MB system)
Maximizing Nonconvex-MIQCP b1 using up to 12 threads and up to 24GB memory
Original problem has:
     57846 rows        48044 cols       197024 elements     23520 entities
Presolved problem has:
     57846 rows        47064 cols       192125 elements     23520 entities
LP relaxation tightened
Presolve finished in 0 seconds
Heap usage: 42MB (peak 82MB, 21MB system)
Coefficient range                    original                 solved        
  Coefficients   [min,max] : [ 5.00e-07,  2.15e+06] / [ 1.63e-02,  2.85e+02]
  RHS and bounds [min,max] : [ 1.00e-07,  1.30e+06] / [ 1.22e-11,  1.00e+06]
  Objective      [min,max] : [ 1.00e+00,  1.00e+00] / [ 1.00e+00,  1.00e+00]
Autoscaling applied Curtis-Reid scaling
Will try to keep branch and bound tree memory usage below 22.7GB
Starting concurrent solve with dual (1 thread) and barrier (11 threads)
              Concurrent-Solve,   0s
            Dual                      Barrier      
    objective   dual inf        p.obj.     d.obj.  
 D  999998.90   .0000000 |  B -999077.44  1.794E+08
 D  1000102.1   .0000000 |  B  610567.25  3.273E+08
 D  1000101.7   .0000000 |  B  950280.07  5958358.7
 D  1000101.6   .0000000 |           crossover     
 D  1000100.6   .0000000 |           crossover     
 D  1000098.3   .0000000 |           crossover     
 D  1000097.0   .0000000 |           crossover     
 D  1000096.4   .0000000 |           crossover     
 D  1000096.0   .0000000 |           crossover     
 D  1000094.9   .0000000 |           crossover     
 D  1000093.8   .0000000 |           crossover     
 D  1000093.2   .0000000 |           crossover     
 D  1000092.7   .0000000 |           crossover     
 D  1000092.2   .0000000 |           crossover     
 D  1000092.0   .0000000 |           crossover     
 D  1000089.2   .0000000 |           crossover     
 D  1000088.7   .0000000 |           crossover     
 D  1000088.5   .0000000 |           crossover     
 D  1000088.4   .0000000 |           crossover     
 D  1000088.3   .0000000 |  P  1000000.0  25636.560
              Concurrent-Solve,   3s
            Dual                      Barrier      
    objective   dual inf       objective   sum inf 
 D  1000087.0   .0000000 |  P  1000000.0  13296.245
 D  1000087.0   .0000000 |  P  1000000.0  12996.489
 D  1000086.6   .0000000 |  P  1000000.0  12996.475
 D  1000086.4   .0000000 |  P  1000000.0  12269.712
 D  1000085.8   .0000000 |  P  1000000.0  12269.669
 D  1000085.7   .0000000 |  P  1000000.0  12269.669
 D  1000085.7   .0000000 |  P  1000000.0  12269.669
 D  1000085.7   .0000000 |  P  1000000.0  12269.359
 D  1000085.6   .0000000 |  P  1000000.0  12269.359
 D  1000085.6   .0000000 |  P  1000000.0  12269.353
 D  1000085.6   .0000000 |  P  1000000.0  12269.348
 D  1000085.6   .0000000 |  P  1000000.0  12266.801
 D  1000085.6   .0000000 |  P  1000000.0  12262.632
 D  1000085.6   .0000000 |  P  1000000.0  12253.901
 D  1000085.6   .0000000 |  P  1000000.0  12251.118
 D  1000085.4   .0000000 |  P  1000000.0  12245.980
 D  1000085.3   .0000000 |  P  1000000.0  12242.632
 D  1000084.9   .0000000 |  P  1000000.0  12239.926
 D  1000084.2   .0000000 |  P  1000000.0  12232.261
 D  1000084.1   .0000000 |  P  1000000.0  12224.610
------ infeasible ------ | ----- interrupted ------
Concurrent statistics:
           Dual: 13903 simplex iterations, 2.19s
        Barrier: 26 barrier and 31963 simplex iterations, 4.49s
            Barrier used 11 threads 11 cores
, crossover used 8 threads
Problem is infeasible
 *** Search completed ***
Problem is integer infeasible
Uncrunching matrix
  Converged solution is outside feasibility tolerance
Problem is nonlinear postsolved
Heap usage: 126MB (peak 211MB, 2503KB system)
NLP solve locally infeasible
  Observed primal integral :  100.000%
  Total / SLP / LP time :     5.165s /      .000s /      .000s
  Time checks (ticks) :        9074 
*** Search completed ***
*** Bounding box was applied to original variables, infeasibility can only be guaranteed up to bounds***
--- Reading solution for model b1
***
*** Solver did not provide marginals for model b1
3

It seems like the issue you’re encountering with your MINLP formulation could be related to the solver’s ability to handle non-linearities effectively, especially when the constraints are tight. In your MILP formulation, the problem is linear and can be solved efficiently even with a large model size, but once you switch to the MINLP version with a non-linear objective function (a/b), the solver might struggle due to the non-linear nature of the objective, especially when the constraints are tight. This can result in the solver declaring the problem infeasible even though it might be feasible under the MILP formulation. To address this, you might want to adjust the solver’s settings to better handle non-linearities. Key settings to experiment with include tightening the tolerance on feasibility and optimality, improving the initial feasible solution (if available), and increasing the solver’s iteration limits or branch-and-bound settings to allow for more extensive exploration of the solution space. You can also try using advanced techniques like adding disjunctions or reformulating the non-linear part of the problem to make it more tractable for the solver. Additionally, ensure that your model is properly scaled, as numerical instability can sometimes exacerbate issues with tight constraints. These solver adjustments should improve the likelihood of finding a feasible solution in the MINLP context.

4

Hi,

Thank you for your reply so far. I was hoping you could take a look at my solve output and see if there are any obvious improvements regarding B&B settings.

Reading Problem b1
Problem Statistics
109817 (      0 spare) rows
94109 (      0 spare) structural columns
342128 (      0 spare) non-zero elements
1 quadratic elements in 1 quadratic constraints
MIP Entity Statistics
40180 entities        0 sets        0 set members
Original problem size
linear:    109817 rows, 94109 columns, 342128 linear coefficients
quadratic: 0 in obj, 1 rows, 1 in rows
Nonlinear presolve
converted 1 quadratic matrix to a formula
simplify removed 2 tokens
linear presolve removed 46067 rows, 42144 columns, 124476 linear coefficients
bound tightening reduced 23 bounds
Presolved problem size
linear:    63750 rows, 51966 columns, 217652 linear coefficients
nonlinear: 1 coefficients, 3 tokens
1 mul             0 div         0 sqrt
Problem is nonlinear presolved
FICO Xpress v9.4.0, Hyper, solve started 7:22:55, May 8, 2025
Control settings used:
LPITERLIMIT = 2147483647
GLOBALTREENLPCUTS = 1000
MIPADDCUTOFF = 0
MIPRELCUTOFF = 0
MIPABSSTOP = 0
MIPRELSTOP = .0001
TIMELIMIT = 1000
LOCALSOLVER = 0
MULTISTART\_THREADS = -1
NLPMAXTIME = 0
XSLP\_ECHOXPRSMESSAGES = 1
NLPCALCTHREADS = -1
NLPTHREADS = -1
XSLP\_OBJSENSE = 1
Maximum expanded nl-formula size: 3  (row 'R109817')
Total tokens: 3
12  parallel calculation threads
Jacobian: symbolic differentiation
1 base AD formula, 3 average complexity
2 in the Jacobian, 1 average complexity
Initial point integer infeasible:         1.0000
\------------------- Calling global solver -----------------
FICO Xpress v9.4.0, Hyper, solve started 7:22:55, May 8, 2025
Heap usage: 26MB (peak 26MB, 21MB system)Node BestSol
Minimizing Nonconvex-MIQCP b1 using up to 12 threads and up to 24GB memory
Original problem has:
63750 rows        51966 cols       217652 elements     25480 entities
Presolved problem has:
63750 rows        50986 cols       212753 elements     25480 entities
LP relaxation tightened
Presolve finished in 0 seconds
Heap usage: 46MB (peak 89MB, 21MB system)
Coefficient range                    original                 solved
Coefficients   \[min,max] : \[ 1.05e-04,  1.14e+06] / \[ 9.67e-03,  1.39e+02]
RHS and bounds \[min,max] : \[ 1.00e+00,  5.38e+09] / \[ 1.00e+00,  1.39e+08]
Objective      \[min,max] : \[ 1.00e+00,  1.00e+00] / \[ 1.00e+00,  1.00e+00]
Autoscaling applied Curtis-Reid scaling
Will try to keep branch and bound tree memory usage below 22.7GB
Starting concurrent solve with dual (1 thread) and barrier (11 threads)
Concurrent-Solve,   0s
Dual                      Barrier
objective   dual inf        p.obj.     d.obj.
D   .0931590   .0000000 |  B  91817.778 -9.340E+08
D   .1584322   .0000000 |  B  1013.5648 -1.346E+08
D   .9737257   .0000000 |  B  101.91862 -31678011.
D  2.1781849   .0000000 |  B  3.6581490 -68662.343
D  2.6065650   .0000000 |  B   .0091337  -.0317947
D  3.2496161   .0000000 |  B   .0034306   .0012992
D  3.6800118   .0000000 |  B   .0027068   .0023425
D  3.9613194   .0000000 |           crossover
D  4.2853768   .0000000 |           crossover
D  4.6092796   .0000000 |           crossover
D  4.8721586   .0000000 |           crossover
D  5.0239525   .0000000 |           crossover
D  5.1872070   .0000000 |           crossover
D  5.3789695   .0000000 |           crossover
D  5.5617044   .0000000 |           crossover
D  5.8175543   .0000000 |           crossover
D  5.9866128   .0000000 |           crossover
D  6.1381061   .0000000 |           crossover
D  6.2528176   .0000000 |           crossover
D  6.3730321   .0000000 |           crossover
Concurrent-Solve,   3s
Dual                      Barrier
objective   dual inf       objective   sum inf
D  6.4393939   .0000000 |           crossover
D  6.4477140   .0000000 |           crossover
D  6.5961858   .0000000 |           crossover
D  6.8657506   .0000000 |           crossover
D  6.9863269   .0000000 |           crossover
D  7.1160136   .0000000 |           crossover
D  7.2880355   .0000000 |           crossover
D  7.8016040   .0000000 |           crossover
D  7.9584096   .0000000 |           crossover
D  8.2814295   .0000000 |           crossover
D  8.5070806   .0000000 |           crossover
D  8.7279044   .0000000 |           crossover
D  8.9581450   .0000000 |           crossover
D  9.1753014   .0000000 |           crossover
\----- interrupted ------ | ------- optimal --------
Concurrent statistics:
Dual: 15564 simplex iterations, 5.41s
Barrier: 60 barrier and 8084 simplex iterations, 5.40s
Barrier used 11 threads 11 cores
, crossover used 8 threads
Optimal solution found

Its         Obj Value      S   Ninf  Nneg        Sum Inf  Time
0           .002657      P      0     0        .000000     5
Barrier solved problem
60 barrier and 8084 simplex iterations in 5.42 seconds at time 5
Final objective                       : 2.656930806173920e-03
Max primal violation      (abs/rel) :       0.0 /       0.0
Max dual violation        (abs/rel) : 1.084e-18 / 8.248e-20
Max complementarity viol. (abs/rel) :       0.0 /       0.0
Starting root cutting & heuristics
Deterministic mode with up to 1 additional thread

Its Type    BestSoln    BestBound   Sols    Add    Del     Gap     GInf   Time
Heuristic s running ( 20323 LP iterations in    0.7 seconds)
1  K                    .004139      0   2010      3              414     25
2  K                    .004349      0   5228    866             1223     27
3  K                    .004909      0   5175   2640             1170     30
4  K                    .004935      0   6612   3853             1316     33
5  K                    .005349      0   7697   4945             1391     36
6  K                    .005432      0   7813   6166             1411     40
7  K                    .005703      0   7704   6468             1401     43
8  K                    .005751      0   7815   6737             1419     47
9  K                    .006261      0   7757   6534             1375     50
10  K                    .006350      0   7506   6311             1398     53
11  K                    .006603      0   7384   6484             1246     56
12  K                    .006920      0   7287   6468             1265     59
13  K                    .006958      0   7256   6672             1245     62
14  K                    .006958      0   7384   6452             1246     65
15  K                    .006958      0   7359   6181             1348     70
16  K                    .007485      0   7447   7703             1295     73
17  K                    .007566      0   7103   5936             1192     75
18  K                    .007566      0   7190   6078             1216     80
19  K                    .007978      0   7399   7082             1251     83
20  K                    .008007      0   7201  24112             1145     85
21  G                    .008355      0   3426      0             1135     87
22  G                    .008510      0   1720   5141             1071     88
Heuristic s running ( 20005 LP iterations in    1.4 seconds)
Heuristic search 'R' started
Heuristic search 'R' stopped

Cuts in the matrix         : 10645
Cut elements in the matrix : 89170
Starting tree search.
Deterministic mode with up to 12 running threads and up to 32 tasks.
Heap usage: 179MB (peak 264MB, 22MB system)


Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
   1                   .008513      0      2      1             1059    111


Will try to keep branch and bound tree memory usage below 21.4GB
2                   .008513      0      2      3             1011    122
3                   .008513      0      3      4             1003    131
4                   .008513      0      4      4             1004    133
5                   .008513      0      5      3             1035    137
6                   .008978      0      6      4             1014    138
7                   .008978      0      7      5              997    143
8                   .008978      0      8      6              952    143
9                   .008978      0      9      6              994    143
Will try to keep branch and bound tree memory usage below 20.3GB
10                   .008978      0     10      5             1010    144
20                   .008978      0     19      7             1001    145
30                   .008978      0     28      8              909    151
40                   .008978      0     35     13              924    159
50                   .008978      0     43      8              942    162
60                   .008978      0     52     12              972    171
70                   .008978      0     62     12              972    174
80                   .008978      0     72     23              892    176
90                   .008978      0     81     22              956    180
100                   .008978      0     89     12              994    182
Elapsed time (sec): 213, estimated tree completion: 0.00000
Heap usage: 179MB (peak 264MB, 46MB system)
B\&B tree size: 8.4MB total


Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
 200                   .008978      0    191     63              817    213
 300                   .008978      0    276     40              932    239
 400                   .008978      0    350     53              925    282


Will try to keep branch and bound tree memory usage below 21.9GB
500                   .008978      0    427     88              968    632