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. 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
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)
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
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
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
Game of Life Pattern Synthetizator
Dynamic programming handout (self study)
Lab materials and HW3 assignment (video)
Public instances for HW3
image_reconstruction_jupyter.zip
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
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.