UiB :: INF271 (2021/1)

• Official INF271 page

• Course plan

• First session - sllides

• Final session - slides

• Oral exam preparation guidelines

• Assignment 1

• Assignment 2

• Assignment 3

• Assignment 4

• Assignment 5

• Assignment 6

• Assignment 7

• Assignment 8

• Ch.2 Complement - cones and extreme rays

• Ch.3 Note - A TU iff [A I] TU

• Ch3 conclusion - independence system is a matroid IFF rank function is submodular

• Ch4 note - Primal-dual idea for weighted assignment problem

• Ch6 note - SAT to 3-SAT example

• Ch9 complement - clique and directed cutset inequalities, exact vs heuristic separation

• Ch9 complement - affine independence

N.B. This page is going to be updated several times throughout the semester!

Links

[added on 10.01] Summer school CO@Work 2020

http://co-at-work.zib.de/

Many excellent lectures by distinguished researchers, developers and managers about concrete applications of combinatorial optimization. Note that lectures on the first week give an introduction to the foundations and motivation of the field, while those in the second week are all about applications and real-life.

[added on 10.01] Discrete Optimization on Coursera, by Pascal Van Hentenryck and Carleton Coffrin

https://www.coursera.org/learn/discrete-optimization

The syllabus of this course is broader than INF271, so it does not cover several topics and does not have the expected depth overall. Nevertheless, I find it very instructive, and it can help a lot in building intuition about the optimization as a whole.

The module on linear programming (LP) is a fine option to catch up on this prerequisite for our course within two and a half hours of intuitive, lively lectures.

[added on 10.01] EURO working group on Practice of OR

https://www.euro-online.org/websites/or-in-practice/

This community is concerned with all practical matters around the use of operations research in the real world. The webpage contains links (including video recordings!) to many talks given in the different working group meetings. For instance, the last edition focus was on Challenges in the deployment of OR projects.

This is a working group of EURO (Association of European Operational Research Societies), the regional grouping within the International Federation of Operational Research Societies (IFORS), whose aim is to promote Operational Research throughout Europe.

Miscellaneous information

[added on 18.01] Bertsimas' analysis on the speedup in MIP solvers over the last 25 years

http://www.epoc.org.nz/presentations/ML_OPT.pdf (check only pages 4 to 6)

"Total speedup: 2.2 Trillion times! A mixed-integer optimization problem that would have taken 71,000 years to solve 25 years ago can now be solved in a modern computer in less than one second."

This is only a piece of information in the introduction of the talk "Machine Learning under a Modern Optimization Lens", by Dimitris Bertsimas (MIT), on February 2020. Bertsimas is a distinguished researcher and lecturer in optimization, machine learning, applied probability, and more. This talk (and the recent book it refers to) makes a case for integer programming as the essential tool for interpretable AI and next-generation ML.

Suggested track on Matoušek and Gärtner for background on LP

[added on 11.01] As it was asked for in the opening session, here is a short selection of topics on linear programming that could serve very well the necessary background for our course. This book is eminently readable, I highly recommend it! I believe that you do benefit from each moment working on it, and that it is possible to have a crash course following the sections below. Of course, this won't be easy, and should not be done in just one or two sittings; plan for some 10 hours spread over a week. Doing this will be quite a head start, and an achievement to be proud of.

Chapter 1

All of it

Chapter 4

Section 4.1

Section 4.2, up to the box before "Proof of Theorem 4.2.3", in page 47. Do not skip the first two proofs on page 45 to make sure that you are able to understand the reasoning, and that you are comfortable with the small subset of linear algebra. (otherwise, check the appendix!).

Section 4.3

Section 4.4

Chapter 6

Section 6.1

Section 6.2

Section 6.4

Section 6.7 is also recommended and instructive, but not really necessary.

Appendix: Linear Algebra

