Non-Convex Quadratic Optimization

Introducing Non-Convex Quadratic Optimization in Gurobi 9.0

In this video, you will learn about the new functionality with Gurobi 9.0: Now with a new bilinear solver which allows you to solve non-convex quadratic programming problems (i.e., QPs, QCPs, MIQPs, and MIQCPs) improved performance, and major new features in Gurobi Optimizer and Compute Server.

 

 

Breakthrough New Capability

With the release of Gurobi 9.0’s addition of a new bilinear solver, the Gurobi Optimizer now supports non-convex quadratic optimization. This groundbreaking new capability allows users to solve problems with non-convex quadratic constraints and objectives – enabling them to find globally optimal solutions to classic bilinear pooling and blending problems and continuous manufacturing problems.

 

Business Applications

Companies utilizing mathematical optimization are able to apply non-convex quadratic optimization to a number of industries and problems including:

  • Pooling problem (blending problem is LP, pooling introduces intermediate pools, which lead to bilinear constraints)
  • Petrochemical industry (oil refinery: constraints on ratio of components in tanks)
  • Wastewater treatment
  • Emissions regulation
  • Agricultural / food industry (blending based on pre-mix products)
  • Mining
  • Energy
  • Production planning (constraints on ratio between internal and external workforce)
  • Logistics (restrictions from free trade agreements)
  • Water distribution (Darcy-Weisbach equation for volumetric flow)
  • Engineering design
  • Finance

 

General MINLP:

  • For general MINLP, another important building block is the support to get automatic
    piece-wise linearization of certain standard non-linear univariate functions like y =
    exp(x), y = sin(x), or y = log(x).
  • Gurobi 9.0 allows to use certain standard non-linear univariate functions like y =
    exp(x) or y = sin(x) in a model. These are automatically approximated using piece-wise
    linear functions.
  • Many classes of general MINLPs can be solved by using these non-linear univariate
    functions and approximating multi-variate functions as polynomials. But note that with
    higher degrees of polynomials, the numerics of the problem become more challenging.

 

Standard Pooling Problem:

Pooling problems are common in the petrochemical refining, wastewater treatment, and mining industries. This problem can be regarded as a generalization of the minimum-cost flow problem and the blending problem. We construct a non-convex mixed-integer quadratically-constrained programming (MIQCP) model of this problem, implement this model in the Gurobi Python API, and compute an optimal solution.

 

View Documentation          Join the Community Discussion


 

Related Resources

 

View the Non-Convex Quadratic Optimization Webinar

This video shows one of the major new features in Gurobi 9.0, the new bilinear solver, which allows users to solve problems with non-convex quadratic objectives and constraints such as QPs, QCPs, MIQPs, and MIQCPs.

Download the materials, here.

Jupyter Notebook Modeling Example

Commercial License

New Users: Gurobi allows you to try a free, full-featured, commercial evaluation license for 30 days. During that time, you’ll also get:

  • Free benchmarking services
  • Free model tuning services
  • Access to Gurobi’s world-class technical support
  • Two free hours of one-on-one consulting services

Note to Existing Customers Affected by COVID-19: Please use this form to request a temporary license, if you are experiencing difficulties accessing the Gurobi Optimizer.

 

Note to Academic Users: Academic users at recognized degree-granting institutions can get a free academic license. You can learn about our academic program here. Can’t view the form? Please click here to open it in a new window.

Thank you! The information has been submitted successfully.