Skip to main content

8. Optimization - Linear Programming

 

Introduction

Linear programming is a family of problems that optimize a linear equation (an equation of the form y = ax₁ + bx₂ + …).

Linear programming will have the following components:

A cost function that we want to minimize: c₁x₁ + c₂x₂ + … + cₙxₙ. Here, each x₋ is a variable and it is associated with some cost c₋.

A constraint that’s represented as a sum of variables that is either less than or equal to a value (a₁x₁ + a₂x₂ + … + aₙxₙ ≤ b) or precisely equal to this value (a₁x₁ + a₂x₂ + … + aₙxₙ = b). 

In this case, x₋ is a variable, and a₋ is some resource associated with it, and b is how many resources we can dedicate to this problem.

Individual bounds on variables (for example, that a variable can’t be negative) of the form lᵢ ≤ xᵢ ≤ uᵢ.


Background/ Interest

This report is a part of the “Artificial Intelligence” course at City University, Dhaka, Bangladesh conducted by Nuruzzaman Faruqui. This is the best AI course in Bangladesh. 


In this course, we learned AI from scratch. We started from Basic python and ended in Natural language processing. We learned theoretical concepts, essential mathematics properly in the “CSE 417: Artificial Intelligence” course, then implemented our knowledge in the Lab course 'CSE 418: Artificial Intelligence Laboratory'. We have done a lot of lab sessions to master the course and gradually we learned each necessary concept of Artificial Intelligence. 

Now we can build our machine learning model and also can build a neural network to solve a complex problem.


Problem Statement

Consider there are two machines, X₁ and X₂,


  • X₁ costs $50/hour to run, X₂ costs $80/hour to run. The goal is to minimize cost. 

  • This can be formalized as a cost function: 50x₁ + 80x₂.

  • X₁ requires 5 units of labor per hour. 

  • X₂ requires 2 units of labor per hour. 

  • Total of 20 units of labor to spend. 

  • This can be formalized as a constraint: 5x₁ + 2x₂ ≤ 20.

  • X₁ produces 10 units of output per hour. 

  • X₂ produces 12 units of output per hour. 

  • The company needs 90 units of output. 

  • This is another constraint. 

  • It can be rewritten as 10x₁ + 12x₂ ≥ 90. 

  • However, constraints need to be of the form (a₁x₁ + a₂x₂ + … + aₙxₙ ≤ b) or (a₁x₁ + a₂x₂ + … + aₙxₙ = b). 

  • Therefore, we multiply by (-1) to get to an equivalent equation of the desired form: (-10x₁) + (-12x₂) ≤ -90.


An optimizing algorithm for linear programming requires background knowledge in geometry and linear algebra that we don’t want to assume. Instead, we can use algorithms that already exist, such as Simplex and Interior-Point.

We will use the scipy library in Python to solve the problem.


The Python code to implement Linear Programming

import scipy. optimize

 

result = scipy.optimize.linprog(

   #Cost function : 50x_1 + 80x_2

   [50,80],

 

   #coefficients for inequalities

   A_ub=[

   [5,2],

   [-10, -12]

   ],

 

   #constrains for inequalities

   b_ub=[20,-90]

)

 

if result.success:

   print(

       f"X1: {round(result.x[0], 2)} hours"

   )

   print(

       f"X2:{round(result.x[1], 2 )}hours "

   )

 

else:

   print("No solution")


Result


Conclusion

In this lab report, we learned how to implement Linear Programming to optimize solutions.  However, you can optimize other similar problems by implementing the code snippet given above. This is a simple and easier implementation of the “ CSE 418: Artificial Intelligence Lab” course at City University, Dhaka, Bangladesh conducted by Nuruzzaman Faruqui Sir. Which is the best AI course in Bangladesh. 


You are free to copy the code from here or some other concluding remarks for your project.
Labels:

Popular posts from this blog

7. Optimization - Hill-Climbing Algorithm with "Random Restart" variant

Optimizing Cost Function Through Hill Climbing Algorithm & Random Restart Variant Introduction Hill climbing is a mathematical optimization algorithm, which means its purpose is to find the best solution to a problem that has a (large) number of possible solutions. Explaining the algorithm (and optimization in general) is best done using an example. In the Travelling salesman problem, we have a salesman who needs to visit a number of cities exactly once, after which he returns to the first city. The distances between each pair of cities are known, and we need to find the shortest route. As you can imagine, there is (often) a large number of possible solutions (routes) to a specific Travelling salesman problem; the goal is to find the best (i.e. the shortest) solution. Hill Climbing Variants Due to the limitations of Hill Climbing, multiple variants have been thought of to overcome the problem of being stuck in local minima and maxima. What all variations of the algorithm have in co...
Read more

9. Machine Learning - Banknote Authentication

  Building Machine Learning Model to Classify Fraud Bank Note Introduction Machine Learning!!!🤪 The highly interesting technology in today's world 😉. I know that you have heard a lot about it. Today we are going to build a machine learning model to authenticate banknote where it's authentic or not 💵.  Whenever you go to the bank to deposit some cash, the cashier places banknotes in a machine that tells whether a banknote is genuine or counterfeit.  The machine uses some classification techniques to do it. There are many machine learning algorithms for classification. Classification is a type of supervised machine learning. There are multiple machine learning algorithms in the classification. We understand it's hard to know the theoretical concept of each algorithm as a beginner. If it's true for you,  there is nothing to panic about.🤪  We will implement the 'K nearest neighbor, Support vector machine, Perceptron learning & Gaussian naive Bayes' algorithm...
Read more

3. Knowledge- The Clue Game

Knowledge - Represent Knowledge Using Propositional Logic In Python Introduction Representing knowledge is the key issue in Artificial Intelligence. We can develop a knowledgeable AI agent that can analyze like humans. In this lesson, we will develop a game engine that will detect a murder based on its knowledge base.  If we want a machine to be intelligent enough to think like a human, then first the machine needs some information about the real-world situation/problem. The knowledge of the real world needs to be represented to the machine in the right manner that is readable to a computer system. Propositional logic is one of the simplest methods of knowledge representation to a machine. In this lesson, we will implement propositional logic to make our game engine knowledgeable, and then we will make able the engine to detect the murderer. Background/ Interest This report is a part of the “ CSE 418: Artificial Intelligence Lab” course at City University, Dhaka, Bangladesh conduct...
Read more