Textbooks

For the first part of the course on linear optimization you may refer to the book `Introduction to Linear Optimization', by Bertsimas and Tsitsiklis, Athena Scientific 1997, ISBN 1-886529-19-1. (A copy of the first five chapter is available on the web page of Prof. Stougie in Amsterdam. You may find good recommendations for additional material on the same web page.) `Network flows' are covered by the homonymous extensive book by Ahuja, Magnanti, and Orlin—it should not be hard to download a free (legal) copy of this book. Another useful resource ("Introduction to Linear Optimization" by A. Nemirovski) can be found here.

Throughout the course I will be heavily relying on examples, lecture notes, assigments, and exercises which can be found on the wonderful MIT OpenCourseWare, for instance here and here. I guess you may behave accordingly.

Additional useful material can be found on the teaching web page of prof. F. Malucelli (Thank you Federico for making your work available on the internet!).

Requirements

The minimum requirement to attend this course is to be familiar with basic concepts of linear algebra and calculus.

Exams

Examination consists solely of a written exam for those who take 6 credits. The students who take 9 credits will be also required to work in a project (details will be discussed soon). There are 6 exam dates per year (still to be fixed):

Winter

• I Feb.

• II Feb.

Summer

• I Jul.

• II Jul.

Fall

• I Sept.

• II Sept.

Links

• GUROBI - Optimization Software

• IBM ILOG CPLEX - Optimization Software

• OR: The science of better

• MIT OpenCourseWare a large amount of resources for students and teachers as well (and not only in OR)

• Michael Trick's Home Page - news, curiosities and folklore in OR.

• INFORMS - web page of the U.S. "International Federation of Operations Research and Management Science"

• Punk Rock Operations Research (sic!) additional Operations Research-folklore

Assigned Projects

Team 1 (Patrycja and Przemek): Uncapacitated Facility Location [UFL Instances here]

The problem is the standard UFL where a set of n (potential) facilities and m clients are given. For each pair (facility i, client j) an allocation/connection cost c_ij are known together with a setup/opening cost for each facility which is opened. The decision is twofold: (i) location: which facilities are to be opened and (ii) allocation: for each client, the opened facility to be connected to. An optimal location-allocation decision is such that the overall cost, associated to opened facilities and connections, is minimum.

Team 2 (Miko and Valerio): Multidimensional-knapsack * [MKP Instances here]

It is a generalization of the standard binary knapsack problem: We have a set of n items, with each item j there are an associated profit p_j and m attributes or "dimensions" (e.g., weight, volume, etc) w^i_j, i = 1,..., m. The objective is to pick some of the items, with maximal total profit, while obeying that, for each dimension, the maximum total size of the chosen items must not exceed a given upper bound W^i. (* Note there are several different generalizations of KP in the literature.)

We assume that all the given data are integers, and they are almost always assumed to be positive.

For both projects, the mandatory tasks are the following:

1. Search for some papers about the problem. You may try with google or scholar. google or whatever. Search for alternative ILP formulations (w.r.t. those you already know) and simple heuristic algorithms for your problem.

2. Choose at least two different IL Programs for your problem and write the corresponding AMPL models.

3. Solve: Consider a time limit between 1800 and 3600 seconds (no more than that) per instance.

   • Can you solve all the provided instances within the time limit?

   • If yes, ask for "harder" instances.

   • If not, from the set of instances provided, answer the foll. questions:

     • How many instances are solved to optimality? How long does it take to the solver to solve those instances?

     • For those instances that are not solved to optimality within the time limit, can you give an estimate of the quality of the solution? (The quality is basically measured by comparing the values of the best solution found and an optimal solution or, more probably, its estimate.)

     • What are the characteristics of the not-solved instances? Are they just larger (in terms of number of clients+facilities or items) instances?

The following point is not mandatory but, of course, it is appreciated.

4. Design a "very simple" algorithm and compare its performance with that of the AMPL-Solver suite, in terms of quality of the solution and computation time.

Homeworks

• 27.10.2016: Write down a linear mathematical program for the problem described here.

• 24.11.2016: Consider the UFL instance obtained from cap94.txt (you may find the instances here) by removing capacities and demand data. Implement/execute greedy algorithm for that instance.

