Name:

MATP6620/ISYE6770
Integer and Combinatorial Optimization
Spring 2023

Midterm Exam, Tuesday, March 28, 2023.

Please do all four problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.

Q1       /30
Q2       /30
Q3       /15
Q4       /25
Total      /100
  1. (30 points) We consider a fixed charge network flow problem where there are both incoming and outgoing arcs at a node D, as illustrated below.

    The flow variables satisfy the fixed charge constraints 0 ≤ x1 ≤ 3y1 and 0 ≤ x2 ≤ 9y2 where yj is a binary variable. The set of feasible solutions at D is given by

    2 2 T = {x ∈ ℝ +,y ∈ B : x2 - x1 ≤ 2, 0 ≤ x1 ≤ 3y1,0 ≤ x2 ≤ 9y2 }.

    A fixed charge inequality is

    ∑ ∑ ∑ x2 + (9 - λ)+ (1 - y2) ≤ 2 + aj + λ yj + xj j∈C - j∈L - j∈N- \(C- ∪L-)
    		(1)

    where C- ⊆ N- = {1} and L- ⊆ N-\ C- are disjoint subsets and a 1 = 3 denotes the capacity of the incoming arc. The parameter λ = 9 -∑ j∈C-aj - 2.

    Note: We have three choices for C- and L-: (i) C- = {1},L- = ∅,N-\ (C-∪ L-) = ∅, (ii) C- = ∅,L- = {1},N-\ (C-∪ L-) = ∅, (iii) C- = ∅,L- = ∅,N-\ (C-∪ L-) = {1}.

    1. (10 points) Show equation (1) is satisfied by all points in T when y2 = 1, regardless of the choice of C- and L-.
    2. (15 points) Show equation (1) is satisfied by all points in T when y2 = 0, regardless of the choice of C- and L-.
    3. (5 points) The point x = (3, 5), y = (1,5 9) is in the LP relaxation of the feasible region. Show equation (1) is violated by this point, for two different choices of C- and L-.
  2. Let
    5 S = {x ∈ B : 5x1 + 7x2 + 4x3 + 3x4 + 5x5 ≤ 13}.

    1. (10 points) Show the valid inequality x2 + x4 + x5 ≤ 2 has Chvatal-Gomory rank equal to one.
      5 S = {x ∈ B : 5x1 + 7x2 + 4x3 + 3x4 + 5x5 ≤ 13 }.

    2. (10 points) Show that x2 + x4 + x5 ≤ 2 defines a facet of conv(S).
      5 S = {x ∈ B : 5x1 + 7x2 + 4x3 + 3x4 + 5x5 ≤ 13 }.

    3. (10 points) Strengthen the valid inequality x1 + x2 + x5 ≤ 2 by lifting it.
  3. Consider the MaxCut problem on K5, the complete graph on 5 vertices. Let V and E denote the sets of vertices and edges of K5, respectively. You may assume the convex hull of feasible solutions is full-dimensional.
    1. (5 points) Show from first principles that the maximum number of edges in any cut is 6.
    2. (10 points) It follows from part 3a that the constraint ∑ e∈Exe ≤ 6 is valid for the MaxCut problem on K5. How would you try to show that this constraint gives a facet of the convex hull of cuts? (Note: I do not want you to show that it is a facet; instead, I want you to tell me what points you might consider, and what you might try to do with those points.)
  4. (25 points; each part is worth 5 points) For each of the following statements, determine whether it is TRUE or FALSE, and give a short justification (one or two sentences).
    1. If G = (V,E) is a perfect graph then its complement graph is also perfect.
    2. Let G = (V,E) be a graph. If the maximum cardinality node packing on G has the same size as the minimum cardinality clique cover on G then G is a perfect graph.
    3. The node-arc incidence matrix of an undirected graph is totally unimodular.
    4. Assume x ∈ ℝ+n satisfies the inequalities gT x ≥ 1 and hT x ≥ 1. Then x also satisfies ∑ j=1n max{g j,hj}xj ≥ 1.
    5. Assume the nonnegative integer vector x satisfies x1 + 0.7x2 + 0.2x3 = 5.4. Then x also satisfies 0.2x2 + 0.2x3 ≥ 0.4.