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

Sarang_Balan · February 18, 2025, 11:29am

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

Sarang_Balan · February 18, 2025, 11:38am

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

michael · March 7, 2025, 10:24am

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.