Solving quadratic integer programming (QIP) problems on optimization solver machines

A non-transitory computer-readable storage medium configured to store instructions that, in response to being executed, cause a system to perform operations, the operations comprising:

• receiving a Quadratic Integer Programming (QIP) problem comprising an objective function and a set of constraints on integer variables associated with the objective function, the received QIP problem is a portfolio allocation problem for an investor portfolio holding a number of assets;
• obtaining an approximation of the QIP problem by relaxing the QIP problem;
• generating an approximate solution by solving the obtained approximation;
• determining whether the number of assets is greater than a threshold number;
• reformulating the portfolio allocation problem as a Closest Vector Problem (CVP) in lattices when a determination is made that the number of assets in the investor portfolio is below the threshold number;
• solving the CVP problem to output an integral solution of the portfolio allocation problem;
• generating a Quadratic Unconstrained Binary Optimization (QUBO) formulation of the QIP problem based on the generated approximate solution and the received QIP problem when a determination is made that the number of assets in the investor portfolio is above the threshold number;
• submitting the generated QUBO formulation to an optimization solver machine;
• receiving, from the optimization solver machine, a solution of the submitted QUBO formulation;
• and
• publishing an integral solution of the received QIP problem on a user device based on the received solution, the integral solution of the portfolio allocation problem includes the set-number of assets to be bought or sold for each asset type in the investor portfolio such that an investment risk associated with the investor portfolio is reduced and an investment return associated with the investor portfolio is increased.

A system, comprising:

• a processor configured to:
• receive a Quadratic Integer Programming (QIP) problem comprising an objective function and a set of constraints on integer variables associated with the objective function, the received QIP problem is a portfolio allocation problem for an investor portfolio holding a number of assets;
• obtain an approximation of the QIP problem by relaxing the QIP problem;
• generate an approximate solution by solving the obtained approximation;
• determine whether the number of assets is greater than a threshold number;
• reformulate the portfolio allocation problem as a Closest Vector Problem (CVP) in lattices when a determination is made that the number of assets in the investor portfolio is below the threshold number;
• solve the CVP problem to output an integral solution of the portfolio allocation problem;
• generate a Quadratic Unconstrained Binary Optimization (QUBO) formulation of the QIP problem based on the generated approximate solution and the received QIP problem when a determination is made that the number of assets in the investor portfolio is above the threshold number;
• submit the generated QUBO formulation to an optimization solver machine;
• receive, from the optimization solver machine, a solution of the submitted QUBO formulation;
• and
• publish an integral solution of the received QIP problem on a user device based on the received solution, the integral solution of the portfolio allocation problem includes the set-number of assets to be bought or sold for each asset type in the investor portfolio such that an investment risk associated with the investor portfolio is reduced and an investment return associated with the investor portfolio is increased.