Homework 3 CHALLENGE: PROBLEMS ON GRAPHS & NETWORKS

Homework 3

INSTRUCTIONS
All homeworks will have many problems, both theoretical and practical.
Programming exercises need to be submitted via SMARTSITE using the assignment boxes NOT DROPBOX.
Other methods of submission without prior approval will receive zero points.
Write legibly preferably using word processing if your hand-writing is unclear. Be
organized and use the notation appropriately. Show your work on every problem.
Correct answers with no support work will not receive full credit.
1. CHALLENGE: PROBLEMS ON GRAPHS & NETWORKS: We saw how the networks can be
used to plan for building projects or to schedule the parts of a project. Here are some some more
challenges:
• Let G be a directed graph with distances or costs on its arcs and two special vertices s, t. We
are interested on the “longest” paths using two possible definitions
– If we call the length of a path the sum of the lengths on the path. Write a model to
compute the longest path on a network.
– If we instead call the length of a path the largest length among arcs the path, write another
model to compute the longest path on a network under this definition.
• Consider again, the TSP for n cities and cost of travel cij . Write a new model for the TSP,
different from the one we saw in class. This time us the binary variables xi,j,k, which are 1if
the k-th leg of the trip, the salesman goes from city i to city j. Your formulation must have a
cubic number of constraints.
2. CHALLENGE: FINDING A GOOD MATCH: Matching problems appear everywhere in applications. E.g., how do students get matched to medical schools? How do workers get assigned to jobs
at work? How do organ donors get match to patients in need?
We can model matchings in graphs. A set M of the edges E is called a matching of G if and only
if:
∀u ∈ V, |{e ∈ M | u ∈ e}| ≤ 1
In other words, a vertex is incident to at most one edge of M. A matching M is said to be maximal
if there is no matching M0 with M ⊂ M0
. A maximal matching of the largest cardinality is a
maximum matching. The size of a maximum matching is denoted by OPTG.
In the following exercises we will explore several approaches to find a maximum matching in a graph:
a. Let M be a matching and let us denote by V (M) the set of endpoints of edges in M:
V (M) := {u | ∃e ∈ M, u ∈ e}
Show that when M is a maximal matching of G, V (M) is a vertex cover of G.
b. Let M be a maximal matching of G, show that |V (M)| ≤ 2OPTG.
c. Now consider the following greedy algorithm for finding a maximum matching: Start with an
arbitrary edge as the very first matching. Find another edge that does not have a vertex in
common with the current matching. If one exists add it to the current matching. Repeat until
no more edges can be added.
d. What is the running time of this algorithm on a graph with n nodes and m edges?
e. Give an example where the algorithm fails to find a maximum matching. But show that the
greedy method always yields a solution that has at least half as many edges as a true maximum
matching.
f. Give now an integer-optimization model (i.e., now based on linear equations, inequalities) to
construct a maximum matching of any graph. G.
3. Let G be a graph with two distinguished vertices s, t. An even st-path is a path from s to t with an
even number of edges. Show that we can formulate the problem of finding an even st-path with as
few edges as possible as a minimum cost perfect matching problem. HINT: Construct an auxiliary
graph H from G, make a copy of the graph G, and remove vertices s, t. Call that new graph G0
.
Construct H starting with the union of G, G0 and joining every vertex v ∈ G different from s, t with
its copy in G0
. Use H.
4. THEORY PROBLEMS: GEOMETRY OF INTEGER SOLUTIONS:
• MEDITATE ABOUT THIS: In the previous problems you dealt with several types of combinatorial optimization problems. Which ones have polynomial time solution? Which ones are
NP-hard? Discuss whatever information you find about their complexity.
• Suppose S = {(y1, y2) ∈ Z
2
: y1 −y2 ≤ 2, 3y1 +y2 ≤ 21, y1 + 5y2 ≤ 34}. Find (a) An inequality
description of convex hull of S. (b) Find the extreme points of conv(S).
• Use the branch-and-bound method to solve the following optimization problem. Show the
solution graphically:
min y1 + 3y2
subject to:y1 + 5y2 ≤ 12,
y1 + 2y2 ≤ 8,
y1, y2 ≤ 0 integer
.
• Generate a valid inequality using Chv´atal-Gomory cut procedure for the following problem:
min y1 + y2 + y3
subject to:3y1 + 5y2 − y3 ≤ 12,
y1 + y3 ≤ 7,
y1 − y2 + 2y3 ≤ 9,
y1, y2, y3 ≤ 0 integer
.
5. CHALLENGE: Applications to genetics, DNA SEQUENCE ALIGNMENT:
In this problem we study the problem of DNA sequence alignment. The input is a pair of DNA
sequences (similar versions exist when trying to align multiple DNA sequences but we omit this
here):
1: TTGATCAATGG
2: ATCATACAAGGA
and the goal is to understand whether or not they have the same biological function. For this we find
the best way to align the sequences to each other. If after alignment, the sequences look “similar
enough”, we will conclude that they have the same biological function.
More precisely, the sequences are aligned by introducing gaps. For the above two sequences, a
possible way to introduce gaps is as follows (gaps are represented by hyphens):
1: TTGAT-CAATGG2: ATCATACAA-GGA
After introducing the gaps, the sequences are compared by counting the number of mismatches,
i.e., the number of locations where the nucleotides differ. For the above example, there are two
mismatches: one at location 0, and one at location 2 (using the usual array indexing convention in
programming!).
Let g denote the number of gaps and m denote the number of mismatches in a given alignment, the
overall cost c of the alignment is then defined by:
c := 2 · g + m
The above alignment has cost 2 · 3 + 2 = 8. Another possible alignment is:
1: TTGAT-CAATGG
2: ATCATACAAGGA
which has cost 2 · 1 + 4 = 6, which is minimal among all possible alignments of these two sequences.
Let us denote by s (resp. t) the first (resp. second) sequence. We define c(s, t) to be the cost of the
alignment of minimal cost among all possible alignments. Finally, we denote by n (resp. m) the
length of s (resp. t).
a. For a sequence s, s[i : j] will denote the substring of s ranging from index i inclusive to j
exclusive. Give a formula to compute c(s[0 : i], t[0 : j]) as a function of c(s[0 : i], t[0 : j − 1]),
c(s[0 : i − 1], t[0 : j]) and c(s[0 : i − 1], t[0 : j − 1]). Think recursively.
b. Using part a. design and describe an algorithm to compute c(s, t) [hint: think dynamically!
It is very useful to think of this problem as a type of matching problem].
c. Implement the algorithm you designed above. A test dataset is available at https://www.
math.ucdavis.edu/~deloera/TEACHING/MATH160/dna.txt. Each line of the datafile is the
list of the first 10,000 base pairs of the genome of the well-known Escherichia coli bacteria
(why is it famous? Do you know?). There are only two lines corresponding to two different
species of this bacteria.
d. Write code (using MATLAB and/or SCIP) which reads the datafile and outputs the cost of the
optimal alignment of the two DNA sequences. Do not forget to Submit the code you wrote.
Using C or Python to help yourself is allowed.
e. Two DNA sequences are considered to have the same biological function if the cost of the
optimal alignment, divided by the length of the sequence is smaller than 5%. Do the two DNA
sequences in the datafile have the same biological function?