Due on Thu, Mar 9 Exam 1. Revision of basic concepts. Posted lecture 1 slides and Handout 1 passwords given out in class. Defined the notion of a polytime reduction. There is a typo in Q1 a in assignment 4. Due on Thu, Apr 16 Homework 4. Here are the Solutions.
Tentative list of topics Some subset of the following topics will be covered. The first one asked students to find out about an application of multivariable calculus relevant for their future career or their interests. Mathematical correctness and clarity of exposition will be factors in grading. References Will post interesting links and papers here. The choice of topics may vary depending on available time and student feedback. Integer programs are optimization models that provide a great deal of flexibility and modeling power, but are are often notoriously hard to solve and are much less understood compared to linear programs in terms of solution methods. Due on Tue, Apr 25 Exam 2.
Your grade will be determined by the total score normalized to You are encouraged to discuss the course material with your colleagues, but no collaboration or other solution sources are allowed on the problems assigned for homework or exams. This, along with the chvata to encode logical statements using binary variables, gives rise to the tremendous modeling power of IPs. This is generally a powerful tool in many research areas.
Started with solution methods for integer programming. Homeworks, Exams Midterm and Final chvstal be in-class written exams. Electronic submission through email will be accepted provided it is in pdf format.
Theory and Applications by G. Optimal allocation of resources, control design, verification, regression, relaxations of hard combinatorial problems to LP.
Transshipment problem and Feasible Spanning Tree Solutions. Collaboration and Cheating Policy You are allowed to collaborate on assignments unless otherwise indicatedbut instances of collaboration should be within reason. Mentioned the issue of precision that arises in the Ellipsoid method. Proved the above lemma about polyhedra.
Polyhedron, Decomposition theorem for polyhedron, Polytopes Week 3 Jan NP completeness, examples, branch-and-bound method. Midterm Week 10 Mar 24, Mar Course Outline Integer programs are optimization models that provide a great deal of flexibility and modeling power, but are are often notoriously hard to solve and are much less understood compared to linear programs in terms of solution methods.
Grading The course will feature weekly homework assignments, and two midterm quizes. Homework submision should have each problem starting in a fresh page and the submission should be stapled. No credit for the homework, midterm or final. Started with polyhedral theory.
Proved corollaries of the above lemma showing that a cchvatal has an essentially unique irredundant description. Norm minimization problems L1,L2, Linftyunconstrained least squares, solving linear systems with noise.
CSCI 5654: Linear Programming
Defined the notion of a polytime reduction. Math Discrete Mathematics: The solutions are in a password-protected area; the username and password will be announced in class on Monday, February 2, Started hpmework topic of separation vs. Assignment 1 is available. Optimizing over polymatroid, Efficiency of Algorithms: Optimality, Relaxations, Bounds Week 2 Jan See univ integrity policy here.
You may pick up the exam any time between Monday, April 6, 12 noon and Wednesday, April 8, 12 noonand you have one week to work on it. Started with computational complexity. Derived Gomory mixed-integer cuts as an example. Assignment 2 is available updated Feb 9.