Operations Research (2): Optimization Algorithms Coursera Ans

Hello Friends in this article i am gone to share Coursera Course: Operations Research (2): Optimization Algorithms All Weeks Quiz Answers with you..

Operations Research (2): Optimization Algorithms

Enroll: Operations Research (2): Optimization Algorithms

ABOUT THIS COURSE

Operations Research (OR) is a field in which people use mathematical and engineering methods to study optimization problems in Business and Management, Economics, Computer Science, Civil Engineering, Electrical Engineering, etc.

The series of courses consists of three parts, we focus on deterministic optimization techniques, which is a major part of the field of OR.
As the second part of the series, we study some efficient algorithms for solving linear programs, integer programs, and nonlinear programs.
We also introduce the basic computer implementation of solving different programs, integer programs, and nonlinear programs and thus an example of algorithm application will be discussed.

WHAT YOU WILL LEARN

Learn how to use algorithms to solve different types of optimization programs.
Learn how to use Gurobi solver with Python to solve these problems efficiently.

SKILLS YOU WILL GAIN

Algorithms
Business Analytics
Mathematical Optimization

Operations Research (2): Optimization Algorithms Coursera Answers

Note: Due to a very hard formatting some questions are incomplete but answers are 100% correct.

Quiz for Week 1

Question 1)
(Special note: Below there are five questions for you to answer. Naturally there are many mathematical formulas and equations in the problem statements. However, due to some technical issues on Coursera, from time to time for some learners, some formulas and equations cannot be displayed correctly (while some others can). As there is no way for the instructing team to solve this issue, we post all the problem statements in a PDF file here. If unfortunately some formulas and equations are not readable for you, please use the PDF file to prepare your answers and then come back to Coursera to choose/fill in your answers.)
Among the following terms, which is not going to be introduced in this course?

Advanced solvers.
Exact algorithms.
Data mining.
Heuristic algorithms.
None of the above.

Question 2)
Among the following terms, which is not a characteristic of heuristic algorithms?

Completing execution in a reasonably short time.
Finding an optimal solution every time.
Finding a feasible solution when the problem is too complicated.
All of the above.
None of the above.

Question 3)
Please solve the following linear system by Gaussian elimination

\[\begin{split}
u+2v+3w&=19 \\
4u+3v+2w&=41 \\
2u-6v+w&=-2. \\
\end{split}\]

What are the values of uu, vv, and ww?

uu = 7, vv = 3, ww = 1.
uu = 4, vv = 2, ww = 1.
uu = 7, vv = 2, ww = 2.
uu = 7, vv = 3, ww = 2.
The system is singular.

Question 4)
Regarding the following three vectors, which statement is not true?

\[x = \begin{bmatrix}
2 \\
4 \\
-2
\end{bmatrix},
y = \begin{bmatrix}
1 \\
3 \\
-2
\end{bmatrix},
z = \begin{bmatrix}
1 \\
-1 \\
2
\end{bmatrix}\]

If we put all vectors into the columns of a matrix, the number of pivots is 2.
The three vectors are linearly dependent.
There are exactly 2 linear independent vectors.
We may linearly combine xx and yy to generate zz.
If we put all vectors into the columns of a matrix, the matrix is nonsingular.

Question 5)
Which of the following statements is not true?

The time complexity of Gaussian elimination is $$O(n^3)$$ for an $$n$$x$$n$$ linear system.
A linear system must be singular when a zero appears in a pivot position during the Gaussian elimination process.
If a matrix AA is invertible, the A−1 must be unique.
A square matrix is nonsingular if and only if it is invertible.
If we have mm nn-dimensional vectors, they must be linearly dependent if m > nm>n.

Quiz for Week 2

x1+x2+x3+1,16
$$x_1 + x_2 + x_3 = 16$$.
$$x_1 + x_2 – x_3 \geq 16$$.
$$x_1 + x_2 – x_3 = 16$$.
None of the above.

