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. There are no strict deadlines, however, you will be penalized by -1 points 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	Handouts	Other materials
1	Introduction, Gurobi installation		01_gurobi.pdf	grading_and_rules.pdf, gurobi-examples.zip, lp_basics_wolfram_notebook.zip
2	Semester Project, LP and ILP basics		Cocontest assignment, 02_simple_problems.pdf	Linear Programming, Duality (in Czech), Convex optimisation, Linear Programming, Duality (in English), lab02_codes.zip, 2020-cocontest-optimal-public.zip
3	ILP 1	HW1, deadline for choosing semester project	03_ilp.pdf	Notes and issues with big-M, hw1_public_instances.zip, lab03_codes.zip, settle_up_models.ipynb.zip
4	Cancelled
5	ILP 2		lab_5_peaking_power_plants.pdf, lab5_catering.pdf, lab_5_settle_up.pdf	Problem introduction videos & solutions 05_ilp_jupyters.zip, 05_solutions.zip
6	ILP 3 - Unexpected applications + Shortest Paths		Lab's exercise: tents_in_the_forest.pdf Other interesting applications: 06_fivers.pdf, game_of_fivers.pdf adversarial_dnn_and_ilp.pdf rubiks_optimal_ilp.pdf Shortest paths: 06_stp.pdf	Lab's exercise: Problem introduction videos & solutions Tents in the Forest: Jupyter Other interesting applications: Game of Fivers, Game of Fivers: Jupyter (solved) Optimal adversarial examples for a DNN via ILP, adversarial_dnn_and_ilp.zip rubiks_optimal_ilp_jupyter.ipynb.zip Shortest paths: Content-aware image resizing via SPT czech_republic.txt, Czech republic approximation (skeleton)
7	Network Flows	HW2	Lab's exercise and HW: Network flows handout (self study) Assignment of HW2 Additional materials: Optimal solver of Rubik's cube using ILP	Lab's exercise and HW: Lab materials and HW2 assignment (video), How to find an initial feasible flow for FF algorithm (video) Public instances for HW2 Additional materials: Optimal solver for Rubik's cube explained (video), ILP for Rubik's cube (jupyter)
8 Tuesday	Consultations
8 Thursday	Cancelled
9	Minimum Cost Flows	HW3	Lab's exercise and HW: Network flows 2 handout (self study) Assignment of HW3 Image reconstruction by min-cost flows Additional materials: Game of Life Pattern Synthetizator Dynamic programming handout (self study)	Lab materials and HW3 assignment (video) Public instances for HW3 image_reconstruction_jupyter.zip Additional materials: Game of Life Pattern Synthetizator via ILP (jupyter)
10	~~Practical Test~~ Traveling Salesman Problem	HW4	Lab's exercise TSP handout (self study) Assignment of HW4	Lab materials and HW4 assignment (video) Lazy constraints generation (video) Public instances for HW4 Circle approximation
11	Bratley's problem	HW5	Bratley's algorithm handout (self study), assignment of HW5	Lab materials and HW5 assignment (video), Public instances for HW5
12 Tuesday	Cancelled		Nonograms	Nonograms (jupyter)
12 Thursday	Consultations		Nonograms	Nonograms (jupyter)
13	Consultations
14	Constraint programming
15	Practical test

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.

Table of Contents

Labs

Plan of the Labs

Classroom computers