Math Programming Modeling Basics

Mathematical programming is an extremely powerful technology that enables companies to make better use of available resources. Mathematical programming technologies like linear programming (LP) and mixed-integer programming (MIP) have been applied in a variety of business areas, often resulting in tens or even hundreds of millions of dollars in cost savings. To give a quick sampling of the breadth of applications for LP and MIP techniques:

• Sports scheduling: The NFL uses MIP to compute better schedules.
• Manufacturing: SAP uses MIP to schedule the production of goods in factories in order to meet customer orders.
• Logistics: FedEx uses MIP to optimize the routing of packages through their shipping network.
• Electrical power distribution: New York ISO uses MIP to choose the most cost effective way to deliver electricity to customers.
• Finance: Betterment uses MIP to choose the optimal mix of assets which maximize after-tax returns while minimizing risk.

While the process of building a mathematical programming model will probably look like magic to a non-expert, the intent of this page is to provide a bit of insight into what goes on behind the magic, and hopefully give an indication of how you might wield some of this magic for yourself. Math programming practitioners typically have mathematical training and significant practical experience, but understanding a few simple concepts can help you get a sense of the overall process. This page provides a quick, high-level overview of mathematical programming, as well as a few useful links to additional information, including case studies and example models.

The important steps in moving from a business problem to a math programming solution

We’ll start our discussion at the point where you’ve identified a part of your business that could potentially benefit from optimization (note that we’ll use the terms “mathematical programming”, “math programming”, “mathematical optimization”, and “optimization” interchangeably here). Such opportunities are generally found wherever critical resources are being underutilized because multiple different business processes compete for resources. The goal of a mathematical programming model is to

• Capture the important decisions in your business process (e.g., “Should I build this product?”, “Should I send this truck to Boston?”, “Should I buy this stock?”, etc.),
• Capture the resources potentially consumed by these decisions (e.g., “Building this product uses these machines”, “Sending this truck consumes time and money”, etc.),
• Capture the potential conflicts between these activities (e.g., “The total budget is $X”, “Building these two products requires the same machine”, “If I send this truck to Boston, I can’t deliver anything to New York”, etc.), and then
• Suggest a plan of action that maximizes the overall efficiency of the process.

If this description seems a bit non-specific, that’s actually due to the flexibility of math programming. LP and MIP are highly mathematical technologies that don’t make any assumptions about the type of problem you are trying to solve or your goal in solving it. The person building the optimization model can specify what it means to maximize efficiency – maximizing profit, minimizing cost, minimizing delays, etc. Similarly, your resources can be anything – money, raw materials, machines, workers, etc. It’s up to the mathematical modeler to translate the often very tangible items that are part of the business process into the very mathematical objects that are used represent them in the optimization model.

If you have a sense that optimization could be the right tool for your business problem, you have a few options for scoping the opportunity. The simplest is probably to speak with an expert. Gurobi has a number of experts on staff, plus a network of consulting partners, that can help you size up an opportunity. The initial assessment typically only takes a few hours. We also have many customers with no background in optimization who have managed to teach themselves the relevant mathematical modeling concepts and have succeeded in building and deploying sophisticated optimization models.

From opportunity to application

Once you’ve identified a business process that could benefit from optimization, the next step is to create an optimization model to exploit the opportunity. There are three main steps to this process:

1. Create the conceptual mathematical model that captures the important resources and constraints in the business problem.
2. Translate the conceptual mathematical model into a computer program that builds that model.
3. Solve the mathematical model using a math programming solver.

Let’s talk about each of these in more detail…

Creating the conceptual mathematical model

As we’ve noted, the first step in using optimization is to create a mathematical model of your business problem. An LP or MIP model consists of three primary ingredients:

1. A set of decision variables, which capture the range of possible decisions you can make (e.g., “How many widgets should I produce?”, “Should I send a truck from New York to Boston?”, “Should these two teams play in week 1?”, etc.). Variables can be continuous (i.e., allowed to take any value between specified lower or upper bounds), or integral (i.e., only allowed to take integral values). A model that only contains continuous variables is a linear program (LP). Mixed-Integer Programming (MIP) models can contain a mix of integer and continuous variables. Integer variables (particulary binary variables) give you quite a bit more modeling power than continuous variables, but they also generally make the resulting model much more difficult to solve. If you are curious, you can refer to our LP Basics and our MIP basics pages for more information on why MIP models are harder than LP models.
2. A set of constraints, which capture global limits on the values your decision variables can take (e.g., “These teams can’t play against each other more than once”, “A truck can only be sent to a single destination in a day”, “There are only enough parts to make 10 widgets today”, etc.). For LP and MIP, these constraints must be linear inequalities (e.g., “x + 2 y <= 3”).
3. An objective function on the decision variables that captures the value you are trying to minimize or maximize (e.g., “Maximize profit”, “Minimize cost”, “Minimize late deliveries”, etc.). For LP and MIP, the objective function must be a linear expression.

