Originally posted by: angelo_carlino

Hello everybody, I'm trying to solve a MIP problem. Here are the stats:

Problem name         : c:\users\vaio\desktop\1998-2008\input_niet_u2.lp
Objective sense      : Minimize
Variables            :  179361
Objective nonzeros   :  135213
Linear constraints   :  144145  [Less: 109264,  Greater: 5808,  Equal: 29073]
  Nonzeros           : 1404256
  RHS nonzeros       :   39488
SOS                  :    1188  [SOS2: 1188, 10296 members, all continuous]

Variables            : Min LB: 0.0000000        Max UB: all infinite
Objective nonzeros   : Min   : 4.595974e-007    Max   : 19757.02
Linear constraints   :
  Nonzeros           : Min   : 0.002419200      Max   : 3415000.
  RHS nonzeros       : Min   : 0.0001500000     Max   : 1.878877e+007

Looking at these I think the problem should be rather well posed and easy to solve. But during the optimization the mipgap gets stuck around 0.09% for a very long time. After some hours, I stopped it and I got the following info about the solution:

 <header
   problemName="c:\users\vaio\desktop\1998-2008\input_niet_u2.lp"
   solutionName="incumbent"
   solutionIndex="-1"
   objectiveValue="95127.193311499766"
   solutionTypeValue="3"
   solutionTypeString="primal"
   solutionStatusValue="113"
   solutionStatusString="aborted"
   solutionMethodString="mip"
   primalFeasible="1"
   dualFeasible="0"
   MIPNodes="594880"
   MIPIterations="32895356"
   writeLevel="1"/>
 <quality
   epInt="1.0000000000000001e-05"
   epRHS="9.9999999999999995e-07"
   maxIntInfeas="0"
   maxPrimalInfeas="1.4013304960869277e-09"
   maxX="99999"
   maxSlack="11323621.999996215"/>

I know the solution is quite close to the optimal one but I'd like to improve my relative gap. Indeed this is only a modification of another problem that I could solve having a mipgap below 0.01% in a much shorter time (few minutes). The modification was adding some new SOS constraints. Here are the stats and the solution info for the previous problem:

Problem name         : c:\users\vaio\desktop\1998-2008\input_niet_u9.lp
Objective sense      : Minimize
Variables            :  174081
Objective nonzeros   :  135213
Linear constraints   :  142429  [Less: 109264,  Greater: 5808,  Equal: 27357]
  Nonzeros           : 1388944
  RHS nonzeros       :   39356
SOS                  :     660  [SOS2: 660, 5676 members, all continuous]

Variables            : Min LB: 0.0000000        Max UB: all infinite
Objective nonzeros   : Min   : 4.595974e-007    Max   : 19757.02
Linear constraints   :
  Nonzeros           : Min   : 0.002419200      Max   : 3.415000e+012
  RHS nonzeros       : Min   : 0.0001500000     Max   : 1.879616e+013

 <header
   problemName="c:\users\vaio\desktop\1998-2008\input_niet_u9.lp"
   solutionName="incumbent"
   solutionIndex="-1"
   objectiveValue="94653.057453952686"
   solutionTypeValue="3"
   solutionTypeString="primal"
   solutionStatusValue="102"
   solutionStatusString="integer optimal, tolerance"
   solutionMethodString="mip"
   primalFeasible="1"
   dualFeasible="0"
   MIPNodes="9815"
   MIPIterations="337804"
   writeLevel="1"/>
 <quality
   epInt="1.0000000000000001e-05"
   epRHS="9.9999999999999995e-07"
   maxIntInfeas="0"
   maxPrimalInfeas="1.4013304960869277e-09"
   maxX="99999"
   maxSlack="11330969055123.414"/>

So, in the end, is the SOS constraints addition making the problem much harder to solve (I also made changed some of the units of the problem to reduce difference in the coefficients of the problem) ? Should I work on the input problem in order to make it easier for cplex to solve (what should I do then?)? Should I have more patience and wait for it to be solved anyway? Or should I accept solutions for the new problem with a higher relative mipgap threshold?

Thanks for any suggestion.

Best,
Angelo

First of all, your model statistics are not great:

• objective non-zeros range from 1e-7 through 1e4
• matrix non-zeros range from 1e-3 through 1e6
• right-hand side non-zeros range from 1e-4 through 1e7

So the difference is up to 11 orders of magnitude. From this numerical problems would definitely not be a surprise. This may be one of the reasons why CPLEX struggles. With these numbers I recommend setting CPX_PARAM_NUMERICALEMPHASIS.

You may also want to play with the CPX_PARAM_MIPEMPHASIS switch. If you know your feasible solutions are (almost) optimal then a value of 3 (work hard on the dual bound) seems reasonable.

Since CPLEX seems to struggle with the dual bound, you could also think about strengthening your problem so that the LP relaxation becomes stronger.

Originally posted by: angelo_carlino

Thank you very much for the help. Indeed I tried to improve the model (couldn't do much better than before anyway) and used your suggestions on the parameters. I found out the numerical emphasis to be the most significant for the problem.

Cheers,

Angelo