Hidden Gems: Advanced Modeling Features

By Dr. Elisabeth Rodríguez-Heck

Mathematical programming is an extremely powerful and flexible technology. Even the most traditional types of mathematical models—like Linear Programs (LP), Mixed-Integer Programs (MIP), and Quadratic Programs (QP)—allow you to solve many of the world’s most complex problems across manufacturing, electrical power distribution, finance, scheduling, supply chain management, transport and logistics, and more.

You may find, however, that for some business requirements, an LP, MIP, or QP alone might not be enough to capture the complexities of your problem or your organization’s processes. That’s why our Gurobi R&D team has built several advanced features that may help you out. Let’s take a look at four of them:

Balancing Act: When Your Problem Has Two Competing Objectives

Real-world optimization problems often have two or more competing—or even conflicting—objectives. For example, a hospital manager may want to minimize the number of total shifts for hospital nurses while maximizing worker satisfaction. Or an investor may want to create a portfolio that maximizes profit while minimizing risk.

In such cases, Gurobi’s Multiple Objectives feature may be just what you are looking for. The Multiple Objectives API allows you to express several objectives and seamlessly integrate them with the rest of your code, helping to keep your codebase easy to understand and maintain.

Gurobi can handle the trade-offs of multiple objectives using one of two approaches—or a combination of both:

• A weighted approach: Optimizing a combination of the individual objectives
• A hierarchical approach: Optimizing one objective after the other in a given priority order while limiting the degradation of higher-priority objectives

Sometimes, using a multi-objective hierarchy can help address numerical issues in problems with large objective function coefficients. For example, a minimization problem may contain two clearly distinct sets of objective function coefficients—with one group of coefficients ranging between 0 and 100 and another group ranging between 100,000 and 100,500. Often, the objective terms with the large coefficients actually correspond to a second “hidden” objective function, which is modeled as a penalty. For example, in the nurse scheduling problem, the primary objective may be to minimize shifts, but a second penalized objective may account for shift balance among the nurses. Unbalanced solutions are penalized (with a factor of 100,000) and are, therefore, (hopefully) avoided by the minimization due to the large coefficient. However, such a large spread of coefficients can sometimes cause numerical issues that can be avoided by modeling the problem as a hierarchical multi-objective optimization instead.

Take a look at our multiobj.py example to learn more about this feature.

Embracing Uncertainty: When Your Problem Data Changes

Life is uncertain—and so is the input data of many business problems. You may have a mathematical model capturing all the details of your problem, but you would still need to understand what happens to the optimized production if the forecasted demand is 10% lower than anticipated. Or you may be planning the construction of a building and want to know what happens to the building costs if phase one of the project is a day late, or two days late, or even five days late.

Gurobi’s Multiple Scenarios feature allows you to specify a set of different scenarios and compute optimal solutions for all these scenarios. While it is possible to implement and solve the scenarios as separate models, using this feature allows you to solve the problems faster than if they were completely separate models, because all the scenarios are solved as one big model using binary variables to distinguish the scenarios.

While, at first, it may look like the multiple scenarios feature is quite restricted, there are some tips and tricks to circumvent these restrictions. A hard restriction, though, is that this feature cannot be used in combination with the multiple objectives feature.

Explore our multiscenario.py and sensitivity.py examples to learn more about this feature.

Winning Acceptance: When Your Customers Won’t Accept the Solution (Even When It’s Optimal!)

You have finished building an impeccable model capturing all of the business details. After fixing some bugs, you spend some time improving your model and maybe even tuning the solver parameters to obtain the best performance. Finally, your model produces an optimal solution in a reasonable time. Congratulations, your job here is done!

…or maybe not?

Very often, the hardest part is not the actual modeling or coding itself, but it’s getting your customers or users to accept and implement the solution that the optimization provided.

How is this possible? Can’t they see this is optimal?

Well… sometimes it may be difficult to accept a solution that comes out of a “black box.” Especially if your users are not familiar with mathematical optimization, it may be difficult to believe that it is actually possible to find an optimal solution to such a complex business problem.

In such cases, it may be very useful to have more than one solution available and provide this to the end-user so that they can compare the solutions and understand why the optimal solution is actually optimal. This approach helps to demonstrate the value of the optimal solution and gives decision-makers a greater feeling of control.

With Gurobi, you can define a Solution Pool, which lets the solver report multiple solutions automatically after a single run. There are different ways to set up the solution pool—such as (1) storing all solutions found in the regular optimization without any additional computation effort or (2) storing the n best solutions in addition to the optimal one, at the cost of additional computations.

Having multiple solutions can also be helpful in cases where your business problem has some implicit elements—like preferences or other aspects—that may be difficult to quantify. In this case, you may prefer to select a solution from the pool, even if it’s different from the optimal one.

Finally, modelers often identify modeling errors or missing constraints by looking at the solutions. While an optimal solution can be helpful for this, it is possible that having other solutions can further help.

Our poolsearch.py example is a good place to get started with this feature.

Navigating the Maze: When Your Model is Infeasible

Dealing with infeasibility can be very frustrating. Especially when working with large-scale models, it can be difficult to understand which constraints are problematic. Sometimes the mathematical translation of the constraints is perfectly sound, but the business requirements must be revised. Gurobi provides two features to help you deal with infeasibility.

The first feature is the Irreducible Inconsistent Subsystem (IIS) computation, which can help you understand why your model is infeasible. In short, an IIS is an infeasible subset of constraints and variable bounds of your original model, such that removing a single constraint or bound makes it feasible. Writing an IIS into a human-understandable model format can help you detect the culprit(s) by manually inspecting the set of conflicting constraints.

Since IISs are meant to be interpreted by a human, Gurobi tries to provide a small IIS. However, this is sometimes not possible, because computing an IIS is an extremely difficult problem itself, often involving the resolution of many MIPs. In cases where the IIS is not helpful, computing a Feasibility Relaxation might come in handy to help you understand which changes you have to make to your model to recover feasibility. The feasopt.py example illustrates the use of the Feasibility Relaxation feature.

Often enough, the business requirements make perfect sense and their translation into mathematical constraints is correct, but Gurobi still says that your model is infeasible. In the majority of such cases, numerical issues are to blame. A symptom of numerical issues can be that optimization says that the model is infeasible, but the IIS computation throws an error saying that an IIS cannot be computed on a feasible model. Even though parameter settings can help resolve the symptoms of numerical issues, addressing the root cause of the numerical issues is usually the recommended and most robust solution.

Discover More Hidden Gems

To dig even deeper into Gurobi’s advanced modeling features—and discover more “hidden gems”—check out our one-hour, on-demand webinar presentation: “Hidden Gems – Useful Gurobi Features You Might Not Know.”