The challenge here is to map the business problem, which may involve tangible entities like machines or products or people, into the form described above, which involves linear constraints on decision variables. At first glance, LP and MIP may appear to be a strange choice for solving business problems. As we noted above, LP and MIP allow you to state a set of linear constraints on decision variables (e.g., ‘2x + 3y + 5z <= 5’) and a linear objective on these same variables (e.g., ‘maximize x + y + z’). MIP also allows you to specify that certain variables must take integer values. These tools then compute values for your decision variables that maximize the objective function while respecting all stated linear constraints. That’s all that LP and MIP can do. While the merits of being able to optimize over a set of linear constraints might be clear if you are solving geometry problems, the suitability for production scheduling or electricity distribution problems probably isn’t so obvious.

For now, you’ll have to take our word for it that it is possible to map a wide variety of problems to LP/MIP form. Let’s spend a minute talking about why you would want to…

When faced with the task of solving a difficult problem, the first step is often to assemble a set of tools that might help to solve that problem. While you may not be able to find a tool that solves your exact problem, you can often find one that is effective at solving a related problem. While a custom tool may be able to exploit some special property of the specific problem you are solving, a general purpose tool has the advantage that it has probably been tuned and refined over a long period of time and a variety of users and uses.

This is particularly true for LP and MIP. If you can express your model as a set of linear constraints with a linear objective, over a set of continuous or integer decision variables, then you can reap the benefit of using a technology that has undergone a process of extensive refinement and improvement over the last 50+ years. The improvements in the technology have been quite spectacular, often transforming problems that were entirely intractable a decade ago into problems that are routinely solved today. What’s more, by building an LP or MIP model for your problem, you are then able to obtain the benefits of future improvements in the technology with no additional effort on your part.

To say that the benefits of expressing your problem as an LP or MIP are due to decades of effort focused on solving the problem doesn’t fully capture the virtues of LP and MIP, though. LP and MIP sit at a juncture between rich mathematical theory, elegant computational implementations, and richness of modeling and expressiveness that is quite rare and quite special. You could set the best and brightest minds at work for 50 years on many other problem types, and you would probably not wind up with technologies that are as powerful or as elegant as LP and MIP.

Mathematical Modeling

Hopefully we’ve convinced you that there are substantial benefits to formulating your problem as an LP or MIP model. If so, then the next step is to talk a bit about how that is done. The fundamental building block for a MIP model is the binary decision variable. It typically capture a yes/no decision, where a value of 1 means yes and a value of 0 means no. You can use a binary variable to represent any number of business decisions (“should I build this product?”, “should I buy this raw material?”, etc.). Constraints between binary variables represent competition for resources. Constraints between binary variables and continuous variables often capture the more detailed implications of these decisions.

Common Modeling Constructs

Let’s consider a few simple examples. If you can choose at most one from among a set of conflicting activities, that would be captured as a linear constraint on binary decision variables:

b1 + b2 + b3 <= 1

If these are all binary variables, then at most one variable in the list can take value 1, and that one would correspond to the chosen activity. Similarly, changing the inequality to an equality:

b1 + b2 + b3 = 1

…would force you to always choose one of the three possible activities.

Given a decision that is reflected in the value of a binary variable, you can use additional variables and constraints to capture the consequences of that decision. For example, if you need to transport items from one city to another, then a decision about whether to send a truck between those cities determines the maximum number of items that can be sent. By introducing a variable items[ij] to represent the
number of items sent from city i to city j, then the following linear constraint would capture the relationship between the number of items sent and a decision about whether to send a truck with a capacity of 10 items:

itemsij <= 10 * truckij

If binary variable truck[ij] is 1, then you can send up to 10 items. If it is 0, then you can’t send any items.

These are just a few examples chosen from among a large set of idioms that are useful when building a mathematical model. A typical optimization model will consist of a mix of many straightforward linear constraints (e.g., the sum of these cost variables must respect the overall budget), along with a few more idiomatic constraints. Furthermore, a typical model will consist of thousands or even millions of constraints, but the overall size is typically the result of replicating the same set of constraints over multiple pieces of input data. One of the best ways to learn these idioms is to study example models. You’ll find examples from a variety of industries that you can browse and learn from here.

