Skip to main content

(Believed to be Optimal) Solution found super quickly, takes forever to certify it with dual



1 comment

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Gabriel,

    Improving the dual bound is often the hardest part of a nonconvex optimization run. Especially when the number of bilinear terms is big (which it is in your instance 17160 bilinear terms).

    In your case, it looks like you should try to provide tight variable bounds for all variables participating in nonlinear terms, i.e., for all variables occuring in a \(x\cdot y\) and \(x^2\) term. These bounds can be motivated by the practical application you are modelling or simply by an educated guess, e.g., "I will never produce more than 100 items of product X". This should already improve the dual bound.

    You could also try reformulating your nonlinear terms. For example, it does make a difference to model

    z &= x_1 + y_1\\
    u &= x_2 + y_2\\
    w &= z\cdot u


    w = x_1\cdot x_2 + x_1 \cdot y_2 + y_1\cdot x_2 + y_1 \cdot y2

    Unfortunately, it is most often not possible to tell which of the two formulations works best for a particular model. Thus, you would have to experiment with different formulations yourself.

    Best regards, 


Please sign in to leave a comment.