The increasing sophistication of optimization technologies has led to the widespread adoption of commercial solvers in various industries. These commercial solutions offer advanced features like presolve techniques, warm starting capabilities, and distributed solving, making them more suitable for complex optimization models compared to their open-source counterparts.

Gurobi, a leading commercial solver developed by optimization pioneers Zonghao Gu, Edward Rothberg, and Robert Bixby, has been instrumental in solving many high-impact optimization problems, including the FCC’s bandwidth allocation project and Pennsylvania State Prison’s prisoner reassignment project.

This article explores how HorusLP, a software package designed for high-level declarative optimization modeling, seamlessly integrates with Gurobi’s API. This integration empowers users with an intuitive modeling experience while leveraging the advanced capabilities of Gurobi.

Understanding Optimization

For those unfamiliar with optimization or operations research, it involves using mathematical techniques to determine the optimal values of variables within a system of equations and constraints. To illustrate, consider the classic knapsack problem.

Imagine having a knapsack with a 15-pound weight limit. You have several items, each with its own weight and monetary value:

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

The goal is to maximize the total value of items carried in the knapsack without exceeding its weight limit. Feel free to create a story around this scenario!

Mathematically, this problem can be represented as:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

We can then apply optimization techniques to determine the best combination of items to carry. Examples of solving this problem using Python and the core HorusLP API are available in my previous articles.

While the underlying mathematical concepts are fascinating, they fall outside the scope of this article. For those interested in delving deeper, I recommend exploring resources like here and here, both provided by Gurobi.

Exploring Gurobi

Specialized software known as solvers are now used to tackle most optimization problems, replacing manual calculations. While many solvers effectively handle well-defined linear and integer programming problems, some stand out with advanced capabilities. These solvers can handle more complex problem classes, utilize cutting-edge mathematics for faster solutions, or employ distributed computing for large-scale problems. Such advanced features are often found in commercial solvers developed by companies specializing in high-performance optimization tools.

Gurobi is a prime example, widely adopted by governments, academic institutions, and companies across various sectors like finance and logistics. It consistently outperforms competitors in numerous benchmarks commonly used to benchmark commercial and open-source solvers.

Furthermore, Gurobi’s powerful Python API enables model construction directly within Python, granting modelers access to Python’s rich data manipulation libraries for enhanced efficiency. To illustrate, here’s how the knapsack problem can be modeled using the Gurobi Python API:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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)

Executing this code will yield the following output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

Introducing HorusLP

HorusLP, born out of experiences in developing optimization algorithms, is an optimization modeling library addressing the shortcomings of existing libraries in handling complex, real-world optimization problems.

As opposed to the low-level imperative interfaces prevalent in most libraries, HorusLP provides higher-level tools to manage the intricacies of increasingly complex optimization models. This simplifies development and iteration with its powerful debugging and reporting features.

At its core, HorusLP employs an object-oriented architecture, leveraging Python’s object-oriented syntax to structure optimization models. This results in a more organized, modular, and readable codebase.

A more in-depth introduction to the core HorusLP library, including code examples, is available in this tutorial.

Bridging the Gap: HorusLP-Gurobi Integration

While HorusLP’s core API offers a user-friendly, high-level interface for building optimization models, its reliance on PuLP limits its access to some of Gurobi’s advanced functionalities.

This is where HorusLP-Gurobi comes in. Built using Gurobi’s Python API, it allows users to directly leverage Gurobi’s advanced features while maintaining consistency with the familiar HorusLP API.

One of the key principles guiding HorusLP-Gurobi’s development is maintaining consistency with the core HorusLP API. This ensures that users of open-source solvers can easily transition to Gurobi by simply installing the Gurobi API and adjusting import statements.

While simple models might require slightly more code in HorusLP-Gurobi compared to using the Python API imperatively, the object-oriented and declarative nature of HorusLP becomes increasingly beneficial as models grow in complexity. It enhances code readability, simplifies debugging, and promotes modularity.

Now, let’s dive into some code examples to illustrate the power of HorusLP-Gurobi.

Code Examples: Bringing It All Together

Basic HorusLP API

Thanks to the consistent API design, code from the HorusLP core tutorial can be easily ported over to HorusLP-Gurobi by simply changing the import statements. However, using HorusLP-Gurobi requires the installation of both the Gurobi optimizer and the Gurobi Python interface. You can obtain Gurobi by contacting them here.

Once Gurobi is installed, we can begin coding with HorusLP-Gurobi by installing the necessary package:

1

Pip install horuslp horuslp-gurobi

With the installation complete, let’s revisit the knapsack problem and model it using HorusLP-Gurobi:

First, import the required libraries:

1
2
3

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

Next, define the variables:

1
2
3
4
5
6
7

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

Define the constraints using the constraints class:

1
2
3
4

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

Define the objective in a similar manner:

1
2
3
4

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

Define the problem:

1
2
3
4
5
6
7
8

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

Instantiate the problem and call the solve function:

1
2
3
4

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

Running this code should produce the following output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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 output consists of two parts: the Gurobi solver output followed by the HorusLP output. The algorithm suggests taking the figurine and horn, resulting in a total weight of 14 pounds and a combined value of $17.

One advantage of using HorusLP with Gurobi is the automatic calculation and presentation of valuable information, including variable values, final objective value, and constraint values, in an easy-to-understand format.

Readers familiar with the previous article on HorusLP core will notice the near-identical API. This consistency is intentional, with the differences between solvers abstracted away in the superclass implementation.

This simple example serves as an introduction to HorusLP. More complex examples showcasing advanced features of HorusLP can be found in the previous article.

Unlocking Advanced Gurobi Features

Gurobi offers a plethora of advanced features for solving intricate problems, mostly accessible through the Model object. To ensure full compatibility with the Gurobi API, the model object is easily accessible from the problem class as model.

For instance, to write the MPS file of the knapsack model in Gurobi, you might use m.write('knapsack.mps'). With HorusLP-Gurobi, you can simply use:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 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!

This will generate the MPS file in your working directory.

This interface grants access to other advanced Gurobi features such as IIS calculation, callback creation, and providing variable hints.

Empowering Optimization with HorusLP-Gurobi

In this article, we explored HorusLP-Gurobi, an integration of the HorusLP library with the Gurobi Python API. This combination empowers users with the debugging and reporting capabilities of HorusLP while unlocking the advanced features of Gurobi.

Whether you’re an existing Gurobi user or someone looking to leverage Gurobi’s optimization power, I encourage you to give HorusLP-Gurobi a try! You can find code examples, provide feedback, or contribute to the project on GitHub.