Modeling Patterns

If you ask an architect to design a house for you, his first thought is not going to be about how to pour concrete for the foundation. He’s going to try to identify important characteristics of the desired house (size, style, bedrooms, etc.), and then modify a house design with similar characteristics to meet your specific needs. Similarly, while understanding the low-level process of building an optimization model can be quite useful, the reality is that the mathematical modeling process is often mostly about recognizing common structure in your problem and customizing well-established models to capture the specifics of your problem.

Mathematical modeling has a number of commonly occurring model patterns that appear in many different applications. Examples include fixed-charge network flow, set partitioning, production planning, facility location, job shop scheduling, portfolio optimization, etc. It is well worth your time to familiarize yourself with common model types. Our website provides a number of example models that capture common model types. To reiterate, the model you need for your problem may not match any of these patterns exactly, but you are often better off approaching your problem by identifying a similar pattern and then thinking about how it could to customized to capture your problem, rather than trying to solve your problem from scratch.

Extensions

While we’ve only mentioned LP and MIP so far, there are a number of interesting extensions that can also be solved efficiently. If your problem has a quadratic objective, involving products of decision variables rather than just linear terms, then you can solve your model as a Quadratic Program (QP) or a Mixed-Integer Quadratic Program (MIQP). If your model has quadratic constraints as well, you can solve your model as a Quadratically Constrained Program (QCP), or a Mixed-Integer Quadratically Constrained Program (MIQCP). These variants place a few restrictions on the form of the quadratic objective or constraint, but many important types of models can be cast in this form.

Another common class of models is non-linear programming (NLP) problems. While general NLP is an extremely difficult problem, such problems can often be solved using a very common and powerful approach called piecewise-linear approximation. By approximating the non-linear function using a series of linear functions, you can often transform what is typically an exceedingly difficult optimization problem into one that can be easily handled by an LP or MIP solver. Optimization solvers typically include modeling tools that make it straightforward to express a piecewise-linear function.

Implementing the model

Once you have an idea of how to build a math programming model that would solve your problem, the next step is to write a computer program that implements your model. Gurobi provides interfaces for most of the commonly used programming languages: C, C++, Java, .NET, Python, R, and MATLAB. When people ask us which language is best for math programming, our answer is that people should use the language they are most comfortable in. All of our interfaces are thin layers that sit on top of the same optimization algorithms (implemented in C). There are difference in our various language API’s, but ultimately those differences will have a smaller impact on your productivity than working in an unfamiliar language would. Another point to consider is that mathematical models rarely live in isolation. They typically consume data from some data source, and they produce results that are consumed by some downstream process. The languages and formats of these dependent processes will influence your choice of language.

Having said that, if you don’t have a reason to prefer one language over another, we recommend you use our Python API. We’ve found that this API increases modeling productivity substantially. It includes a number of higher-level modeling constructs that reduce the gap between the mathematical model itself and the implementation of that model, which makes it a lot easier to build and maintain optimization models.

The mechanics of building the optimization model are generally quite straightforward, once you have assembled the necessary input data. Our Getting Started with the Gurobi API Tutorials work through simple examples in each of our supported languages. This example touches on the basics of our API’s, including the process of creating a model, adding decision variables, adding constraints, setting the objective function, etc. We also include a number of functional examples that cover the use of more advanced features in our product.

Solving the model

A large part of the power of LP and MIP is that they provide a declarative approach to solving a problem. It is your job to state, or declare, your problem (the decision variables, constraints, and objective), and it is our job to find an optimal solution. The solver employs a number of very sophisticated algorithms for both LP and MIP problem types (and a number of parameters that optionally give you control over the behavior of these algorithms), but you generally don’t need to understand how these algorithms works to obtain a solution to your problem.

Next Steps

Your next step in building an optimization model will depend on how hands-on you’d like to be. As we noted above, if you are interested in further details about different aspects of math programming, you can refer to our Python basics discussion for more information on building a model, or our LP basics and MIP basics pages for more information on the underlying solution algorithms. You also browse our examples or our case studies.

If you are a commercial user who would like to discuss your problem with an expert, you can contact Gurobi directly. As Gurobi is free for qualified academic users, we provide direct support for installation and licensing questions and a monitored Gurobi Community Discussion Forum for other questions.

We also have a list of consulting firms who can help you to scope your problem and build a solution.

Of course, the best next step is to try Gurobi for yourself:

Get Gurobi