When data scientists and operations researchers seek to find the best outcome for a problem, they turn to mathematical optimization. One foundational technique in mathematical optimization is linear programming (LP), which involves constructing and solving LP models.
What Are LP Models?
LP models are mathematical models used to solve linear programming problems. As with any optimization model, LP models have the following three components:
- The Objective Function: This is the metric you seek to optimize. “Optimization” means maximizing or minimizing the objective function. For example, a company may seek to maximize profits or factory outputs. Conversely, they may want to minimize costs or greenhouse gas emissions.
- Decision Variables: These are the factors that impact the objective function if they change. Decision variables could include materials (e.g., inputs), equipment (e.g., trucks assigned to a route), labor hours, or financial investment.
- Constraints: These are the limits or conditions that must be met, no matter what. For example, if a company does not want to pay overtime, one constraint would be that no staff member may work more than the maximum number of hours per week.
When Should You Use LP Models?
While linear programming models are useful for many problems, they are not appropriate for every situation. You should use LP models when the decision variables are:
- Linear: The objective and all constraints must be linear. For example, the amount of flour a bakery purchases has a linear relationship with the volume of cookies the bakery produces. If one pound of flour can create 20 cookies, then each additional pound of flour will also create an additional 20 cookies.
- Continuous: All variables should be continuous, meaning they do not need to be discrete, whole units. Using the cookie example, a bakery can purchase flour in units smaller than one pound (e.g., ounces). Compare this with a mixer or oven, which must be purchased as a whole, discrete unit.
What Is an Example of an LP Model?
One classic example of an LP model involves calculating optimal production levels to maximize profits, given the available resources, their costs, and the price points of the output.
You can find a simple example of this type of problem, with a sample formula, for a bakery producing muffins here.
Other classic examples include the diet problem, manufacturing problems, and transportation problems.
LP Models in Real Life
ESUPS (Emergency Supply Pre-Positioning Strategy), a humanitarian logistics and preparedness project hosted by Welthungerhilfe, designed an LP model that optimizes the distribution of humanitarian supplies.
By anticipating needs and moving stock to where it will be needed, ESUPS aims to avoid many of the logistical challenges humanitarians face during disasters. In addition, the model identifies outposts that have excess stock and helps ESUPS redirect items to more appropriate locations. This ensures that disaster survivors have appropriate supplies in the right place at the right time, thus saving time and lives.
Common Pitfalls to Avoid with LP Models
New data scientists or operations research professionals may encounter some issues when designing their first LP model. Common errors include:
- Assuming Linearity: Do all of your variables have linear relationships with the objective function and constraints? Are you sure? Sometimes, one might intuit a linear relationship when it is actually nonlinear. For example, non-experts might assume that there is a linear relationship between a car’s speed and its fuel efficiency. In reality, the relationship is nonlinear. Check your assumptions with subject matter experts on your team to make sure you select the correct model.
- Ignoring Data Quality: Your LP model is only as good as the data you use. Make sure you select appropriate, reliable data when designing your model.
- Over-Constraining Your Model: Adding too many constraints may limit your options and cause you to miss the truly optimal solution. Work with your leadership and subject matter experts to identify the truly non-negotiable, immovable boundaries. Let the other factors become decision variables.
Start Your First LP Model Now
Want to get started on your first LP model? Check out Gurobi’s free Linear Programming tutorial series.
