Mursalin Ibne Salehin
In this article, we will learn to solve integer linear programming in Excel. In Microsoft Excel, users can quickly determine the solution of an integer linear program using the Solver add-in. Today, we will demonstrate this process with easy and quick steps. We will also discuss an example of a mixed-integer linear programming problem in the last section of this article. So, without any delay, let’s start the discussion.
Download Practice Book
You can download the practice book from here.
What Is Integer Linear Programming?
Integer linear programming is a type of mathematical method that consists of integer variables and linear objective functions and equations. With the help of linear programming, we can determine the minimum or maximum outcome of a given problem with some conditions. It is a tool that can be used to achieve a way to apply the limited resources in the best possible manner. All types of linear programming include some main factors. They are given below:
- Decision Variables: We determine the decision variables that minimize or maximize the objective function.
- Objective Function: This is a function that helps us to determine the decision variables. It expresses the relation between the result and the variables.
- Constraints: Constraints are also functions that denote different conditions on possible solutions.
Besides integer linear programming, we will also see an example of mixed-integer linear programming. The mixed-integer linear programming has both continuous and integer variables.
Step-by-Step Procedures to Solve Integer Linear Programming in Excel
To explain the step-by-step procedures, we will use the question below. You need to read it carefully to understand the basic things. You must derive the Constraints and Objective function after reading the question carefully.
Suppose, a machine is used to produce two interchangeable products. The daily capacity of the machine can produce at most 20 units of product 1 and 10 units of product 2. Alternatively, the machine can be adjusted to produce at most 12 units of product 1 and 25 units of product 2 daily. Market analysis shows that the maximum daily demand for the two products combined is 35 units. Given that the unit profits for the two respective products are $10 and $12, which of the two machine settings should be selected?
STEP 1: Analyze Question and Create Dataset
- First of all, we need to understand the given integer linear programming problem and analyze it carefully.
- Analyzing the above question, we have the findings below.
Decision Variables:
- X1: Production quantity of product 1.
- X2: Production quantity of product 2.
- Y: 1 if the first setting is selected or 0 if the second setting is selected.
Objective Function:
Here, the objective function is:
Z=10X1+12X2
Constraints:
We can mainly find 3 constraints from the above question. They are:
- X1+X2<=35
Because the market analysis shows that the maximum daily demand for the two products combined is 35 units.
- X1-8Y<=12
This constraint is specific for product 1.
- X2+15Y<=25
It is the constraint for the second product.
- Y={0,1}
The value of Y will be 0 or 1.
- X1,X2>=0
The quantity of the products can not be negative.
- In the following step, we have created a dataset like a picture below keeping the constraints, functions, and variables in mind. You can change it according to your needs.
Read More: How to Do Linear Programming with Sensitivity Analysis in Excel
STEP 2: Load Solver Add-in in Excel
- Secondly, we need to load the Solver add-in in Excel. If it is already loaded in your Excel, then, you can move forward to step 3.
- To do so, click on the File tab.
- After that, select Options from the left–bottom corner of the screen.
- It will open the Excel Options window.
- In the Excel Options window, select Add-ins.
- Then, select Excel Add-ins and click on Go in the Manage box.
- An Add-ins message box will pop up.
- Check Solver Add-in and select OK from the message box.
- Finally, you will see the Solver feature in the Analysis section of the Data tab.
Read More: How to Solve Blending Linear Programming Problem with Excel Solver
STEP 3: Fill Coefficients of Constraints and Objective Function
- Thirdly, you need to fill the constraints and objective function in the dataset.
- Here, we will mainly insert the coefficients of the constraints and objective function.
- Our first Constraint is that X1+X2<=35. It means if the first setting is selected then, the sum of the products should be equal to or less than 35.
- So, the coefficient of X1 is 1 and X2 is 2.
- Also, the equation indicates the first setting, so the coefficient of Y is 1.
- The sign is <=.
- And the limit is 35.
- Repeat the previous instruction and fill in the coefficients of all the constraints.
- After that, select Cell E10 and type the formula:
=SUMPRODUCT($B$6:$D$6,B10:D10)
In this formula, we have used the SUMPRODUCT function to calculate the product of decision variables with the respected constraints variables and then add them up. In this case, Cell B6 will be multiplied by Cell B10, Cell C6 by Cell C10, and Cell D6 by Cell D10. Then, all the products will be added together.
- Hit Enter and drag the Fill Handle down.
- Now, fill the coefficients of the objective function in Cell B16 to C16.
- In our case, the objective function is Z = 10X1+12X2.
- Again, select Cell E16 and type the formula below:
=SUMPRODUCT($B$6:$D$6,B16:D16)
- In the end, press Enter and you will see a dataset like the one below after inserting the coefficients and formulas.
Read More: How to Calculate Shadow Price Linear Programming in Excel
STEP 4: Insert Solver Parameters
- In step 4, go to the Data tab and select Solver from the Analyze section. It will open the Solver Parameters window.
- In the Set Objective box, you need to type the cell that will contain the value of the objective function.
- So, we have typed $E$16 here.
- Here, we are trying to find the maximum result.
- So, we have selected Max for the next step.
- In the ‘By Changing Variable Cells’ type $B$6:$D$6. It contains the decision variables.
STEP 5: Add Subject to Constraints
- In the fifth step, we need to add subjects to the constraints.
- We need to denote the type of variables whether they are binary or integer and the relation of the constraints.
- For that purpose, click on Add. It will open the Add Constraint dialog box.
- In the Add Constraint window, type $D$6 in the Cell Reference box and select bin from the drop-down menu.
- Cell D6 holds the value of Y which is 0 or 1. That indicates binary numbers. That is why we have selected the bin here.
- Click OK to proceed.
- Again, click on Add.
- This time, type $E$10:$E$12 in the Cell Reference box, <= symbol from the drop-down menu, and =$G$10:$G$12 in the Constraint box.
- Then, click OK.
- Once again, click Add in the Solver Parameters window.
- Now, type $B$6:$C$6 in the Cell Reference box and select int from the drop-down menu.
- Cell B6 and C6 store the value of X1 and X2 which are integers.
- Again, click OK.
STEP 6: Select Solving Method
- In step 6, select Simplex LP in the ‘Select a Solving Method’ section and click on Solve.
- Make sure ‘Make Unconstrained Variables Non-Negative’ is checked.
- After clicking on Solve, the Solver Results window will appear.
- Select OK from there.
STEP 7: Solution of Integer Linear Programming
- Finally, you will find the solutions in your desired cells on the excel sheet.
- In this case, the second machine setting will provide us with the best output.
STEP 8: Generate Answer Report
- Additionally, you can generate the answer report.
- In order to do that, select Answer in the Reports section of the Solver Results window and click OK.
- Lastly, you will find the report on a new sheet.
Mixed Integer Linear Programming Example in Excel
In this section, we will discuss a simple example of mixed-integer linear programming in Excel. You can follow the quick steps to solve mixed-integer linear programming in Excel easily. Let’s take a look at the objective function and constraints for this example.
Objective Function:
Z=2.39X1+1.99X2+2.99X3+300Y1+250Y2+400Y3
Constraints:
- X1+X2+X3=1000
- X1-400Y1<=0
- X2-550Y2<=0
- X3-600Y3<=0
Here, X1, X2, and X3 are integers. On the other hand, Y1, Y2, and Y3 are binary numbers. Also, we need to find the minimum value of Z.
Let’s follow the steps below to learn everything about the example.
STEPS:
- Firstly, create a dataset to store the coefficients of Decision Variables, Constraints, and Objective Function.
- Secondly, type mixed coefficients of the variables of the Objective Function.
- Thirdly, type the coefficients of the variables of Constraints like the picture below. Keep the Total column empty.
- After that, select Cell H10 and type the formula below:
=SUMPRODUCT($B$6:$G$6,B10:G10)
- Press Enter and drag the Fill Handle down.
- Now, type the formula below in Cell H6:
=SUMPRODUCT($B$6:$G$6,B10:G10)- Hit Enter.
- In the following step, go to the Data tab and select Solver. It will open the Solver Parameters window.
- In the Solver Parameters window, set the objective at Cell $H$6 to Min by changing variable cells $B$6:$G$6.
- Then, click on Add.
- At this moment, add the Constraints one by one and choose Simplex LP as the Solving Method.
- Click on Solve to proceed.
- As a result, the Solver Results window will appear.
- Click OK from there.
- Finally, the results will look like the picture below.
Read More: How to Perform Mixed Integer Linear Programming in Excel
Conclusion
In this article, we have demonstrated step-by-step procedures to Solve Integer Linear Programming in Excel. I hope this article will help you to perform your tasks easily. Moreover, we have also added the practice book at the beginning of the article. Furthermore, you can download it to test your skills. Also, you can visit the ExcelDemy website for more articles. Last of all, if you have any suggestions or queries, feel free to ask in the comment section below.
Hi Mursalin. Could you please explain how you got the constraint equations?
Hi KIM,
Thanks for your comment. To explain the step-by-step solution, we used the following question here.
“Suppose, a machine is used to produce two interchangeable products. The daily capacity of the machine can produce at most 20 units of product 1 and 10 units of product 2. Alternatively, the machine can be adjusted to produce at most 12 units of product 1 and 25 units of product 2 daily. Market analysis shows that the maximum daily demand for the two products combined is 35 units. Given that the unit profits for the two respective products are $10 and $12, which of the two machine settings should be selected?”
This question is also stated before starting STEP 1.
Analyzing the above question, we can find the following constraints:
Constraint 1:
X1+X2<=35
Because the maximum daily demand for the two products combined is 35 units.
Here, X1 is the quantity of Product 1 and X2 is the quantity of Product 2.
Constraint 2:
X1-8Y<=12
This constraint is for Product 1. In this constraint, we have combined the conditions for both settings for Product 1. In setting 1, product 1 can be produced at most 20 units; in setting 2, product 2 can be produced at most 12 units.
Here, Y denotes which setting is selected. If setting 1 is selected, then Y will be 1 and if setting 2 is selected, then Y will be 0.
For example, if setting 1 is selected, then we can set Y=1. So, the equation will be:
X1-8.1<=12
As a result, the simplified constraint will be X1<=20 which clearly states the condition for product 1 stated in the first setting.
Constraint 3:
X2+15Y<=25
This constraint is for Product 2. In this constraint, we have combined the conditions for both settings for Product 2. In setting 1, product 2 can be produced at most 10 units; in setting 2, product 2 can be produced at most 25 units.
Here, Y denotes which setting is selected. If setting 1 is selected, then Y will be 1 and if setting 2 is selected, then Y will be 0.
For example, if setting 1 is selected, then we can set Y=1. So, the equation will be:
X2+15.1<=25
As a result, the simplified constraint will be X2<=10 which clearly states the condition for product 2 stated in the first setting.
Constraint 4:
Y={0,1}
The value of Y will be 0 or 1. 1 represents the selection of setting 1 and 0 represents the selection of setting 2.
Non–Negative restriction:
X1,X2>=0
The quantity of the products can not be negative.
Constraints 1, 2 & 3 are the main constraints here.
In the Mixed Integer Linear Programming part, we have used a set of conditions as constraints where X1, X2, and X3 are integers and Y1, Y2, and Y3 are binary numbers.
I hope this explanation of the constraints will help you. Please let me know if you have any queries.
Regards
Mursalin,
Exceldemy.