Skip to main content

Is it possible to get the exact solution of a large-scale convex quadratic programming problem (quadratic objective, linear inequality constraints)?




  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Ximeng Fan,

    As often, the answer is: It depends!

    The first question is what "large-scale" actually means for you (in terms of numbers of variables and constraints)?
    We have seen models with millions of variables and constraints that can be solved quite easily, and we have seen small models that are still open. It highly depends on the internal structure of the model which is not easy to identify and to describe.

    If your model is a convex QP, then current barrier implementations are quite good at solving huge models to global optimality.
    If you have the model at hand, it is usually not much effort to just throw it to a solver (preferably Gurobi ;)) and see what happens. You might be surprised what current solvers are able to do, provided that you have enough memory in your machine in case of large models.

    Best regards,

  • ximeng fan
    First Comment
    First Question

    Hi Mr. Mario,

    Yes, I have been using Gurobi for a long time. What I am confused about is that in our courses, we were asked to manually solve small-scale quadratic programming problems (with the quadratic objective and linear inequality constraints), a similar example can be found here , we can get the exact solution of the problem (meaning that it is exact the optimal solution with zero errors).

    I suspect that for large-scale (maybe 2000 variables and 10000 constraints) problems, we should also be able to get an 'exact solution' if it follows the reqirements:1, strictly convex; 2, having the format of quadratic objective and linear inequality constraints.

    But as far as I know, the interior point method is an iterative method to get a near-optimal solution. The iterations will terminate when the difference between two iterations is smaller than the setting tolerance (usually $10^{-7}$). So I wonder if is it possible to have the exact solution to the aforementioned problems,and how expensive to get the exact solution (in terms of the computation). 


Please sign in to leave a comment.