Matroid Optimization; TDI theory: Subgradients, Strength of Lagrangian Dual Apr Homework submision should have each problem starting in a fresh page and the submission should be stapled. Assignment Problem, Dynamic Programming technique, Appln: This course covered some introductory topics in combinatorics, probability, statistics, linear algebra and optimization.

Started with the traveling salesman problem TSP , and gave a valid formulation using degree constraints and subtour inequalities. Polyhedron, Decomposition theorem for polyhedron, Polytopes Week 3 Jan Figures and math formulae may be drawn by hand in black ink. Stated the three basic problems of optimization, feasibility, and separation, and stated that all three are polytime equivalent. Some specific topics to be covered are: This class was taught through the Prison University Project , an organization whose mission is to provide excellent higher education to people at San Quentin State Prison; to support increased access to higher education for incarcerated people; and to stimulate public awareness about higher education access and criminal justice.

Setareh Taki Office hours: Defined characteristic cone, lineality space, extreme points.

Please make sure you have the latest version. Homework Assignment homeework here is due on monday 28th Sept. An introduction to mathematical arguments and the writing of proofs through topics in elementary set theory, graph theory and number theory.

Homework Assignment 4 here is due on monday 5th October one week late: No credit for the homework, midterm or final. This course covered some introductory topics in combinatorics, probability, statistics, linear algebra and optimization.

# Integer Programming

Vanderbei’s book chapter Linear Programming by R. And the hint for Q6 a has been homeowrk, as mentioned in a previous email. Cutting-plane algorithms Branch and bound Duality in integer optimization and its algorithmic consequences Complexity of integer programming Algorithms for special classes of problems Separation vs. Stated the three basic problems of optimization, feasibility, and separation, and stated that all three are polytime equivalent.

Considering the minimum s – t cut, minimum Steiner tree LP relaxations, and the Maxcut semidefinite-programming relaxation as examples. The first two books cover many of the topics that we will cover in class, however the treatment in these books is often at a more advanced level. Future – You can find me at the following seminars, conferences and workshops: For more information about the Ellipsoid method and its applications to combinatorial optimization, you may want to consult the following book, which is the definitive source of information on this topic: Chvatal Rank and Finiteness Apr If you would really like some topic that is not here to be covered, come chvagal talk to me.

## Integer Programming

Hilbert bases Week 7 Mar 3: A couple of typos in assignment 2: An extra ASK office hour right before the quiz was also added where I went over the problems and showed my thought process. A clarification about Q3 b in assignment 2: Once again, if you have any doubts in this regard, ask the instructor.

Described the generic cutting plane algorithm. Described and analyzed the Ellipsoid method assuming the underlying set K is closed, convex, contained in a bounding ball, and contains a ball.

Some specific topics to be covered are: Shortest Path Problem Mar Showed how a Gomory cut and Gomory mixed-integer cut can be generated from the final simplex tableaux.

Knowledge of linear programming at the level of CO or higher. The students earn credits for chvaatl course through Adams State University.

Due on Thu, Feb 19 Homework 2. Finished the above proof. Mathematical correctness and clarity of exposition will be factors in grading.

Introduced network flow problems, defining the min-cost flow problem.