MATP6620/DSES6760 Combinatorial Optimization & Integer Programming
Homework 2.

Due: Friday, February 18, 2011, in class.
Penalty for late homeworks: 10% for each day or part of a day.

  1. In an uncapacitated facility location problem, the constraint that material can only be shipped from an open facility can be modeled using either aggregated or disaggregated constraints. AMPL model files for these two alternatives can be found at
    http://www.rpi.edu/~mitchj/matp6620/hw2/uflRagg.mod
    http://www.rpi.edu/~mitchj/matp6620/hw2/uflRdisagg.mod

    Generate a problem instance with m ≥ 10 warehouses and n ≥ 40 customers, changing the seed used in the model from 421415. Use the AMPL command let m := 10; to set m and n. Solve your problem with each of the two models. Next, turn off cplex’s cut generation subroutines using the command:

    option cplex_options ’mipcuts=-1’;

    and solve your problem again with the two models. What do you conclude? (Include your values of m, n, and randseed in the solution you hand in.)

  2. Show that
    3 S := {x ∈ ZZ +3 : 7x1 + 9x2 + 12x3 ≥ 17} = {x ∈ ZZ + : 4x1 + 5x2 + 6x3 ≥ 10} = {x ∈ ZZ3+ : x1 + x2 + x3 ≥ 2, 2x1 + 3x2 + 4x3 ≥ 6}.
    Which formulation do you think is most effective for solving max{cTx : x ∈ S}? Why? You may want to experiment with AMPL to confirm your answer.
  3. 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 E1 and E2 such that neither E1 nor E2 contains a triangle?

    Is the LP relaxation to your formulation feasible?

  4. Assume we have a polynomial time algorithm for determining the optimal value of binary knapsack problems of the form max{cTx : x ∈ IBn,aTx ≤ 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.
  5. Using the Hamiltonian path problem, or otherwise, show that the following problem is NP-complete.

    Given a graph G = (V,E) and a set L ⊆ V , is there a spanning tree T of G such that the set of leaves is L?

    (A leaf of a tree is a vertex of degree 1. The Hamiltonian path problem is: Given a graph G = (V,E), does there exist a path which visits all the vertices of G exactly once? You may assume that this problem is NP -complete.)

    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Tuesday, Wednesday, 2-3pm.