Questions 1–5 of this homework are concerned with a knapsack problem with 20 objects,

A link to the data can be found in question 1 of the online version of this homework. In your initial formulation use variables x_j to indicate whether object j is used.

You will solve this problem using AMPL and CPLEX. The packages are available on LMS. More on these packages can be found at http://www.rpi.edu/~mitchj/ampldetails.html and also on LMS.

I lectured about AMPL in MATP 4700, and the videos are linked in LMS, and also available on Box from following the link on the webpage for that course, http://homepages.rpi.edu/~mitchj/matp4700/ (see Lecture 9C).

Part 1: introduction (14:17). Link: https://rensselaer.webex.com/webappng/sites/rensselaer/recording/play/3602c4e8d6cc489e994d7e176dd425bb

 Part 2: an example session. Note: You may want to play this lecture full-screen. (22:03). Link: https://rensselaer.webex.com/webappng/sites/rensselaer/recording/play/e0f03ef357db4444ada1977df3c143e6

1. Solve the LP relaxation of the problem, so each x_e satisfies 0 ≤ x_e ≤ 1. Show that this does not give an optimal solution to the knapsack problem. The LP relaxation model and data files are available online.
2. Find a feasible binary solution with value 35.
3. Improve the LP relaxation by adding in selected cover constraints

   for subsets C ⊆{1,…, 20}, where ∑ _j∈Ca_j > b. The ampl code for cover constraints is included in the model file, along with one commented-out line in the data file.

4. Show that adding in all covers of cardinality 3 does not give an optimal solution to the knapsack problem. Hint: AMPL syntax allows constraints of the form

   subject to cover3{i in 1..n-2, j in i+1..n-1, k in j+1..n}:
   x[i] + x[j] + x[k] <= 2;

5. Can you strengthen the cover inequalities to give a value of the relaxation that is closer to 35?
6. Consider the following LP, which we call problem (P):
   1. Solve (P) geometrically.
   2. What is the dual (D) of (P)?
   3. Write down the complementary slackness conditions for this problem and use them to solve the dual (D). Check your answer by evaluating the optimal costs for (P) and (D).
   4. For problem (D), what is the optimal basis matrix B? What are the reduced costs at the optimal solution? What are B^-1, B^-1N, c _B^T B^-1N, c _B^T B^-1b, and c_N^T - c _B^T B^-1N?
7. Model the following feasibility problem as an integer programming feasibility problem:

   Given a graph G = (V,E), does there exist a partition of the edges E into two sets E₁ and E₂ such that neither E₁ nor E₂ contains a triangle?

   Can you find a feasible solution to the LP relaxation of your formulation?