Given n objects, we want to find an ordering (or permutation) of the objects, so, given two objects i and j, either i is before j or j is before i. We can model the set of orderings by introducing variables x_ij for 1 ≤ i,j ≤ n defined as follows:

The set of feasible solutions can be written as

The inequalities are called triangle inequalities. You may assume that the dimension of P_LOⁿ is n(n - 1)∕2.

1. Solve the integer program min{c^Tx : x P_LOⁿ} with n = 8 using a cutting plane algorithm, adding violated triangle inequalities as cutting planes. The objective function coefficients c are as follows:

   with c_ij = 0 for i > j. (Hint: the optimal value is 22.)

2. Let a^Tx ≤ b be a facet-defining inequality for P_LOⁿ. Define _ij for 1 ≤ i,j ≤ n + 1 by:

   Prove that ^Tx ≤ b is a facet defining inequality for P_LOⁿ⁺¹.

3. Use the result of Question 2 to show that the simple bounds x_ij ≥ 0 and x_ij ≤ 1 and the triangle inequalities all define facets of P_LOⁿ for n ≥ 3.
4. Let U = {u₁,…,u_k} and W = {w₁,…,w_k} be two disjoint subsets of the objects. Show that the inequality

   is valid for P_LOⁿ. (Note that the inequality includes k edges pointing up in the picture and k(k - 1) = k² -k edges pointing down.)

   

5. Find a point ℜ^n(n-1), 0 ≤_ij ≤ 1, which satisfies _ij + _ji = 1 for 1 ≤ i,j ≤ n and all the triangle inequalities, but which violates the inequality in question 4. (Hint: such a point exists when k = 3.)