Technology
9 minute read

HorusLP-Gurobi: High Level Optimization Architecture for Gurobi

Sean is a passionate polyglot developer with extensive experience in full-stack web development, system administration, and data science. He has developed everything from machinery interfaces to market intelligence software.

As optimization technologies become more sophisticated, commercial solvers have started to play an increasingly important role in the industry. Compared to open-source solvers, commercial solutions tend to have more features for solving complex optimization models such as advanced presolve, warm starting, and distributed solve.

One of the most popular commercial solvers in the market is Gurobi, named after the cofounders Zonghao Gu, Edward Rothberg, and Robert Bixby, each a pioneer in the commercial solver space. Gurobi has powered many high-profile optimization projects in recent history including the FCC’s bandwidth allocation project and Pennsylvania State Prison’s prisoner reassignment project.

Today, we will look at how HorusLP, a software package that provides a high-level declarative interface for optimization modeling, integrates with Gurobi’s API to bring an intuitive modeling experience to users while harnessing Gurobi’s most advanced features.

Optimization: A Quick Refresher

For those who are not familiar with optimization or operations research, optimization refers to a collection of mathematical techniques that finds the optimal values of variables within a system of equations subject to a system of constraints. If the above sentence sounds a bit dry, perhaps an example will help illustrate.

Suppose you had a knapsack with 15 pounds of carrying capacity. You have in front of you a few items, each with a specific weight and monetary value:

  1. Camera: weight 2 lbs, value $5
  2. Figurine: weight 4 lbs, value $7
  3. Cider: weight 7 lbs, value $2
  4. Horn: weight 10 lbs, value $10.

You want to choose items to place into your knapsack such that the total weight stays below 15lbs but the value is maximized. (If you require more context on why we’re sticking high-value items into a knapsack, you’re encouraged to use your imagination for a narrative. Good candidate narratives include rescuing things from a fire and estate auctions… or some nefarious activities we’d rather not mention.)

We can formulate the problem as the following optimization problem:

Let
 // Each variable stands for whether we put the item into the knapsack
Camera = {0, 1}
Figurine = {0, 1}
Cider = {0, 1}
Horn = {0, 1}

// Maximize dollar value
Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn
// Weight must stay below 15 pounds
2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Once we have formulated this problem, we can apply optimization techniques to find the best items to place into our knapsack. You can find an example of the solution from my earlier articles on solving optimization problems using Python and solving optimization problems using the core HorusLP API.

The underlying mathematical technique is quite fascinating, but outside of the scope of this article. If you’d like to find out more, I recommend looking here and here, both courtesy of Gurobi.

Gurobi

While the earliest optimization problems were solved by teams of mathematicians working with calculators, most optimization problems today are solved using specialized software called solvers. While most solvers are generally able to find solutions of majority of well-formulated linear and integer programming problems, some solvers are much more capable than others. They can solve classes of problems that others cannot solve, solve problems more quickly by applying cutting-edge mathematics, or solve large, difficult problems using distributed computers. The most advanced features are usually provided in commercial solvers developed and maintained by companies specializing in building the fastest, most sophisticated solvers.

Gurobi is one of the leaders in the commercial solvers market, used by large segments of the optimization community including governments, academic institutions, and companies operating in industries ranging from finance to logistics. In terms of speed, gurobi consistently outperforms in several benchmarks used to judge commercial and open source solvers.

Gurobi also comes with a powerful Python API that allows you to build models from Python. This feature gives modelers access to all of Python’s useful data manipulation libraries during model construction, which greatly aids in their process. As a demonstration of the gurobi Python API, here is how you might model the knapsack problem:

import gurobipy as gr

m = gr.Model()

camera = m.addVar(name='camera', vtype=gr.GRB.BINARY)
figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY)
cider = m.addVar(name='cider', vtype=gr.GRB.BINARY)
horn = m.addVar(name='horn', vtype=gr.GRB.BINARY)
m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint')
m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE)

m.optimize()
print(camera.x)
print(figurine.x)
print(horn.x)
print(cider.x)

Running the example will give you the following output:

Optimize a model with 1 rows, 4 columns and 4 nonzeros
Variable types: 0 continuous, 4 integer (4 binary)
Coefficient statistics:
  Matrix range     [2e+00, 1e+01]
  Objective range  [2e+00, 1e+01]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 14.0000000