Question 2)
Following from the previous problem, we may list all the basic solutions of the standard form. For this example, there should be $$A$$ basic variables and $$B$$ nonbasic variables in each basic solution. There are $$C$$ basic solutions and $$D$$ basic feasible solutions.

$$A = 3$$, $$B = 2$$, $$C = 10$$, and $$D = 4$$.
A = 2A=2, B = 3B=3, C = 10C=10, and D = 4D=4.
A = 2A=2, B = 3B=3, C = 9C=9, and D = 4D=4.
A = 3A=3, B = 2B=2, C = 4C=4, and D = 9D=9.
None of the above.

Question 3)
Following from the previous problem. Use the simplex method to solve the linear program. After a few iterations, we obtain an optimal tableau

where AA, BB, and CC are missing. Please write down these missing values in the order of AA, BB, and CC by separating two consecutive values with a comma. Do not have any symbol other than numeric values, negation, and comma in your answer.

5, 3, 8

Question 4)
Following from the previous problem, what is an optimal solution to the original LP?

(x1,x2)=(16,0).
The original LP is infeasible.
The original LP is unbounded.
None of the above.

Question 5)
Consider the following LP

Use the simplex method with the two-phase implementation to solve the LP. Write down your conclusion. If you find an optimal solution, write it down in the order of x_1x
1 and x_2x 2 by separating two consecutive values with a comma. Do not have any symbol other than numeric values, negation, and comma in your answer. For example, if you believe an optimal solution is (0, 0)(0,0), write down “0,0”. If you conclude that the problem is infeasible or unbounded, write down a single character “I” or “U”, respectively.

Quiz for Week 3

In this problem, we will use the branch-and-bound algorithm to solve the following IP

As always, our first step is to solve the linear relaxation of the given IP. Write down the unique optimal solution in the order of x1 and x2 by separating two consecutive values with a comma. Do not have any symbol other than numeric values, negation, decimal point, and comma in your answer. For example, if you believe an optimal solution is (0.2, -2.3)(0.2,−2.3), write down “0.2,-2.3”.

8.5,7.5

Question 2)
Following from the previous problem, branch on $$x_1$$ to obtain two subproblems. What are the two constraints you add to the first subproblem to generate the two new subproblems?

$$x_1 = 8$$ and $$x_1 = 9$$.
$$x_1 \leq 8$$ and $$x_1 \leq 9$$.
$$x_1 \leq 8$$ and $$x_1 \geq 9$$.
$$x_1 \leq 8$$ and $$x_2 \leq 7$$.
None of the above.

Question 3)
Following from the previous problem, find an optimal solution to the original IP. Write down the unique optimal solution in the order of $$x_1$$ and $$x_2$$ by separating two consecutive values with a comma. Do not have any symbol other than numeric values, negation, and comma in your answer. For example, if you believe an optimal solution is $$(2, -3)$$, write down “2,-3”.

Question 4)
Recall the following parallel machine makespan minimization problem we introduced in the past. There are mm machines and n jobs. For job j, we know its processing time is pj We want to assign each job to a machine so that the makespan, which is the longest total processing time among all machines, is minimized. For example, suppose that we have n = 15 jobs and m = 3 machines. The processing times are listed in Table 1. These data define an instance for the parallel machine makespan minimization problem.

While this problem is NP-hard, it is straightforward to consider the following heuristic algorithm. We simply assign each job one by one to a machine. When a job is to be assigned a machine, it is assigned the machine currently with the smallest total processing time (if there is a tie, choose the machine with the smallest machine ID among those machines having the smallest total process time).

For example, suppose that we assign jobs to machines in the order the job IDs, from small to large. We will then assign job 1 to machine 1, job 2 to machine 2, job 3 to machine 3, and then job 4 to machine 2 (because at that moment machine 2 has the smallest total processing time, which is 4), and then job 5 to machine 3, …, and finally job 15 to machine 3. The result of applying the simple heuristic algorithm is in Table 2. The makespan of the simple heuristic algorithm on this instance is 45.

Question 5)
Following from the previous problem, whenever we apply a heuristic algorithm on an instance and obtain a feasible solution, we want to evaluate its performance by calculating the optimality gap. For the instance above, as we do not have an optimal solution, we look for a lower bound on the makespan of an optimal solution. To do this, note that we may formulate an IP for the makespan minimization problem, we may then solve its linear relaxation to obtain a lower bound. For the makespan minimization problem, however, there is an easier way: All

Quiz for Week 4

Question 2)
Let’s solve

by gradient descent. Let x^0 = (1, 0) be the initial solution. Run on iteration of gradient descent to find the next solution x^1.In each iteration, let the step size be that bringing you to the global minimum along the improving direction. Follow the output format requirement provided in Question 1.

Question 3)
Then find its determinant. Write down a single number. Do not have any symbol other than numeric values, negation, and decimal point in your answer. Do not have unnecessary zeros at the end of a number. For example, if you believe the determinant is -9.01−9.01, write down “-9.01−9.01”.

Question 4)
Let’s solve
by Newton’s method. Let x^0 =(6,6) be the initial solution. Run on iteration of Newton’s method to find the next solution x^1. Follow the output format requirement provided in Question 1.

Question 5
Which of the follow statements are correct? Check all correct answers.

Gradient descent is an interior-point method, i.e., its search path is not restricted in the boundary of the feasible region of an optimization problem.
Gradient descent is always slower than the Newton’s method in solving a nonlinear optimization problem.
Gradient descent is a first-order method, i.e., it does not require any information about the second-order derivative of the objective function.
The Newton’s method always find an optimal solution when it is used to solve an unconstrained minimization problem whose objective function is quadratic with upward curvature.
All of the above.

Quiz for Week 5

According to the instructor, what are the major sources of costs in the facility location problem introduced in this week? Check all the correct answers.

Office rent.
Traveling cost.
Engineer hosting cost.
Engineer training cost.
Facility construction cost.

Question 2)
Which of the following statements best describes the main decision to make in the facility location problem discussed in this week?

For each location, determine the facility scale and facility type.
For each location, determine the facility scale and number of engineers hosted here.
For each location, determine the number of engineers hosted here.
For each location, determine whether to build a facility there.
None of the above.

Question 3)
What of the following is not one of the three models we need in an Operations Research study?

Which of the following statement is correct?

A conceptual model.
A mathematical model.
A universal model.
A computer model.
All of the above.

Question 4)
Recall that in the facility location problem discussed in this week, there is a constraint saying that for each customer and each location, only a built facility may serve customers. The mathematical formulation is

The new feasible region becomes smaller or the same. The new formulation is wrong.
The new feasible region remains the same. The new formulation is correct.
The new feasible region becomes larger or the same. The new formulation is wrong.
The new feasible region may become smaller or larger. The new formulation is wrong.
None of the above.

Question 5)
Which of the following is the most appropriate category of the heuristic algorithm introduced in this week?

A brute-force algorithm.
A divide-and-conquer algorithm.
A greedy algorithm.
A dynamic programming algorithm.
A backtracking algorithm.

Quiz for Week 6

Question 2)
A city is divided into nn districts. The time (in minutes) it takes an ambulance to travel from District i to District j is denoted as dij. The population of District i (in thousands) is p_i. An example is shown in Table 2 and Table 3. The distances between districts are shown in Table 2, and the population information is shown in Table 3. In this instance, we have n = 8 districts. We may see that, e.g., it takes 5 minutes to travel from District 2 to District 3, and there are 40,000 citizens.

Question 3)
Continue from the previous question. For any value of mm, consider the following heuristic algorithm which runs mm iterations. In each iteration, we locate an ambulance in a district that (1) currently does not have an ambulance, and (2) may minimize the maximum population-weighted firefighting times among all districts. If there are multiple districts satisfying these two conditions, pick the one with the smallest district ID among them. We then proceed to the next iteration to look for the next district to locate an ambulance.