CODEWITHSUNDEEP
optimizationcombinatoricsdiscrete-mathematicscplexinteger-programming
martin
martin

Reputation: 775

Why does CPlex solve this mixed integer linear program so incredibly fast?

I am working on an optimization problem where I want to find resource-activity assignment based on skill restrictions (not all resources have all skills for the demands d), resource restrictions (resources have a limited presence p) and an assignment restriction l limiting the number of resources assigned to an activity. I want to maximize the sum of weights w of all selected activities. The model is depicted here:

enter image description here

Now I fed this into CPlex and it solves gigantic instances in a very short amount of time as long as I allow heuristics (1000 activities, 50 resources, 5 skills within about 10 sec), even though there is a huge possible number of selected issues AND a huge number of possible assignments for each activity.

Why is this problem so easy for CPlex? Is there some kind of easily solvable underlying problem that I am missing?

edit: typical output of one of my solver runs:

Tried aggregator 1 time.
MIP Presolve eliminated 3051 rows and 64954 columns.
MIP Presolve modified 49950 coefficients.
Reduced MIP has 52001 rows, 236046 columns, and 662190 nonzeros.
Reduced MIP has 47952 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.61 sec. (276.60 ticks)
Probing time = 0.38 sec. (12.12 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 1323 rows and 62181 columns.
MIP Presolve modified 3366 coefficients.
Reduced MIP has 50678 rows, 173865 columns, and 474324 nonzeros.
Reduced MIP has 47952 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.78 sec. (334.49 ticks)
Probing time = 0.26 sec. (9.19 ticks)
Tried aggregator 1 time.
Reduced MIP has 50678 rows, 173865 columns, and 474324 nonzeros.
Reduced MIP has 47952 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.49 sec. (220.07 ticks)
Probing time = 0.36 sec. (10.46 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 2.86 sec. (1101.00 ticks)
    Nodes                                         Cuts/


 Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                            7.0000     5631.0000     3104     --- 
      0     0     2265.4000     2        7.0000     2265.4000     3104     --- 
*     0+    0                         2265.0000     2265.4000     3107    0.02%
*     0     0      integral     0     2265.0000     2265.4000     3107    0.02%
Elapsed time = 7.59 sec. (2779.25 ticks, tree = 0.00 MB, solutions = 2)

Cover cuts applied:  1

Root node processing (before b&c):
  Real time             =    7.61 sec. (2792.47 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    7.61 sec. (2792.47 ticks)

Upvotes: 1

Views: 1298

Answers (1)

Yongxiang Zhang
Yongxiang Zhang

Reputation: 11

I think that's because the form of your model is relatively simple, such as the objective function, and the model scale is rather small. You can test CPLEX with more complicated examples. I used to solve a MIP model with more than 800 thousand constraints and 300 thousand variables.

Upvotes: 1

Related Questions