• 15.12.2016: 1. Solve the "blackboard instance" of Min Cost Flow. 2. Show how any instance of Bipartite Max Cardinality Matching can be solved via a suitable instance of Min Cost Flow.

Calendar

Mon 30.1 Project assignment. End of course.

Thu 26.1 Project assignment. End of course. Canceled.

Tue 24.1 Intermediate test.

Thu 19.1 Total unimodularity (notes by prof. Uetz). Multi-commodity flows (reading: ...).

Tue 17.1 Shortest path problem as a min cost flow problems (reading: notes by prof. Goemans and notes by prof. Stroemberg)

Thu 12.1 Correction of the intermediate test.

Tue 10.1 Intermediate Test

23.12.16-8.1.17 Holiday

Thu 22.12 Ford and Fulkerson algorithm for Max Flow.

Tue 20.12 Max cardinality matching as a min cost flow problem. Max Flow Min Cut: LP formulations and duality relations.

Thu 15.12 (Directed) Networks: basic definition (resumed). Flows. Minimum cost flow problems (reading: notes by prof. Goemans and notes by prof. Stroemberg). Do homework 15.12.2016.

Tue 13.12 Duality in linear programming: optimality conditions, complementary slackness. Supply-Demand Flow problem: LP formulation and interpretation of its dual.

Thu 8.12 Holiday

Tue 6.12 On the AMPL software (notes and lecture by prof. Veronica Piccialli).

Thu 1.12 Erlenkotter's dual ascent method

(reading

http://www.wiwi.uni-sb.de/lst/ufo/Download/Dateien/Vorlesungen/%20WS%200809%20-%20Facility%20Location%20and%20Strategic%20SCM/Vorlesung%206.pdf

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/lecture-notes/lec17.pdf).

Tue 29.11 Strong duality for linear programming (reading: Bertsimas Sec. 4.2). The dual of the linear relaxation of UFL. Erlenkotter's dual ascent method

(reading https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/lecture-notes/lec17.pdf).

Thu 24.11 Greedy algorithm for UFL (reading http://www.wiwi.uni-sb.de/lst/ufo/Download/Dateien/Vorlesungen/%20WS%200809%20-%20Facility%20Location%20and%20Strategic%20SCM/Vorlesung%206.pdf). Do homework 24.11.2016.

Tue 22.11 Dual of a linear program in a generic form (reading: Bertsimas Sec. 4.2). Min-max relations in graphs: Max-cardinality matching and min-cardinality vertex cover. ILP formulations, their linear relaxations as a primal-dual pair (reading TBD).

Thu 17.11 Relaxation of a mathematical program. Linear relaxation of an ILP. Lagrangean relaxation for a LP and dual problem.

Tue 15.11 On degeneracy in LP (reading: Bertsimas Sec. 3.4). Capacitated and uncapacitated facility integer linear program examples on the spreadsheet optimization tool.

Thu 10.11 On degeneracy in LP: Bland's rule (reading: Bertsimas Sec. 3.4). Location problems. Uncapacitated facility location: ILP formulation.

Tue 8.11 Integer linear program examples on the spreadsheet optimization tool. Disjunctive constraints (big M method).

Thu 3.11 Homework revision, integer linear program examples: piecewise linear and fixed charge objective functions.

Tue 1.11 Holiday

Thu 27.10 The simplex method phase I (reading: Bertsimas Sec. 3.3). Spreadsheet optimization tools: example. Do homework 27.10.2016.

Tue 25.10 The simplex method phase II (reading: Bertsimas Sec. 3.2)

Thu 20.10 The simplex method (reading: Bertsimas Sec. 3.1)

Tue 11.10, Thu 13.10 and Tue 18.10 Geometry of Linear Programming (reading: Bertsimas Sec.s 1.5, 2.1, 2.2, 2.3, 2.5, 2.6)

Fri 7.10 ILP formulations of some problems on graphs

Thu 6.10 Basic definitions: graphs, networks.

Tue 4.10 Administrivia. Introduction to linear optimization. Examples. `Components' of a mathematical program.