Labs

The goal of the labs is to exercise the topics presented on lectures.

On some labs you will receive homework assignment, which are implementation of an algorithm or a method solving some interesting combinatorial optimization problem. In all cases, the solutions to homework assignments are submitted to Brute where they are automatically checked and evaluated. Late upload will be penalized by -1 point for each week after deadline. Completing all homeworks successfully (i.e., the output is classified as correct according to Brute) is a mandatory requirement for the assessment. Moreover, we encourage you to solve the homeworks since in the practical test you will use algorithms implemented for the homeworks.

Plan of the Labs

Week No.	Title	Notes	Materials
1	Introduction, Gurobi installation, LP basics		Grading and rules Gurobi installation guide Gurobi code example (code) LP basics (Wolfram notebook) Introduction (colab notebook), Introduction (solved) Transportation problem (colab notebook) Simplex worst case notes (optional) Wolfram simplex (optional) LP algorithms (optional)
2	Semestral work, ILP basics		Cocontest assignment: (pdf), Public instances (zip), Public threshold instances (zip) ILP basics (colab), ILP basics (colab solved) Gurobi official interactive examples Mathematical programming book with examples
3	ILP 1	HW1	HW1 assignment (pdf), Public instances (zip), Call center (colab TODO), Call Center (colab solved) The Catering Problem (colab TODO), Catering (colab solved), Video, Solution Computable vs uncomputable functions (optional)
4	ILP 2		Dlužníček (Colab TODO), Video, Dlužníček (colab solved), Solution Peaking Power Plants (colab TODO), Video, Peaking Power Plants (colab solved), Solution (video) Tiles (colab TODO), Tiles (colab solved) Blog about perils of big-M
5	ILP 3	HW2	HW2 assignment (pdf) Public instances, Video Lazy Constraints: Handout (pdf), Video, Colab Notebook, Circle approximation (zip), Wolfram notebook (optional)
6	Unexpected ILP applications		Game of Fivers: Game, Video, Handout (pdf), Colab (TODO), Colab (solution) Rubik's Cube: Video, Handout (pdf),Colab Verification of DNNs: Video, Handout (pdf), Colab
7	Metaheuristics + consultations		Metaheuristics: Colab, Solved Circle packing: ILP (colab), GPU (colab) Cocontest: Public threshold instances (zip)
8	SPT	CC-O	Handout (pdf), Function approximation (colab) czech_republic.txt, Content-aware image resizing, Online demo
9	Max flow	HW3	Max-Flow: Handout (pdf), Video, Lazy separation notes (optional) HW3: HW3 assignment (pdf), Initial feasible flow for FF (video), Public instances
10	Min-cost flow		Min-cost flow: Handout (pdf), Object tracking (pdf), Object tracking (video) Min-cost flow: Image reconstruction (colab) Multicommodity flows: Pipe puzzle (colab)
11	cancelled
12	DP/approx	Thursday → Tuesday	DP: Handout (pdf), Optimal coin system design (colab) Approximation: LPT rule approximation factor (colab)
13	Scheduling	HW4	HW4 Assignment (+ Handout), Public Instances, Video The Scheduling ZOO
14	Scheduling, CP masterclass		CP: Scheduling with CP (colab) , CP overview (slides) Cocontest: results (pdf) Other materials: Nonogram (colab TODO), Game of Life sythetizator (colab), Game of Life (video), Game of Life (game) Computational proof of Euler's impossible puzzle (colab)

Classroom computers

OS: Debian Linux 64b, select Ubuntu during booting

Login: uses credentials from Department of Computers. If you haven't use them before, setup them at https://www.felk.cvut.cz/labpass/

Development environments: CLion (C++), IntelliJ (Java), PyCharm (Python), GVim, Netbeans are installed. CLion, IntelliJ and PyCharm are installed in /opt and their license have to be activated via creating JetBrains account with faculty email.

VPN: Gurobi (Academic) licence can be obtained for free, but only from the university network; to access it remotely, you can use VPN - for more info see FEL VPN (CZ)/ FEE VPN (EN).

Table of Contents

Labs

Plan of the Labs

Classroom computers