CAAM 471/571
INTRODUCTION TO LINEAR AND INTEGER PROGRAMMING

Spring 2014 $\cdot$ Rice University

Lectures:	Tues/Thurs: 1:00-2:15PM, Room DCH 1070
Web Site:	http://www.caam.rice.edu/~yzhang/caam471
Instructor:	Yin Zhang (yzhang_at_rice_dot_edu), Duncan Hall 3090, (713) 348-5744
	Office Hours: Mon. 4-6pm OR Wed. 1:30-3:30pm (the day before homework is due)
Description:	Linear and integer programming involve formulating and solving fundamental optimization models widely used in practice. This course introduces the basic theory, algorithms, and software of linear and integer programming. Topics studied in the linear programming part include polyhedron concepts, simplex methods, duality, sensitivity analysis and decomposition techniques. Building on linear programming, the second part of this course introduces modeling with integer variables and solution methodologies in integer programming including branch-and-bound and cutting-plane techniques. This course will provide a basis for further studies in convex and combinatorial optimization.
Prerequisites:	CAAM 335 and CAAM 378 (recommended).
	You should be familiar with multivariable calculus and basic matrix operations (including solving linear systems of equations), and be able to write MATLAB programs.
Textbooks:	Required: Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis.
	Recommended: Theory of Linear and Integer Programming by S. Schrijver.
Assignments:	- Ten Problem sets will be assigned, roughly weekly, and due a week later at 5pm (unless otherwise specified). These assignments will differentiate between CAAM 571 and 471.
	- Three problem sets are pledged that must be completed individually and independently ($\approx$ take-home exams). Further instructions will be given with the assignments.
	- On unpledged assignments, you may collaborate on ideas and methodologies, but your write-ups must done independently. Copying (even with alternations) is not allowed.
	-You may not consult solutions from previous sections of this class.
Late Policy:	- CAAM 471 students may have 2 free late submissions on 2 unplugged problem sets up to one class period. Subsequent late submissions will be subject to 20% penalty each.
	- No late submissions will be accepted after one class period without a valid written excuse.
	- For CAAM 571 and for CAAM 471 on plugged problem sets, no late submissions will be accepted (unless in exceptional cases permitted by the instructor).
Grading:	- 60% for pledged assignments and 40% for unpledged ones.
	- Class participation will be considered when assigning borderline grades in CAAM 471.
	- Class participation will be heavily weighted in CAAM 571 when assigning grades.
Programming:	Many problem sets will require MATLAB and/or AMPL programming. Your solutions should adhere to good programming standards, and must not be copied from other students. Consult the course web site for pointers to MATLAB and AMPL tutorials.

Any student with a disability requiring accommodation in this course is encouraged to contact the instructor during the first week of class, and also to contact Disability Support Services in the Ley Student Center.