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.
| Week No. | Title | Notes | Materials |
|---|---|---|---|
| 1 | Introduction, Gurobi installation, LP basics | Grading and Rules Gurobi Installation Guide Gurobi Example (code) Introduction: Worksheet, Solution Transportation: Worksheet, Solution |
|
| 2 | ILP basics | CC-OPT | CoContest: Handout, Public Instances Basics: Worksheet, Solution Gurobi Official Interactive Examples Mathematical Programming Book with Examples |
| 3 | ILP 1 | HW1 | HW1: Handout , Worksheet , Solution, Public instances Catering: Worksheet , Solution ⇒ video: Introduction, Solution Tiles: Worksheet , Solution Blog about perils of big-M |
| 4 | ILP 2 | Settle Up: Worksheet , Solution ⇒ video: Introduction , Solution Peaking Power Plants: Worksheet , Solution ⇒ video: Introduction , Solution Tents: Worksheet , Solution ⇒ video: Introduction , Solution |
|
| 5 | ILP 3 | HW2 CC-T CC-R Deadline HW1 | CoContest Threshold and Ranking: Public Instances HW2: Handout , Public Instances ⇒ video: Introduction Lazy Constraints: Handout , Visualization ⇒ video: Introduction |
| 6 | Interesting ILP applications | Game of Fivers: Game , Handout , Worksheet , Solution ⇒ video: Introduction and Solution Verification of DNNs: Worksheet ⇒ video: Introduction and Solution Rubic's Cube: Worksheet ⇒ video: Introduction and Solution |
|
| 7 | Practical test | Deadline HW2 | Training Test: Handout, Public Instances |
| 8 | Max-Flow | HW3 Deadline CC-OPT | Max-Flow: Handout ⇒ video: Introduction, Solution, and HW3 HW3: Handout , Public Instances ⇒ video: Initial Feasible Flow for FF |
| 9 | Metaheuristics, consultations | Metaheuristics: Worksheet , Solution Shortest Paths: Handout , Worksheet Circle Packing: Worksheet Gurobi, Worksheet EvoTorch |
|
| 10 | Min-Cost Flow | HW4 Deadline HW3 | Minimum Cost Flow: Handout , Worksheet Images , Worksheet Pipes ⇒ video: Introduction HW4: Handout , Public Instances |
| 11 + 12 | Scheduling - Bratley's algorithm | HW5 Deadline HW4 | Bratley's algorithm and HW5: Handout , Public Instances , The Scheduling Zoo ⇒ video: Introduction Dynamic Programming: Handout |
| 13 | Consultation, selected topics | Deadline CC-T Deadline CC-R | Game of Life: Worksheet Nonograms: Worksheet Quantum Soldiers: Worksheet |
| 14 | Ungraded assessments, SP presentations, CC-R results, modeling master class | Deadline HW5 | Constraint Programming: Worksheet CoContest: Results |
If possible, bring your own computer.
OS: Debian Linux 64bit, 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++), PyCharm (Python), GVim, Netbeans are installed. CLion 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).