Learn how to use Python PuLP to solve Cargo loading problems and Knapsack Problems using Integer Programming.
Linear programming deals with non-integer solutions but in certain scenarios, we need integer solutions such as the number of products to manufacture, number of apartments to construct, number of trees to plan. In this approach, we optimize the linear function and set of linear constraints on integer variables. Integer programming is widely utilized in the area of job scheduling, inventory management, transportation, computer science, and production planning.
In this tutorial, we are going to cover the following topics:
Types of Integer Programming
There are three types of Integer programming problems:
- Pure Integer Problems: In this type of problem, all the variables have integer solution.
- Mixed Integer Problems: In this type of problem, some of the variables have integer and some of the variable have the continuous solution.
- 0-1 Integer Problems: In this type of problem, all the varaibles requires value of 0 or 1.
The knapsack problem is defined as how many units of each different kind of item or product to put in a knapsack with a given capacity in order to maximize profit. It is also known as the fly-away kit problem because a jet pilot decides the most valuable items to take abroad a jet. The knapsack problem is a special case of integer programming where the objective function is maximized with a single less than or equal to linear constraint. It has many applications in the real world.
Cargo Loading Problem
The cargo loading problem is a typical example of a knapsack problem. This type of problem solves the capacity planning problem of a shipment. We load the items into a shipment with limited capacity. The main objective is to load the most optimum items in the shipment.
Suppose there are n items 1,2,3 … n and the number of units of each item is mi. The weight per unit of item i is wi, ri is the revenue per unit of item I, and W is the total capacity of cargo.
Understand the problem
One Cargo shipment of Shakti Pumps has a capacity of 10 tons. Shakti Pumps wants to ship three types of pumps A, B, and C in this shipment.
- A pump weight of 1 ton and profit of $12 (X1)
- B pump weight of 2 tons and profit of $25 (X2)
- C pump weight of 3 tons and profit of $38 (X3)
Maximize Z = 12X1 + 25X2 + 38X3
12X1 + 25X2 + 38X3≤ 10 (Cargo storage capacity 10 ton)
Initialize LP Model
In this step, we will import all the classes and functions of
pulp module and create a Maximization LP problem using LpProblem class.
# Import all classes of PuLP module from pulp import * # Create the problem variable to contain the problem data model = LpProblem("Cargo-Loading-Problem", LpMaximize)
Define Decision Variable
In this step, we will define the decision variables. In our problem, we have three variables A, B, and C. Let’s create them using
LpVariable will take the following four values:
- First, arbitrary name of what this variable represents.
- Second is the lower bound on this variable.
- Third is the upper bound.
- Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are
# Define Decision Variables x1 = LpVariable("A", 0, None, LpInteger) x2 = LpVariable("B", 0, None, LpInteger) x3 = LpVariable("C", 0, None, LpInteger)
Define Objective Function
In this step, we will define the maximum objective function by adding it to the
# Define Objective model += 12 * x1 + 25 * x2 + 38 * x3
Define the Constraints
In this step, we will add only 1 constraint defined in the problem by adding them to the
# Define Constraints model += x1 + 2*x2 + 3*x3 <= 10 # Cargo storage capacity 10 ton ; pump A is 1 ton, pump B is 2 tons and pump C is 3 ton.
In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.
# The problem is solved using PuLP's choice of Solver model.solve() # Print the variables optimized value for v in model.variables(): print(v.name, "=", v.varValue) # The optimised objective function value is printed to the screen print("Value of Objective Function = ", value(model.objective))
Output: A = 1.0 B = 0.0 C = 3.0 Value of Objective Function = 126.0
In this article, we have learned about Integer Programming, Knapsack Problems, Cargo Loading Problems, Problem Formulation, and implementation in python using the PuLp library. We have solved the cargo loading problem using an integer programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. In upcoming articles, we will write more on different optimization problems and its solution using Python. You can revise the basics of mathematical concepts in this article and learn about Linear Programming in this article.