Questions & explanations
1. Eliminate y from the system: x + y ≤ 2, x - y ≤ 1, y ≥ 0.
First, rewrite inequalities to isolate y: y ≤ 2 - x from first, y ≥ x - 1 from second, and y ≥ 0 from third. Combine lower bounds: y ≥ max(0, x-1). Upper bound: y ≤ 2-x. For feasibility, we need max(0, x-1) ≤ 2-x. This gives two cases: if x-1 ≥ 0, then x-1 ≤ 2-x → 2x ≤ 3 → x ≤ 1.5; if x-1 < 0, then 0 ≤ 2-x → x ≤ 2. Also x-1 < 0 gives x < 1. So overall x ≤ 1.5 and x ≥? From lower bound, we also need x-1 ≤ 2-x always? Actually, the condition is that there exists y, so the new system is x ≤ 1.5 and no lower bound on x from these? Wait, we also need x such that max(0,x-1) ≤ 2-x. This inequality defines the projection. So the projected system is just x ≤ 1.5? But also need x ≥? From y ≥ 0, we have x-1 ≤ 2-x always? Let's solve: For x < 1, condition is 0 ≤ 2-x → x ≤ 2, so all x < 1 work. For x ≥ 1, condition is x-1 ≤ 2-x → x ≤ 1.5. So overall x ≤ 1.5. So projection is x ≤ 1.5.
2. Compare Hoffman's bound to a simple rounding approach: which gives a tighter guarantee?
Hoffman's bound provides a theoretical guarantee on the distance from the relaxation solution to an integer feasible point, while simple rounding (e.g., rounding each variable to the nearest integer) may not always yield a feasible solution. The bound is often tighter because it accounts for the geometry of the feasible set. For instance, rounding could produce a solution far from optimal, whereas Hoffman's lemma ensures there exists an integer solution within a certain distance. However, the bound may be conservative in practice. In general, Hoffman's lemma gives a worst-case guarantee, while rounding can be heuristic.
3. Given a robust integer programming formulation for a network design problem with uncertain travel times, explain how to solve it using Benders decomposition.
Benders decomposition splits the problem into a master problem and subproblems. The master problem chooses integer variables (e.g., which arcs to build) without considering uncertainty. Then, for each scenario of travel times (or using robust constraints), a subproblem checks feasibility and optimality. The subproblem is a linear program that, if infeasible, generates a Benders cut to add to the master. For robust optimization, the subproblem must handle the uncertainty set, often by reformulating as a linear program with dual variables. The cuts gradually force the master to choose a robust solution.
4. What is a matroid?
A matroid is a mathematical structure that captures the idea of independence, like linear independence in vector spaces. It consists of a set of elements and a collection of subsets called independent sets, satisfying certain axioms. For example, in a graphic matroid, the elements are edges of a graph, and a set of edges is independent if it contains no cycle. Matroids generalize many combinatorial optimization problems. The intersection of two matroids is the set of subsets that are independent in both. Edmonds' theorem gives conditions for the existence of a common independent set of a given size.
5. Compare Edmonds' blossom algorithm with the Hungarian algorithm for assignment. How are they similar?
Both algorithms use augmenting paths to improve a matching. The Hungarian algorithm solves the assignment problem on bipartite graphs using potentials and alternating paths. Edmonds' algorithm generalizes this to non-bipartite graphs by handling odd cycles via blossom contraction. The Hungarian algorithm does not need contraction because bipartite graphs have no odd cycles. Both algorithms are polynomial-time and rely on finding augmenting paths. However, Edmonds' algorithm is more complex due to the blossom handling. They share the idea of iteratively improving a feasible solution until optimality.
6. Given two matroids on the same ground set, how can we find a maximum common independent set?
We can use Edmonds' matroid intersection algorithm, which is a polynomial-time method. It works by constructing an auxiliary bipartite graph and finding augmenting paths, similar to matching algorithms. The algorithm starts with an empty set and iteratively increases its size. At each step, it checks for an exchange opportunity using the matroid properties. The algorithm terminates when no augmenting path exists, yielding a maximum common independent set. The correctness relies on the matroid intersection theorem, which states that the maximum size equals the minimum over certain rank functions.
7. Compare robust optimization with stochastic optimization.
Robust optimization assumes the uncertain parameters belong to a set and seeks a solution that works for all worst-case scenarios. Stochastic optimization assumes a probability distribution and optimizes the expected value or a risk measure. Robust optimization is more conservative and does not require distributional knowledge, while stochastic optimization can give less conservative solutions if the distribution is known. Robust problems are often reformulated as convex programs, whereas stochastic problems may require sampling or scenario decomposition. Both are used to handle uncertainty.
8. Compare the matroid intersection problem with the bipartite matching problem. How is it more general?
Bipartite matching is a special case of matroid intersection. In bipartite matching, the two matroids are partition matroids: one for each side of the bipartition, where independent sets are those with at most one edge incident to each vertex. Matroid intersection generalizes this to any two matroids, allowing more complex constraints. For example, finding a maximum set of edges that is both a forest (graphic matroid) and has at most one edge per vertex (partition matroid) is a matroid intersection problem. Thus, matroid intersection is a powerful framework for many combinatorial problems.
9. How does robust optimization differ from stochastic programming?
Robust optimization assumes the uncertain parameters belong to a set and seeks a solution that works for all possibilities, without using probabilities. Stochastic programming assumes the parameters follow a known probability distribution and optimizes the expected value or a risk measure. Robust optimization is more conservative because it protects against the worst case, while stochastic programming may allow occasional constraint violations if they are unlikely. Robust optimization is often easier to solve when the uncertainty set is simple, but it may give overly pessimistic solutions.
10. Explain the matroid intersection polytope and its relation to Edmonds' theorem.
The matroid intersection polytope is the convex hull of characteristic vectors of common independent sets of two matroids. Edmonds' theorem characterizes this polytope via linear inequalities: a vector x is in the polytope if and only if it satisfies nonnegativity, the rank constraints for each matroid, and a certain submodularity condition. This description allows solving optimization over common independent sets using linear programming. The theorem also gives a min-max formula for the maximum size of a common independent set. This is a fundamental result in combinatorial optimization.
11. How does the convex hull of feasible integer points relate to the linear programming relaxation?
The linear programming (LP) relaxation of an integer program drops the integer constraints, giving a larger feasible region. The convex hull of the integer feasible points is a subset of the LP relaxation. The LP relaxation may have fractional extreme points, while the convex hull has only integer extreme points. Optimizing over the convex hull yields the integer optimum directly, but it is often difficult to describe. Valid inequalities cut off fractional points and approximate the convex hull. The goal of cutting plane methods is to tighten the LP relaxation to the convex hull.
12. Explain the main steps of Edmonds' blossom algorithm.
The algorithm starts with an empty matching. It repeatedly searches for an augmenting path using a breadth-first search from unmatched vertices. If it finds an augmenting path, it increases the matching size. If it encounters a blossom (an odd cycle), it contracts the blossom into a single vertex and continues the search on the contracted graph. Once an augmenting path is found in the contracted graph, it expands the blossom and updates the matching accordingly. The algorithm terminates when no augmenting path exists, meaning the matching is maximum. It runs in polynomial time.