Solving a large scale MILP problem with cplex takes long time

Specific Domains Optimization (Mathematical)
,
3

Your language is a bit vague.

If that “large scale MILP problem” is you original problem, then you should form a plan in your mind

  1. how much time can I tolerate

  2. what’s my expected accuracy

For example, if cplex can reduce the relative gap to below 0.05% in 24 hours, and you are happy with it. Then your aim is already achieved. (In your case, cplex spends 1572 seconds to achieve a 8.98% rgap.)

No. You can always deliver your original problem—no matter how large it is—to a black box MIP solver. And typically you had best try solving it directly before you try any customized decomposition methods, because otherwise there are numerous nontrivial issues you may encounter. And much experience is entailed for you to successfully implement them.

For decomposition methods:

  1. From primal side, we have Benders decomposition

  2. From dual side, we have dual decomposition (by relaxing some complicating constraints with Lagrangian multipliers)

  3. Dantzig-Wolfe’s method is merely a dual perspective of the Lagrangian’s method, therefore at least for me, it is overshadowed

1 Like