Combinatorial Optimization 2018

Combinatorial Optimization 2018

Back to the main page


The official homepage of the lecture: Course



The lectures:
We are going to have a lecture (after our next practice lecture) at 20th of April from 12:15 in the room IB134 (it will be instead of the 30th of April). In this lecture we will practice to the exam, and I will upload the detailed material here.
The lectures are on every Monday in IB138 at 08:30-10:00 (there will be a spring break at April from 2nd to 6th), and on every second fridays in E402 at 10:15-11:45 (2018.02.16, 03.02,03.10, 04.20, 05.04,05.18; Note that 10th of March is Saturday)

FIRST lecture: What is a Polynomial. The assymptotical behaviour of polynomial and other functions. What is an Algorithm. The diference between continuous and dischrete optimization. Binary representation of a number (the length is log_2 n).
Calculate upper bounds on the Running time of an algorithm (as a function of the length of the input). The running time of addition, multiplication and exponentiation.
Graph theory, vertices, nodes, paths, circuits, trees, Spanning trees, Connectivity.


SECOND lecture: What is an Indirect proof. (It is correct since A->B <=> Not(A) Or B )
Proove that Connectivity is equivalent to the existence of a spanning tree.
Turn optimization problems to Decision problems.
P is the class of decision problems which can be solved with a polynomial time algorithm.
NP is the class of decision problems for which if the answer is TRUE, then there exists a witness. A witness is information whith which the solution of the problem is possible in polynomial time.
The problem Even is in NP.
Bipartite graphs, Maximum matching problem. It is in NP.

THIRD lecture (practice): (finishing the proof of Maximum matching is in NP).
The length of the representation of a graph (with Adjacency matrix). Directed graphs.
The graph k-Coloring problem. 3-coloring is in NP.
The Partition problem. The partition problem is in NP
EXAMPLE: For a detailed solution of an example see the first problem here, and the corresponding first solution here
PROPOSED HOMEWORKS: 1.a, 1.b, 1.c., 1.e, 1.f, 1.g (1.d is hard, but you can try that also)

FOURTH lecture: The difference between minimum and minimal.
P is a subset of NP. The one million dollar question.
Karp's reduction or polynomial reduction. It is transitive.
Reduction from the composite problem to the smallest divisor problem. If X is in P then there exists a reduction from X to Y for every Y decision problem.
If Y is in P (/NP) and there exists a reduction from X to Y, then X is also in P (/NP).
NP completeness. Examples: 3-coloring, Partition, k-clique.
How to prove that something is NP complete, using an other NP complete problem. k-independent is NP complete (by a reduction from the k-clique problem to the k-independent problem).
If there would be an NP complete problem X which has a polynomial solution, then P=NP. If there would exist a problem in NP which does not have a polynomial solution then P is not equal to NP.

FIFTH Lecture: Hamiltonian problems. Reduction from the u,v-Hamiltonian path to the Hamiltonian cycle problem (hint: one new node and two edges).
BFS algorithm. Deciding connectivity. Find shortest paths. Deciding acyclicity.


SIXTH lecture (practice): Reduction from the general Hamiltonian path to the Hamiltonian cycle problem (hint: 3 new nodes and 2n+2 edges).
Reduction from the Hamiltonian cycle to the Hamiltonian path problem (hint: node duplication + 2 new nodes and 2 edges).
Running BFS on some of the following Graphs. Using BFS to count the number of components
PROPOSED HOMEWORKS: 2. and 3.


SEVENTH Lecture: Using BFS to decide binarity. Minimum weight spanning tree problem. Kruskal's algorithm. Network flow problem. Ford-Fulkerson algorithm.


EIGHTH Lecture:Ford-Fulkerson examples 1 2 , Kruskal examples 1 2.
PROPOSED HOMEWORKS: 4. and 5.


NINTH Lecture: Dynamic programming for maximum continuous sum problem, for counting the number of routes in grids and for knapsack problem.
PROPOSED HOMEWORK: 6.



The topics until here are parts of the first exam. Every topic under this line will be in the second exam.



TENTH Lecture: Dijkstra: dynamic programming for shortest path finding from one node to every other (weighted graph, directed or undirected case, no negative edge).
PROPOSED HOMEWORK: 7.



ELEVENTH Lecture: Widest path problem: Undirected case = Kruskal; Directed case = Dijkstra. Widest shortest path problem, modified Dijkstra methods. Example
PROPOSED HOMEWORK: 8. 9.



TWELFTH Lecture: Linear Programming (LP) problem. Graphic solutions. Duality theorem.
PROPOSED HOMEWORK: 13. 14.



THIRTEENTH Lecture (practice): Integer Programming (IP) problem. Linear Programming and Integer Programming formulation of different problems: knapsack problem, network flow problem, maximum assignment problem.
PROPOSED HOMEWORK: 10. 11. 12.



FOURTEENTH Lecture (additional practice): Here can be found the whole lecture material: Examples with solutions.



FIFTEENTH Lecture: Maximum assignment problem and Minimum potential function. Branch and bound method for solving Integer Programming (IP) problems and knapsack problems.
PROPOSED HOMEWORK: 15. 16.




SIXTEENTH Lecture (practice): Practice the topics of the previous lecture.



SEVENTEENTH Lecture: Practice for the second exam.



EIGHTEENTH Lecture: Solutions of the second exam. Practice for the retake. Totally unimodular matrices, duality of integer programming problems.



NINETEENTH Lecture (practice): Retake of the exams.




The exams:
Results of the exams.
Examples of the first exam , Solutions of the first exam (except example 5) , Solution of the 5th example of the first exam ,
Examples of the second exam.


