Course 11: Integer Programming Modeling
Author: OptimizationCity Group
Introduction
In linear programming, the assumption of divisibility causes continuous values to be given to integer variables, which are conceptually meaningless. For example, the number of people or the number of devices must be assigned to integer values. In the literature, this type of modeling are called integer linear programming, which is called integer programming for short. If all the decision variables of a linear programming problem are integers, it is called pure integer programming. If the variables are integer only for a number of variables, it is called mixed integer programming. In the following, an example is presented.
Example:
A manufacturing company decides to establish a new factory in one of two cities (A) and (B) in order to develop its activities. In the city that is chosen for this purpose, it can build a new warehouse, but it is allowed to have a maximum of one warehouse. In the table below, the costs related to the construction of factories and warehouses in cities (A) and (B) are shown. The maximum budget for this development is $24 million, and the goal of the problem is to determine the solution that maximizes net worth.
Solution:
The decision variable of this problem is as follows:
Because decisions x1 and x2 are incompatible (the company can have at most one factory), the following constraint is needed:
Similarly, decisions x3 and x4 are incompatible (the company can have at most one warehouse).
x3 and x4 are dependent on x1 and x2 (building a warehouse in a city depends on building a factory in a city). This condition is expressed using the following constraint:
In the first constraint, if x1=0 (that is, a factory is not built in the city (A)), then x3=0 (A warehouse is no built in the city (A)). But if a factory is built in city (A) , a warehouse can be built in city (A) (x3=0 or 1).
Therefore, the model is as follows:
Special case of integer programming modeling
Either-or constraint
Consider a situation where you can choose one of the two existing constraints, but it is not necessary that both constraint are satisfied. Suppose that in a problem, one of the following two constraints must be satisfied:
Using a large number M, the above constraints can be reduced to the following:
where y is a zero and one variable. If y=1, then we have:
In this case, the constraint of x1+4x2≤16 is established and there is no need to establish the constraint of 3x1+2x2≤18.
If y=0, the constraints become:
In this case, the constraint of 3x1+2x2≤18 is established and there is no need to establish the constraint of x1+4x2≤16.
K constraints out of N constraints
Now consider the case where there are constraints as follows.
We want to satisfy k constraints out of N constraints. The formulation of this problem is as follows:
Functions with N possible values
Consider the function f(x1,x2,…,xn) which can take up to one of N values d1,d2,…,dN. The equivalent integer programming model is as follows:
Fixed charge cost
Production operations usually require a fixed charge or a set up cost. In this case, the total cost of production includes variable cost (relate to the volume of activity) and fixed charge cost. If xj represents the volume of activity number j, kj represents the fixed charge cost, and cj represents the cost of each unit of this activity, the total cost will be equal to:
Now consider the following model:
The equivalent of the integer programming model is as follows:
In the above model, if yj=0, then xj=0 and then fj(xj)=0. If yj=1, then xj can take any positive value and we will have:
Warehouse planning problem
In warehouse planning problem, a decision must be made between transportation costs and warehousing costs. Suppose, a manager has to decide which of the n warehouses to set up to satisfy the demand of m customers. The decision variable of such a decision is as follows:
xij: the amount of goods that go from warehouse i to customer j.
fi: Fixed rental fee for warehouse i if it is open.
cij: operating cost of warehouse i plus shipping cost from warehouse i to customer j.
There are two constraints in this problem, which are:
1) Demand dj for each customer must be supplied from warehouses.
2) Goods are shipped from a warehouse only the warehouse is open.
The integer programming model is as follows:
Knapsack problem
One of the famous problems is the knapsack problem. This problem is related to the transportation of goods by cars, planes, ships or human. The items carried in this problem are indivisible, different goods with different weight and revenue. If the goal is to transport n types of goods with weights (a1,a2,…,an) and revenue (C1,C2,…,Cn) using a C-capacity vehicle, the following model shows the mathematical expression of knapsack problem.
In the above model, xj represents the decision to carry or not to carry the jth goods. xj=1 means carrying jth goods and xj=0 means not carrying jth goods.
Example:
Consider a cargo ship with a maximum capacity of 120 tons. The owner of this ship is offered to carry goods of different weight and revenue below. According to its capacity, which of the goods should be selected for transportation in order to maximize the total revenue:
Solution:
If xj (j=1,…,8) indicates the selection or non-selection of goods for transportation, the model of this problem is as follows:
Another condition can be added to the above problem. For example, deciding to choose at least one of the two goods number 1 and 4, the following constraint shows this condition:
By adding the above constraint, it is possible to carry at least one of the two good or both of them, two variables can never take the value of zero at the same time. On the other hand, if the decision is to take at most one of the two goods number 2 and 5, the following constraint can be used:
Multiple choice problem
Choosing one choise from several different choices in a problem is called a multiple choice problem. Oil well drilling problems are an example of such problem. It is possible to drill m oil well from n drilling sites. The figure below shows this situation.
The cost of drilling from the site i to well j is equal to Cij and the cost of construction site i is equal to Si. The goal is to choose the best location of drilling sites with the minimum cost. The model of this problem is formulated as follows:
Then
Constraints are as follows:
Each well j (j=1,2,…,m) must be drilled through only one site.
The maximum number of drilling operations that can be performed from site i to well j is equal to n.
where yi=0,1.
Example: Drilling can be done from three sites to four oil wells. The costs of site preparation and rig installation and cost of drilling are presented in the table below.
The policy is that each oil well should be explored by only one site.
Solution:
The decsion varialbes is as follows:
The model is as follows:
Constraints 1, 2, 3, and 4 state that oil well 1, 2, 3, and 4 should be drilled through only one site, respectively. Constraints 5, 6, and 7 state that If a site is set up, it is possible to dig for finding the oil wells.
Traveling salesman problem
Consider a salesman who starts his journey from his city and returns to his city after traveling to several different cities. The goal is to find the shortest possible route for this journey. In operations research, this problem is known as the traveling salesman problem. The model of this problem is as follows:
The objective function is:
The restrictions of entering the city and leaving the city are in accordance with:
The solution of the above model does not necessarily provide a complete round trip from the origin of the trip. For example, consider the following solution.
The graphic representation of the above solution is as follows.
As is clear, the above answer does not determine a round trip for the saleman. To solve this problem, it is necessary to add constraints that lead to the elimination of sub-tour trips. The following example shows how to add these constraints.
Example: The matrix below shows the distance between four different cities.
In this matrix, the distance between city i and city i has been set as M to exclude impossible trips in the model.
The constraint is only one trip from one origin to one destination as follows. In other words, it is not possible to make two trips from any node.
The limitations of reaching a destination only through ONE origin are as follows.
Another group of restrictions that need to be added to prevent sub-tour, whose length is smaller than n cities. In other words, it causes the seller not to return to the city of origin before visiting all the cities. If these constraints are not added to the problem, we may have the infeasible solution. In the following, the constraints for removal of sub-tours are written.
If the salesman goes from city i to city j, he should not return from city j to city i. By doing this, the sub-tours of two cities will be removed from the feasible solution.
If the salesman goes from city i to city j and then to city k, he should not return from city k to city i. By adding these constrains, the sub-tours of three cities are removed from the feasible solution.
The objective function of the model is equivalent to:
Multiple traveling salesman problem
In the generalized case, the traveling salesman problem is called the multiple traveling salesman problem or MTSP for short. The number of traveling salesmen is assumed to be M, and each salesman must visit a subtour of cities that includes the origin city to make sure that each city except the origin city is visited exactly once by only one salesman. The objective is to minimize the total distance traveled by all M salesmen:
The distribution problem
A large company produces goods in n different factories (i=1,2,…,n. This company distributes the goods either through direct supply to r retailers (k=1,2,…,r) or through m wholesalers (j=1,2,…,m) in the country. The figure below shows the graphic representation of the distribution network.
The variables of this problem are as follows:
xij: the amount of goods shipped from factory i to wholesaler j with a unit shipping cost of Cij.
Zik: The amount of goods shipped from factory i to retailer k with a unit shipping cost of Cik.
yjk: the amount of goods sent from the wholesaler j to the retailer k with a unit shipping cost of Cjk.
Each factory has a monthly production capacity of Ni units, and the wholesaler can receive and store Mj units per month. This is despite the fact that every retailer has a minimum demand of Rk per month. The goal of the problem is to minimize the cost of distributing goods. The objective function of this problem is as follows:
The constraints of this problem are as follows:
Production capacity constraint:
Wholesaler’s warehouse constraint:
The balance of receiving and sending the goods by the wholesaler meets by the following constraint:
Retail demand constraints
Location problem
Location problem are used to determine suitable locations for the construction and operation of factories and warehouses. Suppose a construction company receives the proposal to work on m different projects. n different places have been nominated to create the workshops. The purpose of this problem is to determine the appropriate location of the workshop to minimize the total cost. The total cost are as follows:
1) Shipping cost: This cost depends on the amount of demand for workshop.
2) Setting up cost: This cost includes the construction and installation of workshops in candidate locations.
3) operational costs
In this model:
i: the location nominated to create a workshop (i=1,…,n).
j: the construction projects (j=1,…,m).
Cij: The cost of transporting each unit of goods from place i to place j.
bi: the cost of workshop maintenance at location i.
ai: the cost of building workshops at location i.
Qj: the demand of Project j
xij: A proportion of the demand Qj shipped by workshop i.
The objective function of this model is as follows:
The constraints of this model are as follows
Job shop scheduling problem
Consider a job sequencing problem that requires n different activities to be performed on a single machine in the minimum possible time. Making a complete product is done by performing a series of different operations that must be done in order. Also, each manufactured product may have a specific delivery date. So this issue may have three types of limitations:
Constraint 1) Sequencing
Constraint 2) Noninterference
Constraint 3) Delivery date
This problem is called job shop scheduling problem. Consider constraint 1. Let xj be the start time of activity j, which is started from the origin of time , i.e. zero. Similarly, assume that ai is the time of doing activity i. If activity i is supposed to be performed before activity j, the work sequence constraint (constraint 1) is related to it as follows:
Then consider constraint 2 or the time non-interference constraint. In the event that activities i and j are not performed simultaneously on the machine, the following limitation must be established.
One of the above two case is selected according to the order of i or j. That is, either j occurs after i or i after j. It is not possible to use the “this or that” constraint in linear programming. In this lesson, we talked about this constraint, which can be solved by adding a 0-1 variable. Consider the variable yij.
In this way, the constraint “this or that” is equivalent to two simultaneous constraints in the form of “and”.
In the above constriants, if yij=0, constraint 1 becomes redundant, but constraint 2 is effective. If yij=1, constraint 1 is effective and constraint 2 is redundant.
Limitation 3 deals with the delivery date of the products. Product delivery dates can be enforced by adding the following constraint. Assume that activity j must be finished by time dj, then:
If t is the total time required to complete all n activities, the problem becomes as follows.
Example: Suppose three products A, B, and C are made by 4 machines. The sequence of machines and the time of using the corresponding machine for each of the three products are shown in the figure below.
For example, to produce product A, machine 1 should work for a1 hour, then machine 3 for a3 hours, and finally machine 4 for a4 hours. Working time on products B and C is different for machines. Each machine can only work on one product at a time.
In addition, product B is required to be delivered before d hours from the start time. The problem model is as follows:
Let XAj display the start time (starting from zero) of producing product A by machine j for j=1,3,4. Similarly, XBj is defined for j=1,2,4 and XCj for j=2,3.
The sequence of tasks is written as follows:
For product A
For products B and C
The noninterference limit is written as follows. According to the figure, machine 1 should be used to produce products A and B. Since machine 1 can only be used to produce one product at a time, one of the following two equations must be written to avoid work interference on machine 1:
As mentioned, the above two constraints can be written as follows:
For machines 2, 3, and 4, the noninterference limit is as follows:
The delivery time limit is as follows.
In order to write the objective function, note that product A is completed in time xA4+a4, product B is completed in time xB4+b4, and product C is completed in time xC3+c3. If Z represents the time when all three products are completed, then the objective is to minimize Z as follows:
Converting integer variables into 0-1 variables
In integer programming models, the number of integer variables may be 0-1, and some may not be 0-1. To convert all variables of the model to 0-1, following two methods can be used:
A) Changing the integer variable as the sum of 0-1 variables. For example, if
If so, then the variable is changed as follows:
where yi=0 (i=1,…,6). The weakness of this method is revealed when there is a big number 50 instead of 6. In this case, the number of 0-1 variables increases from 6 to 50. That is,
In order to avoid increasing the number of 0-1 variables, the second method is suggested.
b) In this way, variable xj is replaced by a function of 0-1 variables obtained from the following relationship:
k is the smallest integer number that applies in the following relation and U is the upper limit for xj.
Example: Convert the integer variable x1 with the upper limit of 6 into 0-1 variables.
First, we consider k=1 and check that the result of the expression exceeds the upper limit?
If k=2, we have:
Because 7 is greater than 6, therefore the value of k becomes smaller by 2. Therefore, x1 can be written as follows:
which are y0,y1,y2=0,1. Since the value of x1 can be all integers up to 6, and in the constraints of the problem, we put the following relation.
According to the table below, the relationship y0+2y1+4y2 represents the variable x1.
Vehicle Routing Problem
In the Vehicle Routing Problem, which was first proposed in 1959 by Dantzig and Remser, the goal is to determine a set of routes for the delivery of goods for vehicles that are sent from the main service center to different demand points. According to the constraints in the model, we want to minimize the total travel cost of all the vehicles.
There is the main service center that has NV vehicles. To deliver the orders requested by the customers, this center sends the vehicle containing the orders to their address. Each customer i (i=1,…,n) has di units of demand. The capacity of each vehicle v is equal to kv (v=1,2,…,NV).
We also denote the travel cost between nodes i and j (arc (i,j)) by cij. If this cost depends on the type of vehicle, it is equal to cijv for vehicle v. All vehicles must be sent from main service center and returned to main service center, and each customer must be served by only one vehicle. We want to plan the travel path of each vehicle with the aim of minimizing the total travel cost of all vehicles. A view of the problem is shown in the figure below.
We see the application of vehicle routing problem in the daily services such as urban postal service, newspaper distribution services, and etc Also, there are some obvious assumptions in the model which are as follows.
1- The demand of each customer does not exceed the capacity of any of the available vehicles.
2- A customer’s request is fully satisfied by the assigned vehicle. That is, to deliver a customer’s order, the vehicle stops only once and the entire order is delivered.
To model the problem, the following variables are first defined:
The objective function and constraints of the problem are as follows:
The mathematical representation of the constraints is as follows:
Each node is served by only one vehicle:
If a vehicle enters a node, it must exit from the same node:
Vehicle capacity limit:
Each vehicle route can enter or leave the main service center only once if used:
As mentioned in the traveling salesman problem, in order to remove sub–tours from the possible solutions, the method mentioned in the traveling salesman problem is used.
In many real-world vehicle routing models, there is a time limit to travel each route. For example, the maximum time of sending a newspaper from the newspaper printing press to the newsstands should not exceed one hour. In this case, we show the maximum time allowed to travel a route by vehicle v with Tv. If tijv is the time required for vehicle v to travel the arc (i,j) and tiv is also the time required to deliver the goods at the i-th node by vehicle v. Then we have:
The decision variables are defined as follows.
Instead of one type of product, we could have several products. in this case the problem becomes Multicommodity VRP. We could also have several main service centers instead of one. In this case, we had the problem of multi-depot VRP. If the customers’ demand is a random variable with a certain probability distribution function, then we have a Stochastic VRP.
Examples
Example:
A young couple wants to divide the housework (shopping, cooking, washing dishes, laundry) between them in such a way that two tasks are assigned to each and the total time spent doing the tasks is minimized. Their efficiency in performing these tasks is different. The time each of them spends on each task is as follows:
Formulate this problem as a 0-1 programming.
Solution:
The decision variables are defined as follows:
Example: A company is considering investing in 6 major projects. The amount of returns of these investments in the long term, as well as the amount of capital required for these projects, are shown in the following table (in millions of dollars).
The total budget for investment is 100 million dollars. Projects 1 and 2 are incompatible and cannot be implemented both. Projects 3 and 4 are also like this. In addition, none of the projects 3 and 4 can be implemented unless one of the projects 1 and 2 is also implemented. There is no such limitation for other projects. The objective of the problem is to choose the best projects that maximizes the total return.
Solution: The decision variable is defined as follows.
If pj is the return (profit) for project j, cj is the cost of investing in project j, the model is as follows.
Example:
An airline is looking to purchase a new passenger plane that comes in three sizes: large, medium, and small. The purchase price of large, medium, and small planes is 33.5, 25, and 17.5 million dollars, respectively. The company has allocated 750 million dollars for the development of the fleet. Regardless of which aircraft is purchased, it is estimated that there will be enough passengers to fly the aircraft at full capacity. It is estimated that the annual profit of each of the large, medium, and small aircraft is 2.1, 1.5, and 1.15 million dollars, respectively.
It is expected that thirty pilots are available for these planes. The equipment and facilities are enough to maintain and repair 40 small planes, but the equipment and facilities needed to maintain and repair a medium and large plane are 4/3 and 5/3 times the equipment and facilities required for a small plane, respectively. How many of each type of aircraft should this company buy to maximize its profit:
Solution:
L, M, and S are the number of long, medium, and short planes, respectively. The integer programming model is as follows:
Example: The piecewise linear function is shown in the figure below. Provide an integer program model that expresses this piecewise linear function.
Solution:
To model the above curve, we show each x value as the sum of three variables δ1, δ2 and δ3. So we have:
where in:
In this case, the value of the function is the sum of three variables δ1, δ2 and δ3 as follows:
Note that δ1, δ2 and δ3 must have the following properties.
δ1: refers to a value of x that is greater than zero but smaller than 4.
δ2: The excess of x value from 4 until x is less than or equal to 10.
δ3: The excess of x value from 10 until x is less than or equal to 15.
In order for the above variable to exist, the following two binary variables are defined:
By defining the above two variables, the conditions can be expressed as follows:
Now we check the equality of conditions for different values of w1 and w2:
If w1=0, based on the relation 6w2≤δ2≤6w1, then w2=0 and therefore δ1, δ2 and δ3 are as follows.
In this case, 0≤x≤4
If w1=1 and w2=0, then the values of δ1, δ2 and δ3are as follows:
In this case, 4≤x≤10.
And finally, if w1=1 and w2=1, then the values of δ1, δ2 and δ3 are as follows:
In this case, 10≤x≤15.
Example: The urban population is concentrated in the I district and the i-th district has a population equal to pi. Using preliminary analysis, the candidate locations for the construction of the fire station are specified and equal to J. We want to find the best possible place to build a fire station and determine the allocation of districts to the selected fire stations.
Solution: The decision variables are defined as follows:
Since each restrict should be assigned to only one fire station, its mathematical representation is as follows:
None of the restricts should be assigned to a fire station that is not selected. That is, yj=0 results in xij=0. The simple representation of this constraint is as follows:
The distance between restrict i and the fire station of that restrict is equal to di, which is expressed as follows:
The total population covered by fire station j is:
Due to the importance of the central area of the city, fire stations 1 and 2 or fire stations 3 and 4 should be considered for the protection of this restrict. In this case, the mathematical representation is as follows:
Assuming that y=0 or 1, the constraint replaces the above two constraints as follows:
The cost of building a fire station in j district depends on the population of jth district and is limited to B. If this cost is a function of sj, fj(sj), then the budget limit for the construction of the fire station is as follows:
The objective function is to minimize the farthest distance of an restrict to the fire station assigned to that restrict. This objective function is as follows:
Finally, the complete model is as follows:
