Reference no: EM132230637
1. Identify which statements about heuristics are true.
A heuristic is formulated as a linear program.
Traveling-sales-man and other vehicle-routing problems are typically not solved with heuristics in practice.
Heuristics are used to optimally solve complex problems in a reasonable amount of time.
A heuristic is used to identify a near-optimal solution in a reasonable amount of computing time.
At least one of the following methods is a heuristic: nearest neighbor, cheapest-insertion, Dijkstra's algorithm.
None of the above.
2. Which of the following statements about Integer Programming are true?
IP problems are much harder to solve, and take longer, that LP problems.
With integer programming, the feasible region becomes a collection of points.
IP and MILP are very similar, both force the decision variables to be integers.
Mass enumeration consists of finding the value of the objective function for each feasible solution.
Finding the optimal solution for an IP problem is easy, you just need to solve it as an LP problem and then round the solution to be an integer.
None of the above.
3. In the last weeks you learned about approximating the logistics cost. Which of the following statements are true?
To find an estimate for a typical one-to-many distribution problem you have to find an estimate for the local route, the line-haul, and the back-haul.
The Euclidean Metric is also referred to as L1 and the Manhattan Metric is also referred to as L2.
The circuity factor can take on any positive value.
To calculate an estimate of a logistics-cost problem you can break down a large problem into smaller pieces and quantify the pieces.
Everything else being equal, calculating point-to-point distances with the Euclidean Distance always yields less or equal values than using the Manhattan Metric.
None of the above.
4. Create a mixed integer linear program to optimally solve the problem outlined in Question 1. Use the result to identify which of the following statements are true.
The shortest route includes traveling from node T to node 2 and from node 5 to node 9.
The shortest route includes traveling from node T to node 1 and from node 1 to node 6.
The minimal costs associated with traveling from Tanzania to Kenya in the network given in Question 1 are 176 and it includes traveling from node 1 to node 6.
The minimal costs associated with traveling from Tanzania to Kenya in the network given in Question 1 are 173.
The shortest route includes traveling from node T to node 1 and from node 6 to node 8.
None of the above
5. You remember the nearest-neighbour-method (NMM) from your 'Introduction to Algorithms' class.
Which of the following statements are true?
The NNM will always find a better solution than using a mixed-integer linear program.
Heuristics are methods to balance the effort to reach and the accuracy of a solution.
The NNM will always find the optimal solution.
The NNM is a method to find a near-optimal solution.
The NNM is a heuristic.
None of the above