Just skim the appendix pages to make sure that you remember the fundamental concepts. If you are unsure of something, read it more carefully (but it shouldn't be necessary to study elsewhere).

It certainly helps to be exposed to more examples. Moreover, the above sections do not include many possibilities on model building/formulations. Studying Chapter 2 is a good choice for all this, but definitely not necessary to follow our course this semester.

Note that we are skipping algorithms altogether. Although we solve lots of linear programs in combinatorial optimization, most of the time it's enough to pretend we have an oracle, to which we can give an LP problem and expect a correct answer in polynomial time. If you do have the time and want to learn about the simplex method, for a start, you could read from page 57 until Lemma 5.51 on page 66, skipping its proof, and skim Section 5.9 for culture.

Suggestions for an introduction to graph theory

[added on 13.02] Following a request in our sessions, I suggest below a few options to build up a stronger foundation on graph theory.

I mentioned that, strictly speaking, it suffices to our purposes that you simply make sure you understand the definitions and results that we use in class and in exercises. For this, reading through the first section in the corresponding page at Wikipedia should suffice. The references below are for those who feel like doing some structured reading (and are likely to benefit from it for a long time...).

• - "I simply want a few pages to read and be properly introduced to fundamental concepts."
  - Read the first few sections in Chapters 4 and 5 of the wonderful book "Invitation to discrete mathematics" by Matoušek and Nešetřil.
  

• - "I'm decided to spend a few weeks, learning more about graphs in my spare time (e.g. because it is truly fun / because I have a project requiring it)."
  - Well, first you read some sections on the suggestion above, because it is a masterpiece and makes everything else more exciting. Then continue to one (or both) of the following.
  a) Study the first chapter (which actually includes some chapters worth of material) in the excellent and lively "Combinatorics and graph theory" by Harris, Hirst, and Mossinghoff.
  b) If you would like to see a bit more of graph algorithms and the computational questions around them, you definitely should look at Chapters 22 to 26 in the classic "Introduction to algorithms" by Cormen, Rivest, Leiserson, and Stein.
  

• - "The semester is over and I'm reading this because I saved the reference for later. What are good choices of advanced textbooks in graph theory?"
  - Any of Diestel, or Bondy & Murty (both the short 1977 version and the much extended 2008 version), or Bollobas will give you material for a degree or two... Feel free also to pair up and invite me for an eventual reading group - we could discuss the material and solutions to problems in any selection of chapters.

All of the books mentioned above are available electronically at UiB. You have access to them following the links when connected to the campus network or when using our VPN.

The job of an optimizer (any applied mathematician and data analysts, actually) includes dealing with different solvers, programming languages, and prototyping tools that a client/institution uses; not to mention that we try new options for the possibilities they offer. Below are instructions for setting up the Gurobi solver, a top-quality and established option competing for the first place in a decades-long competition of both commercial and free tools.

Check https://www.gurobi.com/resource/starting-with-gurobi/ for some introductory information. In a nutshell, what you need to do is:

1. Visit https://pages.gurobi.com/registration to create an academic account, and download Gurobi Optimizer in https://www.gurobi.com/downloads/ .
   

2. Install the solver.
   On GNU/Linux, we simply unpack the file (e.g. under /opt) and extend the usual environment variables PATH and LD_LIBRARY_PATH in the end of the files .bashrc and .profile in our home to include the path to Gurobi folders; check against the installation guide: https://www.gurobi.com/documentation/9.1/quickstart_linux/software_installation_guid.html#section:Installation
   For Mac OS and Windows there are usual installation executables.
   

3. Request a free academic license on https://www.gurobi.com/downloads/end-user-license-agreement-academic/ and run the grbgetkey tool to validate it. N.B. the specific command is indicated at the bottom of the License Detail page you get in the end of this step! Just copy and paste it on the terminal (after restarting your session/login so that the command is recognized). (:
   Important: this validation only works if you are connected to UiB's network (or using its VPN).

Done!

The best way to make sure you've had success is to run one of the example applications that come with Gurobi - check Examples under your installation directory! Also see some detailed example in the documentation!

https://www.gurobi.com/documentation/9.1/quickstart_linux/cpp_interface.html#section:C++

--

Boring tweaks for working in Windows:

Linking with the Gurobi libraries by hand when using an arbitrary C++ compiler, for instance, is a nightmare. :( The recommended procedure is to download and use Visual Studio (not Visual Studio Code). Then

1. Open the solution file *.sln that comes with Gurobi (in the subdirectory Examples > Build);

2. Duplicate and edit any of the example projects; add any file you want here;

3. One still needs to prevent the terminal from closing after execution (check the option in settings, and/or run in debug mode).

"Done!"