Presolve time: 0.01s
Presolved: 1 rows, 4 columns, 4 nonzeros
Variable types: 0 continuous, 4 integer (4 binary)

Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0      17.0000000   17.00000  0.00%     -    0s

Explored 0 nodes (1 simplex iterations) in 0.01 seconds
Thread count was 4 (of 4 available processors)

Solution count 2: 17 14

Optimal solution found (tolerance 1.00e-04)
Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000%
-0.0
1.0
1.0
-0.0

HorusLP

HorusLP is an optimization modeling library that was built on experiences developing optimization algorithms. Currently available modeling libraries lack tools required for working with the type of complex, multifaceted problems that are typically encountered by commercial applications of operations research.

While most optimization libraries offer a low-level imperative interface, as optimization models become more complex, better tools are needed to manage the complexity. HorusLP is a library that provides higher-level tools to manage these complexities. HorusLP also provides powerful debugging and reporting tools that allow for faster development and iteration.

At its core, HorusLP is an object-oriented library that provides much-needed architecture around optimization models. By leveraging the Python object-oriented syntax, the HorusLP library provides a structure around which optimization models can be optimized. The result is a codebase that is decoupled, modular, and easy to read.

If you would like a more detailed introduction to the core HorusLP library with code samples, you can find a tutorial here.

HorusLP-Gurobi Integration

While HorusLP’s core API provides a convenient, high-level API for building optimization models, it is built on PuLP, which, while capable of making use of Gurobi as a solver, does not have access to some of Gurobi’s more advanced capabilities.

HorusLP-Gurobi is a version of the HorusLP API built using Gurobi’s Python API. This allows the user direct access to advanced features of Gurobi, while keeping the HorusLP API consistent.

One of the key philosophies guiding the development of HorusLP-Gurobi was consistency with the HorusLP core API. By keeping the minimalist structure of HorusLP consistent, a user of an open source solver can easily transition to using Gurobi by installing the Gurobi API and switching the import statements.

For simple models, HorusLP-based models will take more lines of code than simply using the Python API imperatively. However, as the development process continues and as the models become more complex, the object-oriented and declarative designs of the HorusLP API will make for easy debugging and development. The object orientation will also make the model more readable, as the model definition creates centralizes and clearly delineates the objectives, constraints, and variables, etc.

Without further ado, let’s dive into some code samples!

Code Examples

Basic HorusLP API

Because HorusLP-Gurobi keeps the API consistent, the code from the HorusLP core tutorial can be ported over with a simple change in imports. To use HoruLP-Gurobi, however, you will need to make sure that you have the Gurobi optimizer and Gurobi’s Python interface installed. You can get Gurobi by getting in touch with them here.

Once you install Gurobi, we can start with coding with HorusLP-Gurobi! Let’s begin by installing the requisite package:

Pip install horuslp horuslp-gurobi

Once the install completes, we can start using HorusLP-Gurobi! Recall the example knapsack problem from earlier. We can use HorusLP-Gurobi to model the problem as follows:

First, import the relevant libraries.

from horuslp_gurobi.core.Variables import BinaryVariable
from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent
from horuslp_gurobi.core.constants import MAXIMIZE

Define some variables.

