Warning

# 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
Consultation 1 (Czech)
Gurobi installation guide (pdf)
Gurobi examples (zip)
2 Semester Project, LP and ILP basics
Consultation 2 (Czech)
CC CoContest: Assignment, Public instances
ILP Basics: Handout, Jupyter, Solutions, Wolfram illustration
Linear Programming, Duality (in Czech)
3 ILP 1
Consultation 3 (Czech)
HW1 HW1: Assignment, Public instances
Settle up: Handout, Jupyter, Video
Solution (Jupyter), Solution (video)
Catering: Handout, Jupyter, Video
Solution (Jupyter), Solution (video)
Notes and issues with big M
4 ILP 2
Consultation 4 (Czech)
Tents in the Forest: Handout, Jupyter, Video
Solution (Jupyter), Solution (video)
Peaking Power Plants: Handout, Jupyter, Video
Solution (Jupyter), Solution (video)
5 Consultation
Consultation 5 (Czech)
Optional materials on SPT: Content-aware image resizing via SPT, SPT (Handout), czech_republic.txt, image_approximation_skeleton.zip
6 ILP 3
Consultation 6 (Czech)
Game of Fivers: Game, Video, Handout, Jupyter (solved)
Rubik's Cube: Video, Handout, Jupyter (solved)
Adversarial examples for DNN via ILP: Video, Handout, Jupyter (solved)
7 Network flows
Consultation 7 (Czech)
HW2 Network flows handout (self study), Assignment of HW2, Lab materials + HW2 (Video), Initial feasible flow for FF (Video), Public instances for HW2
8 Consultation
Consultation 8 (Czech)
Optional materials: Nonograms (PDF), Nonograms (Jupyter)
Dynamic programming (self study)
9 Minimum Cost Flows
Consultation 9 (Czech)
HW3 Handout and HW3: Handout (PDF), Assignment of HW3, Lab materials and HW3 assignment (Video) Public instances
Image reconstruction: Solution (PDF), Solution (Jupyter)
10 Practical test
Consultation 10 (Czech)
11 Traveling Salesman Problem
Consultation 11 (Czech)
HW4 Handout: TSP handout (self study), Lab materials and HW4 (Video)
HW4: Assignment of HW4, Public instances for HW4
Lazy constraints: Lazy constraints generation (Video), Circle approximation (Python), Circle approximation (Wolfram notebook)
12 Bratley's problem
Consultation 12 (Czech)
HW5 Bratley and HW5: Handout (self study), Lab materials and HW5 (Video), Public instances for HW5, Scheduling ZOO
13 ILP/CP master class
Consultation 13 (Czech)
Handout: Masterclass (PDF)
14 Reserve

## 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).