Artificial Intelligence
5. Optimization & Decision-making Algorithms
Lesson 3 Route Optimization Problem
Lesson Route Optimization Problem - Artificial Intelligence - ثالث ثانوي
Part 1
1. Basics of Artificial Intelligence
2. Artificial Intelligence Algorithms
3. Natural Language Processing (NPL)
Part 2
4. Image Recognition
5. Optimization & Decision-making Algorithms
Mathematical Programming In Optimization Problems
Table 5.2: Examples of decision and state variables
The objective function is formulated as a mathematical expression
The Knapsack Problem
A knapsack instance is illustrated in figure 5.6 with six items having specific weights
The code creates a list x to store the binary decision variables for the items. The mip library provides:
for each item
Traveling Salesman Problem
The following code can be used to create an instance of the TSP.
The following code used the above function to create a TSP instance with 8 locations and pairwise distances between 5 and 20:
Creating a Brute-Force Solver for the Traveling Salesman Problem
The brute force solver uses the permutations() tool to create all possible routes. Note that the startstop
The brute force solver computes the total distance of each route and
Using MIP to Solve the Traveling Salesman Problem
The following code uses the Python mip library to create an MIP solver. It then adds one binary decision variable for every possible transition in the TSP instance generated above.
The above code uses the numpy.full() tool to create N×N numpy array for storing the binary x variables.
The next step is to ensure that the solver only reports solutions that visit each location,
The complete formulation of the TSP includes one more type of constraint to ensure the computation
As an example, consider the 1→2→1 route in the 2-route solution of the TSP instance shown
The following code generates 100 TSP instances with 8 locations and a distance range between5
The results verify that the MIP solver reports the optimal solution for 100% of the problem instances.
Explain how mathematical programming can be used to solve complex optimization problems.
What are the advantages and disadvantages of the MIP approach for solving optimization problems?
Analyze two optimization problems that can be solved with mathematical programming and outline their state and decision variables.
List three different optimization problems from the family of routing problems.
You want to create a brute-force solver function for the Traveling Salesman Problem. Complete the following code so that the solver function returns the best route and best total distance.
You want to create an MIP solver for the Traveling Salesman Problem. Complete the following code so that the decision variables and connectivity constraints are selected correctly.