class KnapsackVariables(VariableManager):
    # we define variables by declaring the “vars” class variable
    vars = [
        BinaryVariable('camera'),
        BinaryVariable('figurine'),
        BinaryVariable('cider'),
        BinaryVariable('horn')

Now, we can define the constraints using the constraints class.

class SizeConstraint(Constraint):
    # implement the ‘define’ function, the variables will get passed in by name
    def define(self, camera, figurine, cider, horn):
        return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

We can then implement the objective in a similar fashion.

class ValueObjective(ObjectiveComponent):
    # implement the define function and return the objective expression
    def define(self, camera, figurine, cider, horn):
        return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

And finally, we can define the problem.

class KnapsackProblem(Problem):
    # defining a problem using the Horus API is a matter of setting variables in the subclass
    variables = KnapsackVariables
    objective = ValueObjective
    # constraints is a list variable, since there can be multiple constraints,.
    constraints = [SizeConstraint]
    # make sure to set the sense!
    sense = MAXIMIZE

And we instantiate the problem and call the solve function. This is where the magic happens.

prob = KnapsackProblem() # instantiate
prob.solve() # call the solve method
prob.print_results() # optional: print the standard Horus debug report
print(prob.result_variables) # optional: print the variable results as a list

Run the code and you should see the following output:

Optimize a model with 1 rows, 4 columns and 4 nonzeros
Variable types: 0 continuous, 4 integer (4 binary)
Coefficient statistics:
  Matrix range     [2e+00, 1e+01]
  Objective range  [2e+00, 1e+01]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 14.0000000
Presolve time: 0.01s
Presolved: 1 rows, 4 columns, 4 nonzeros
Variable types: 0 continuous, 4 integer (4 binary)

Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0      17.0000000   17.00000  0.00%     -    0s

Explored 0 nodes (1 simplex iterations) in 0.01 seconds
Thread count was 4 (of 4 available processors)

Solution count 2: 17 14

Optimal solution found (tolerance 1.00e-04)
Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000%
KnapsackProblem: Optimal
camera -0.0
figurine 1.0
cider -0.0
horn 1.0
ValueObjective: 17.00
SizeConstraint: 14.00
{'camera': -0.0, 'figurine': 1.0, 'cider': -0.0, 'horn': 1.0}

The first part is the Gurobi solver, and the second part is the output from HorusLP. As you can see, the algorithm recommends that we take the figurine and horn, resulting in 14 pounds of items with $17 of value.

One of the benefits of using HorusLP with Gurobi is that you get a lot of information “for free.” A lot of the information that one would normally want to look at during development, such as the value of each variable, the final objective value, and the constraint values are automatically calculated and outputted in an easy-to-read format.

If you have read the previous article on HorusLP core, you will notice this is almost the exact same API. To keep the API simple, the interfaces of HorusLP core and HorsLP-Gurobi are identical, with differences between the solvers abstracted away in the superclass implementation.

Thus, we will leave the introduction of HorusLP to this simple example; more complex examples demonstrating advanced features of HorusLP can be found in the previous article.

Gurobi Features

Gurobi provides many advanced features for solving complex problems. Most of the features are accessible through the Model object. To allow for full compatibility with the Gurobi API, the model object is easily accessible from the problem class as model.

For example, if you wanted to write the MPS file of the knapsack model, in Gurobi you may write something like m.write(‘knapsack.mps'). While using HorusLP-Gurobi, you can simply:

# import the problem as usual
from horuslp_gurobi.core.Variables import BinaryVariable
from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent
from horuslp_gurobi.core.constants import MAXIMIZE

# define the constraint
class SizeConstraint(Constraint):
    def define(self, camera, figurine, cider, horn):
        return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

# define the objectives as above
class ValueObjective(ObjectiveComponent):
    def define(self, camera, figurine, cider, horn):
        return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

# define the variables used by the constraints and objectives
class KnapsackVariables(VariableManager):
    vars = [
        BinaryVariable('camera'),
        BinaryVariable('figurine'),
        BinaryVariable('cider'),
        BinaryVariable('horn')


# define the problem as in the above example
class KnapsackProblem(Problem):
    variables = KnapsackVariables
    objective = ValueObjective
    constraints = [SizeConstraint]
    sense = MAXIMIZE

# instantiate the problem. We don’t need to call solve or print any reports.
prob = KnapsackProblem()
prob.model.write('knapsack.mps') # this is the only bit of new code!

And you should see the MPS file in your working directory.

You can use this interface to access advanced Gurobi features such as calculating IIS, creating callbacks, or giving variable hints.

Advanced Gurobi Features at Your Service

Today we looked at a version of the HorusLP library built on top of the Gurobi Python API. In addition to the reporting and debugging features of the core HorusLP, you now have access to all the advanced features of Gurobi accessible seamlessly through integration with Gurobi’s Python API.

If you are a current Gurobi user or someone interested in using Gurobi optimization, I hope you give HorusLP a try! You can find example code, make suggestions, or contribute to HorusLP-Gurobi on GitHub.

Understanding the basics

What is HorusLP?

HorusLP is a Python optimization library designed to help you architect algorithm development workflows. It has a simple, declarative API and very little boilerplate.

What is the knapsack problem?

The knapsnack problem is an optimization problem centered on combinatorial optimization. When presented with a set of items with different weights and values, the aim is to “fit” as many of them into a knapsack that is constrained and not subject to change.

What is Gurobi used for?

Gurobi is used to solve constrained optimization problems. It can handle both linear and quadratic problems and is one of the leading commercial solvers on the market.

What is Gurobi Python?

Gurobi Python is the Python API for building Gurobi models. It allows Python developers to use python’s rich standard library to aid in model building.