03.22. 18:00-20:00 (in Q-I: building Q, first floor)
05.08. 18:00-20:00 (in Q-I: building Q, first floor)
05.18. 10:00-12:00 (retake)
05.28 10:00-12:00 (reretake: you have to register on Neptun)

The grades will be calculated from the overall percentage of the written exams. (0-47: 1; 48-65: 2; 66-83: 3; 84-101: 4; 102-120: 5).
There are two midterm tests during the semester. The condition of completing the subject is a result of at least 40% on all midterm tests.


If you have any questions or comments please write me an email (cscsgy at gmail dot com).

Topic of the first exam:
Everything from the FIRST to the NINTH lecture.

Topic of the second exam:
Everything from the TENTH to the SEVENTEENTH lecture.

Main topics what we learn about: Algorithms, Polynomials, Graph theory, Combinatorial optimization, Running time, Polynomial reduction, Bipartite graphs, Spanning trees,
Greedy algorithm, Kruskal's algorithm, BFS, Flows, Ford–Fulkerson algorithm, Assignment problem, Hungarian algorithm,
Dijstra's algorithm, Dynamic programming, DP solution for Knapsack problem,

Classes of decision problems: P, NP, NP-complete,

Problems what we learn: Prime, Composite, Partition, Subset sum, Knapsack problem,
Graph theoretical problems: Connectivity, Perfect matching, Path existence, Shortest path, k-Clique, k-Coloring, Hamiltonian cycle,
Widest path, Minimum spanning tree, Maximum flow,

Useful examples: Dijkstra: video, picture
Knapsack: video, slides



Homeworks to practice: (If you send me a solution in email [or give it to me in a paper on a lecture], then I correct the mistakes and send back how many points would that solution worth in the exam)
1.
a. Prove that the Hamiltonian path problem (Input: G graph, Output: True if there exists a Hamiltonian path in the graph) is in NP.
b. Prove that the maximum weight matching problem (Input: G graph, a weight function w(e) on the edges, and number k, Output: True if there exists a matching with weight at least k) is in NP.
c. Prove that the k-Coloring problem (Input: G graph and number k, Output: True if there exists a good coloring with at most k colors) is in NP.
d.* Prove that the Connectivity problem (Input: G graph, Output: True if G is connected) is in NP.
e. Prove that the Composite (Input: A number n, Output: True if n is not a prime) is in NP.
f. Prove that the Path existence problem (Input: G graph and two of its nodes u and v, Output: True if there exists a path between u and v) is in NP.
g. Prove that the k-Clique problem (Input: G graph, Output: True if there exists a clique in G on k vertices) is in NP.

2.
a. Give a polynomial reduction from the Hamiltonian cycle problem to the longest cycle problem (Input: G graph and number k, Output: True if there exists a cycle with at least k edges).
b. Give a polynomial reduction from the Hamiltonian path problem to the longest path problem (Input: G graph and number k, Output: True if there exists a path with at least k edges).
c. Give a polynomial reduction from the 3-Coloring problem to the k-Coloring problem.

3. Run the BFS algorithm in the given graphs (to decide connectivity, decide binarity, find shortest paths, decide acyclicity):
a,b. from 0, and from 6: G_1
c,d. from 10, and from 6: G_2
e,f. from M, and from I: G_3

4. Run the Kruskal algorithm in the given graphs:, a. G_1,
b. G_2,
c. G_3

5. Run the Ford-Fulkerson algorithm in the given graphs:
a. from a to f: G_1
b. from s to t: G_2
c. from 1 to 8: G_3
d. from s to t: G_4

6. Solve the following knapsack problems using dynamic programming (Limit: weight-value pairs):
a) 10: 1-1,2-8,3-10,4-10,5-19,6-25 Solution
b) 6: 3-25,2-20,1-15,4-40,5-50 Solution

Second part of the semester

7. Run the Dijkstra method to find the shortest paths (from one node to all the others) in the following graphs:
a) From A and from G Solution
b) From k and from e Solution

8. Run the modified Dijkstra method to find the widest paths (from one node to all the others) in the following graphs:
a) From 3 and from 4 Solution
b) From 3 and from 7 Solution

9. Run the modified Dijkstra method to find the widest shortest paths (widest among the shortests from one node to all the others) in the following graphs:
a) From 4 (the first numbers are the distances, the seconds are the weights) Solution
b) From C and from G (here the numbers are the weights and the distances are equal to one in every edge) Solution

10. Formalize the flow problem of these networks as linear programming problems. a) network1 (from 1 to 3) b) network2 (from + to -) Solutions

11. Formalize the knapsack problems of the 6th homework as integer programming problems. Solutions

12. Formalize the maximum weight matching problems on these graphs as integer programming problems. a) graph1 b) graph2 Solutions

13. Draw the set of solutions of these LP-s in coordinate systems. a) LP1 b) LP2 Solutions

14. Give the dual of these LP-s. a) LP1 b) LP2 c) LP3 Solutions

15. Find a maximum assignment and a minimum potential function on the following two bipartite graphs. Graphs Solutions

16. Solve the knapsack problems of 6 with the branch and bound method. Solution for a) Solution for b)


Collection of other useful materials: Alexander Schrijver's lecture
MIT course (usable for us: 'Matching Algorithms','The Matching Polytope: Bipartite Graphs','Flow Duality and Algorithms','Minimum Cuts ','Linear Programs','NP-completeness','Approximation Algorithms')
Princeton lecture of Robert Sedgewick and Kevin Wayne (usable for us: 'Undirected Graphs','Directed Graphs','Minimum Spanning Trees','Shortest Paths','Linear Programming','Reductions')