Table of Contents

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 Example (code)
Introduction: Worksheet Solution
Transportation: Worksheet Solution
Optional: Simplex worst case notes, Wolfram simplex, LP algorithms
2 Semestral work, ILP basics CC-O CoContest: Handout Public instances
Basics: Worksheet Solution
Gurobi Official Interactive Examples
Mathematical Programming Book with Examples
3 ILP 1 HW1 HW1: Handout Public instances
Call center Worksheet Solution
Catering: Worksheet Solution
Video Solution
Computable vs uncomputable functions (optional)
4 ILP 2 Settle Up: Worksheet Solution
Video Solution
Peaking Power Plants: Worksheet Solution
Video Solution
Tiles: Worksheet Solution
Blog about perils of big-M
5 ILP 3 HW2 HW2: Handout Public instances
Video
Lazy Constraints: Handout Colab notebook Circle approximation Wolfram notebook
Video
6 Unexpected ILP applications Game of Fivers: Game Handout Worksheet Solution
Video with solution
Rubic's Cube: Handout Worksheet
Video with solution
Verification of DNNs: Handout Worksheet
Video with solution
7 Metaheuristics + consultations CC-T/R Metaheuristics: Worksheet
Circle packing: Worksheet (ILP) , Worksheet (GPU)
Cocontest Threshold: Public instances
8 SPT SPT: Handout
Function Approximation: Worksheet, Data
Content-aware image resizing: Paper Demo
9 Max flow HW3 Max-Flow: Handout Lazy separation notes (optional)
⇒ video: Introduction, Solution, and HW3
HW3: Handout Public Instances
⇒ video: Initial Feasible Flow for FF
10 Min-cost flow
11 [Cancelled]
12 DP/approx
13 Scheduling HW4
14 Scheduling, CP masterclass

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