====== 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 [[https://cw.felk.cvut.cz/brute/|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 | | {{ :courses:ko:2024_lab01_grading_and_rules.pdf | Grading and Rules}} \\ {{ :courses:ko:2024_lab01_gurobi_installation_guide.pdf | Gurobi Installation Guide}} \\ {{ :courses:ko:2024_lab01_gurobi_example.zip | Gurobi Example (code)}} \\ {{ :courses:ko:2024_lab01_lp_basics.zip | LP Basics (Wolfram notebook)}} \\ [[https://colab.research.google.com/drive/1635gKL4Sp-_Y1PkQagsjFt74wtWrLqKU?usp=sharing | Introduction (colab TODO)]] \\ [[https://colab.research.google.com/drive/1vRegLBA7Kc19Yu8s5XFHKD8D0dKVyRgl | Transportation (colab TODO)]] \\ [[https://colab.research.google.com/drive/1I3frh0Lhhk59maXQIvoRsbYV824ZYg3z?usp=sharing | Introduction (colab solved)]] \\ [[https://colab.research.google.com/drive/1PenAW4pRK5DiwZuomLuZMctBrw38ZsNR | Transportation (colab solved)]] |
| 2 | ILP basics | CC-OPT | {{ :courses:ko:2024_cocontest.pdf | CoContest}}, {{ :courses:ko:2024_cocontest_public_instances_opt.zip | Public Instances}} \\ [[https://colab.research.google.com/drive/1DgCHpI_1g8-4IkGCt1LPCE1TE2fIE1qL | ILP Basics (colab TODO)]] \\ [[https://colab.research.google.com/drive/1-M-rjNcvrWH8g7NSN9Nn5ApilotIize- | ILP Basics (colab solved)]] \\ [[https://www.gurobi.com/jupyter_models/?_sft_difficulty_level=beginner | Gurobi Official Interactive Examples]] \\ [[https://www.wiley.com/en-us/Model+Building+in+Mathematical+Programming%2C+5th+Edition-p-9781118443330 | Mathematical Programming Book with Examples]] |
| 3 | ILP 1 | HW1 | {{ :courses:ko:2024_hw1.pdf | HW1 Assignment}}, {{ :courses:ko:2024_hw1_public.zip | Public Instances}} \\ [[https://colab.research.google.com/drive/1w70DFyQU-qtYGnSE7OCCxqYyH1eYCRiT?usp=sharing|Call Center (colab TODO)]] \\ [[https://colab.research.google.com/drive/1_hGqDdLiTiyrCk5lxifSNjbLEgyDIxKG?usp=sharing|The Catering Problem (colab TODO)]] \\ [[https://colab.research.google.com/drive/1dHubmtXao1c3O9q2_Jdb4Z0ZiR0xNGc5?usp=sharing|Tiles (colab TODO)]] \\ [[https://colab.research.google.com/drive/1IpaW4vAS7WsKRGmo2nztIQjmPc6HBUn3?usp=sharing|Call Center (colab solved)]] \\ [[https://colab.research.google.com/drive/1810qGeZvSc4OMSDVM1zN0l2gKM1Zjbja?usp=sharing|Catering (colab solved)]] \\ [[https://colab.research.google.com/drive/1gdZD55KiMUAMO1KyPkqRNh2PK93j6sNz?usp=sharing|Tiles (colab solved)]] \\ **Catering Video:** ([[https://www.youtube.com/watch?v=zELw0vFn1Ag|introduction]], [[https://www.youtube.com/watch?v=_KrRTK3aWMQ|solution]]) \\ [[https://orinanobworld.blogspot.com/2011/07/perils-of-big-m.html| Blog about perils of big-M]]|
| 4 | ILP 2 | | [[https://colab.research.google.com/drive/1PMfxzrG4CMx1X8TLJcShneyS55RlLzOj?usp=sharing|Settle Up (colab TODO)]] \\ [[https://colab.research.google.com/drive/1MIG7gFD5jYnZw1JAffZ-kJ1riApEtrPZ?usp=sharing|Peaking Power Plants (colab TODO)]] \\ [[https://colab.research.google.com/drive/1hK9Pk_Ve-6i6kGb1mbD9cOEYsZYYMC60?usp=sharing|Tents (colab TODO)]] \\ [[https://colab.research.google.com/drive/1L1e3XRsSm6Ooobm2y4aNSshwQgJr1Ss1?usp=sharing|Settle Up (colab solved)]] \\ [[https://colab.research.google.com/drive/1jS5QlfEGb_9IwLYSAKz_WzcqCdY76EJC?usp=sharing|Peaking Power Plants (colab solved)]] \\ [[https://colab.research.google.com/drive/16and0I-TNYV0vvyGZd1myMQZHeLZmXpl?usp=sharing|Tents (colab solved)]] \\ **Settle Up Video:** ([[https://www.youtube.com/watch?v=Bk3_4xrYfxk&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=2|introduction]], [[https://www.youtube.com/watch?v=ttee0c7ut1s&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=4|solution]]) \\ **Peaking Power Plants Video:** ([[https://www.youtube.com/watch?v=2eu-TRY6I88&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=5|introduction]], [[https://www.youtube.com/watch?v=ZxXRYcBDrM8&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=7|solution]]) \\ **Tents Video:** ([[https://www.youtube.com/watch?v=U7_vIpIT3Ew&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=6|introduction]], [[https://www.youtube.com/watch?v=ZmWZ3oNmmU4&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=8|solution]]) |
| 5 | ILP 3 | HW2 \\ **Deadline HW1** | {{ :courses:ko:2024_hw2.pdf | HW2 Assignment}}, {{ :courses:ko:2024_hw2_public.zip | Public Instances}}, [[https://youtu.be/olPrgTulvyI?si=tkjOjb4ZjVfALn0Y|Video]] \\ **Lazy Constraints:** {{ :courses:ko:2024_lab05.pdf | Handout }}, [[https://www.youtube.com/watch?v=3dtkmEwB_N0|Video]], [[https://colab.research.google.com/drive/1ReW-ejA9FIMNOtIvBq-WYJZnmmy0RqoU?usp=sharing|Colab Notebook]] |
| 6 | Interesting ILP applications | | **Game of Fivers:** [[http://rtime.felk.cvut.cz/~novakan9/ko/fivers.html | Game]], [[https://www.youtube.com/watch?v=RTqgBaKgQHE|Video]], {{ :courses:ko:2024_ilp_fivers.pdf |Handout }}, [[https://colab.research.google.com/drive/1E1zBjFBRltK2wXKiLSQ1nsDKR78TY7kf?usp=sharing | Colab (TODO)]], [[https://colab.research.google.com/drive/1oVes-ln0MTfhURkNJLSHN7htFaMClbA4 | Colab (Solved)]] \\ **Rubik's Cube:** [[https://www.youtube.com/watch?v=Q-6QToN62Rc|Video]], [[https://colab.research.google.com/drive/1p6bkp6avEBhtEL42ZJM9L_WtarS0WdxN?usp=drive_link|Colab]]\\ **Verification of DNNs:** [[https://www.youtube.com/watch?v=VFHqi7hL7E8&feature=youtu.be|Video]], [[https://colab.research.google.com/drive/1KvE7-hgS8X2F7GUfQsfRVwoVAXvbGehw?usp=drive_link|Colab]] |
| 7 | Metaheuristics + consultations | CC \\ **Deadline HW2**  | {{ :courses:ko:2024_cocontest_public_instances_threshold.zip | CoContest Threshold Public Instances}} \\ [[ https://colab.research.google.com/drive/1NHsmcSuZ4enlfAQvdD8-GfHyk0ySlDFG | Metaheuristics (colab TODO) ]] \\ [[ https://colab.research.google.com/drive/1_Thl8IjWLtQe38NwKe1wo3iCHoqjuPaA | Metaheuristics (colab solved) ]] \\ {{ :courses:ko:2024_lab07_optional.pdf | Handout SPT (optional) }}, [[https://colab.research.google.com/drive/1JUOs4AwLuRITQXWFIviusFKBZ6wI6MhF?usp=sharing|Function approximation (colab)]] \\ **Practical Test Training:** {{ :courses:ko:2024_practice_test.pdf | Assignment}}, {{ :courses:ko:2024_practice_test_public_test_instances.zip | Public Instances }} |
| 8 | **Practical test**| **Deadline CC-OPT** | 
| 9 | Max-Flow | HW3 | **Max-Flow:** {{ :courses:ko:2024_flow_handout.pdf |Handout}}, [[https://www.youtube.com/watch?v=pWUKhsZt18E|Video]] \\ **HW3:** {{ :courses:ko:2024_hw03.pdf | HW3 Assignment}}, [[https://www.youtube.com/watch?v=Gxb6gMVosuc| Initial feasible flow for FF (video)]], {{ :courses:ko:2024_hw3_public.zip | Public instances}}|
| 10  | Consultation + selected topics  | | **Optional materials:** {{ :courses:ko:2024_mincostflow.pdf | Min Cost Flow}}, {{:courses:ko:2024_handout_dp.pdf | Dynamic programming}}, [[https://colab.research.google.com/drive/1HYPZZb6Oio_8ziI_l7Tu7MIn3DHsYlMe?usp=sharing|Nonogram (colab TODO)]], [[https://colab.research.google.com/drive/1zyIa5artTqO4qhpEb0B8J948-Y0rkfPn?usp=sharing|Pipes (colab solved)]], [[https://www.youtube.com/watch?v=8D63o5ruIFQ&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=17 |Min-Cost Flow (Video)]]|
| 11 | Scheduling - Bratley's algorithm | HW4 \\ **Deadline HW3** | {{ :courses:ko:2024_hw4.pdf | HW4 Assignment (+ Handout)}}, {{ :courses:ko:2024_hw4_public.zip | Public Instances}}, [[https://www.youtube.com/watch?v=kbQ0J6I72Ww&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=17&pp=iAQB | Video]] \\ [[http://schedulingzoo.lip6.fr/|The Scheduling ZOO]] |
| 12 + 13 | Modeling master class | **Deadline HW4** \\ **Deadline CC** | [[https://colab.research.google.com/drive/1kqTZWdRW9EkE5wjeZ8_8EhO2NePyhkUx?usp=sharing|Masterclass (colab)]], {{ :courses:ko:2024_lab11_data.zip | data (zip)}} \\ {{ :courses:ko:cpoptimizer.pdf | CP overview (slides)}} \\ [[https://colab.research.google.com/drive/1OCeWhzMf-05FBkZb-bcaV3NjtKH451za?usp=sharing|Image Reconstruction (colab)]], [[https://colab.research.google.com/drive/1lVejrAC7xGuDgTSsBm1lLeGmR4_XqXU7?usp=sharing|Quantum Soldiers (colab)]], [[https://colab.research.google.com/drive/1c0zrETQvM-GY1T22lEOoGWy6sSrzwwDy?usp=sharing|Game of Life (colab)]], [[https://www.youtube.com/watch?v=xP5-iIeKXE8&ab_channel=PhillipBradbury|Game of Life (video)]], [[https://playgameoflife.com/|Game of Life (game)]] |
| 14 | Consultations, ungraded assessments, SP presentations | | |
===== Classroom computers =====
//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 [[https://svti.fel.cvut.cz/cz/services/vpn.html | FEL VPN (CZ)]]/[[ https://svti.fel.cvut.cz/en/services/vpn.html | FEE VPN (EN)]].