MATP6620/ISYE6760 Combinatorial Optimization & Integer Programming

Homework 2.

Solutions

Due: Thursday, February 18, 2021, by end of day.

Penalty for late homeworks: 10% for each day or part of a day.

- A method for representing a spanning tree on the complete graph on vertices {1,…,n} as a string of n - 2
numbers was presented in class. Find the trees with 8 vertices corresponding to the following
strings:
- 543156.
- 768773.
- 543854.

Solution:

- Show that
^{T}x : x ∈ S}? Why? How do the feasible regions of the LP relaxations compare?Solution:

The three formulations of S are equivalent since all three sets consist of the points

and all binary points that are smaller than at least one of these points.

The most effective formulation is the one with the tightest LP relaxation. Denote the feasible regions of the LP relaxations as

while

so neither set contains the other.

If x ∈ S

_{2}thenor equivalently

which dominates the inequality defining S

_{1}, so S_{2}⊆ S_{1}.Similarly, if x ∈ S

_{3}thenor equivalently

which dominates the inequality defining S

_{1}, so S_{2}⊆ S_{1}.Thus, S

_{1}is the weakest formulation. It is not easy to compare the other two formulations; the better one will depend on the objective function. The inequalities in the third formulation can be obtained by one C-G rounding from the second formulation, and vice versa. - 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

_{1}and E_{2}such that neither E_{1}nor E_{2}contains a triangle?Is the LP relaxation to your formulation feasible?

Solution:

Let the binary variable indicate whether an edge is in E

_{1}, so we wantIf three edges constitute a triangle in E then we need the sum of their x-values to be either 1 or 2. Otherwise, if the sum is 3 then all three edges are in E

_{1}, and if the sum is 0 then all three edges are in E_{2}. So the binary variables x_{e}must satisfy the constraintsThe LP relaxation is feasible: take all x

_{e}= 0.5.Note that the original combinatorial feasibility problem is not necessarily feasible: consider the case of a complete graph on 6 vertices.

- Assume you have an algorithm A for finding the minimum weight perfect matching in a graph with
nonnegative edge weights. How could you use this algorithm to find the maximum weight matching in
a graph G = (V,E) with nonnegative edge weights? (Note: the matching isn’t required to be
perfect.)
Solution:

If |V | is odd, we first add an extra vertex.

We then complete the graph, giving the added edges length 0 so any maximum weight matching is still a maximum weight matching.

Let W be the largest edge weight.

We create a perfect matching problem by using new weights

Note that any perfect matching uses exactly ⌈|V |∕2⌉ edges. Let M be a matching in the original graph. With the construction, this corresponds to a matching in the modified graph. Because every perfect matching contains the same number of edges, we have

so finding the minimum weight perfect matching is equivalent to finding the maximum weight matching in the original graph.

- Assume we have a polynomial time algorithm for determining the optimal value of binary knapsack problems
of the form max{c
^{T}x : x ∈ B^{n},a^{T}x ≤ b}. This algorithm does not tell us the values of the variables in the optimal solution. Show that we can use this algorithm as a subroutine in a polynomial time algorithm for finding the optimal solution to a binary knapsack problem.Solution:

We can find the optimal value of n + 1 binary knapsack problems. At each iteration, the number of variables in the knapsack problem is reduced, and the right hand side might be changed. We define

Algorithm:

- Initialize with k = n, q = b, and find the value v
_{b}^{n}of the original problem. Initialize the set of objects in the optimal solution to S = ∅. - Reoptimize to find v
_{q}^{k-1}.- If v
_{q}^{k-1}= v_{q}^{k}then object k is unnecessary, so can set x_{k}= 0 permanently. - If v
_{q}^{k-1}< v_{q}^{k}then object k is necessary, so can set S = S ∪{k}. Update q ← q - a_{k}.

- If v
- Set k = k - 1.
- If k ≥ 1, return to 5b.
Otherwise, STOP and return S.

Note that the algorithm works even if there are multiple optimal solutions: an item is discarded if and only if there is an optimal solution remaining that doesn’t include the item. The particular solution returned depends on the ordering of the items.

- Initialize with k = n, q = b, and find the value v

John Mitchell |

Amos Eaton 325 |

x6915. |

mitchj at rpi dot edu |

Office hours: Monday and Thursday 1pm–2pm. |

webex: https://rensselaer.webex.com/meet/mitchj |