Skip to main content

MIP takes too long to solve

Answered

Comments

5 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Jean,

    It is quite hard to guess what might help here from just looking at the model. Could you please share the model? This way I could have a look and experiment a bit. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum. Please also have a look at the Knowledge Base article How do I write an MPS model from a third party API? to produce an MPS file you can share.

    Best regards, 
    Jaromił

    0
  • Jean Jaci
    First Comment
    First Question

    Hello, Jaromił.

    I apologize for the delayed response, I had some matters to attend to in the past few days. I've uploaded the model to Gurobi, and the file is named Jean_model.mps. The compressed file is titled Jean_model.rar. While I simplified the model due to an excess of decision variables in the previous version, solving still requires an exceptionally long time. I'm hopeful you can assist in reviewing the model for possible improvements to enhance solving speed. Thank you very much for your help.

    Best regards,

    Jean

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Jean,

    Thank you for the model. The objective of your model has over 8 million binary product terms. Each product of binary variables is comparable to an additional binary variables. This would mean that your model is comparable to one with over 8 million binary variables. It is no surprise that it takes an extremely long time to converge.

    The best way to reduce complexity would be to perform a manual presolve step where you try to remove a big part of the bilinear terms. For example, you could remove all terms with a small coefficient, which is let's say \(< 10^{-3}\). You could also try to use your application knowledge to remove even more of the products.

    If you are only interested in a good feasible point, I would recommend using the NoRelHeurTime parameter. This parameter will activate the No Relaxation heuristic which searches for feasible points even before a first relaxation is solved. I would set it to some large value like 3600 (= 1 hour). I am not very optimistic about improving the dual bound.

    What surprised me is that the dual can attain negative values. I would have thought that since you are trying to minize the \(||\cdot ||_2\) norm, the objective should always be \(\geq 0\). Maybe adding a contraint

    Objfunction >= 0

    may help.

    Best regards, 
    Jaromił

    0
  • Jean Jaci
    First Comment
    First Question

    Hi Jaromił,

    Thank you very much for your suggestions. I attempted to remove terms with small coefficients, but many binary product terms still remain, leading to prolonged convergence times. I also tried using the NoRelHeurTime parameter, but the improvement was minimal. I noticed that when using Gurobi to solve MIP models with branch-and-bound, the first step is Root relaxation, which yields an objective function value. I am now interested in examining the values of individual decision variables (x) when this objective function value is achieved. Is it possible to obtain this information?

    Another approach I'm considering is relaxing the model. I find the constraint of decision variables being binary too restrictive, potentially resulting in suboptimal solutions. Therefore, I am thinking of converting the decision variables to continuous variables. For example, if previously my first constraint was x1 + x2 + ... + x64 = 1, where x1, ..., x64 are binary variables, I would modify the constraint to x1 + x2 + ... + x64 < 1. In this case, x1, ..., x64 would be continuous variables, and the maximum value among them must be significantly greater than the others. For instance, assuming the maximum value is xk, I could set a threshold xi < 0.001 * xk for i ≠ k. I am aware that Gurobi can solve non-convex models, but I am unsure if this constraint formulation can be expressed using Gurobi.

    One more question: Does Gurobi in Matlab support defining decision variables of complex type? I observed in the Gurobi MATLAB API Overview that the variable types mentioned include continuous variables, integer variables, semi-continuous variables, and semi-integer variables.

    Thank you very much for your assistance.

    Best regards,

    Jean

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Jean,

    I also tried using the NoRelHeurTime parameter, but the improvement was minimal.

    Interesting, on my end running the NoRel heuristic for ~1800 seconds improved the primal bound a lot. It went down to around ~7. Do you have a log output of such a NoRel run which you could share? My impression was that the dual bound will not improve quickly and thus, I think that searching for a better feasible point is the best option here. You could then just terminate after some given TimeLimit and use the best solution found so far even without an optimality proof. Of course only if your application allows for this.

    I noticed that when using Gurobi to solve MIP models with branch-and-bound, the first step is Root relaxation, which yields an objective function value. I am now interested in examining the values of individual decision variables (x) when this objective function value is achieved. Is it possible to obtain this information?

    Yes, you can implement a callback and use the cbGetNodeRel method to get the relaxation solution point. I recommend having a look at the callback.py example. Note that the MATLAB API does not support callbacks. In MATLAB, you could use the gurobi_relax function if your model was a MIP. However, your model has bilinear terms and these are not relaxed by the gurobi_relax function. In this case, the MATLAB API is limited and I would recommend to switch to our Python API if possible for this task. You could still generate your model in MATLAB and just read it in via the read function from Python to not having to rewrite your model building code.

    Another approach I'm considering is relaxing the model. I find the constraint of decision variables being binary too restrictive, potentially resulting in suboptimal solutions. Therefore, I am thinking of converting the decision variables to continuous variables. For example, if previously my first constraint was x1 + x2 + ... + x64 = 1, where x1, ..., x64 are binary variables, I would modify the constraint to x1 + x2 + ... + x64 < 1. In this case, x1, ..., x64 would be continuous variables, and the maximum value among them must be significantly greater than the others. For instance, assuming the maximum value is xk, I could set a threshold xi < 0.001 * xk for i ≠ k. I am aware that Gurobi can solve non-convex models, but I am unsure if this constraint formulation can be expressed using Gurobi.

    Strict inequalities are not supported in Gurobi. In order to model a \( ...< 1 \) inequality, you would have to introduce a finite positive threshold \(\epsilon>0\) and formulate your constraint as \( ...\leq 1 - \epsilon\). \(\epsilon\) should be at least one order of magnitude larger than the default FeasibilityTol value to avoid numerical issues.

    One more question: Does Gurobi in Matlab support defining decision variables of complex type? I observed in the Gurobi MATLAB API Overview that the variable types mentioned include continuous variables, integer variables, semi-continuous variables, and semi-integer variables.

    No, Gurobi does not support complex numbers. As far as I know, only so-called Hermitian solvers support complex numbers natively. Unfortunately, I cannot help furthere here as I have only very little knowledge about this field of optimization.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.