====== 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:rm35koa:koa_rules.pdf |Grading and rules}}\\ {{ :courses:rm35koa:01_installation_guide.pdf |Gurobi installation guide}}\\ {{ :courses:ko:2024_lab01_gurobi_example.zip |Gurobi code 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 notebook)]]\\ [[https://colab.research.google.com/drive/17kYBA8tgwj7AV8D5F9YCytxUlpqO_q_d|Transportation problem (colab notebook)]] \\ {{ :courses:rm35koa:01_koa_simplex_notes.pdf |Simplex worst case notes (optional)}}\\ {{ :courses:rm35koa:01_worst_case_simplex.nb.zip |Wolfram simplex (optional)}}\\ {{ :courses:rm35koa:karmarkarsalgorithmforlinearprogrammingproblem-091203083518-phpapp02.pdf |LP algorithms (optional)}}  |
| 2 | Semestral work, ILP basics | | {{ :courses:rm35koa:cocontest_2024_koa.pdf |Cocontest (pdf)}}, {{ :courses:ko:2024_cocontest_public_instances_opt.zip |Public instances}}, {{ :courses:ko:2024_cocontest_public_instances_threshold.zip |Public instances threshold}}\\ [[https://colab.research.google.com/drive/1I3frh0Lhhk59maXQIvoRsbYV824ZYg3z?usp=sharing | Introduction (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]]\\ {{ :courses:rm35koa:koa_computablefunctions.pdf |Computable vs uncomputable functions (optional)}}|
| 3 | ILP 1 | HW1 | [[https://colab.research.google.com/drive/1DgCHpI_1g8-4IkGCt1LPCE1TE2fIE1qL | ILP basics (colab TODO)]], [[https://drive.google.com/file/d/10MJ_4NgYOXqI9FFZ-jA7rAv0UmRbIJk8/view?usp=sharing | ILP basics (colab solved)]]\\ [[https://drive.google.com/file/d/17kYBA8tgwj7AV8D5F9YCytxUlpqO_q_d/view?usp=sharing | Transportation (colab TODO)]], [[https://drive.google.com/file/d/1Th6BIU0khnJuiT6MB1m21on3ace5NyHY/view?usp=sharing | Transportation (colab solved)]]\\  {{ :courses:rm35koa:hw1_koa_2024.pdf |HW1 assignment (pdf)}}, {{ :courses:rm35koa:hw1_koa_public_test_cases.zip |Public instances (zip)}}  |
| 4 | ILP 2 | | [[https://drive.google.com/file/d/1WnouSD5_y57RIfr6VWhLP7zF4pHRTtGK/view?usp=sharing | Call center (colab TODO)]], [[https://colab.research.google.com/drive/1IpaW4vAS7WsKRGmo2nztIQjmPc6HBUn3?usp=sharing|Call Center (colab solved)]]\\ [[https://colab.research.google.com/drive/1_hGqDdLiTiyrCk5lxifSNjbLEgyDIxKG?usp=sharing|The Catering Problem (colab TODO)]], [[https://colab.research.google.com/drive/1810qGeZvSc4OMSDVM1zN0l2gKM1Zjbja?usp=sharing|Catering (colab solved)]], [[https://www.youtube.com/watch?v=zELw0vFn1Ag|Video]], [[https://www.youtube.com/watch?v=_KrRTK3aWMQ|Solution]]\\ [[https://colab.research.google.com/drive/1dHubmtXao1c3O9q2_Jdb4Z0ZiR0xNGc5?usp=sharing|Tiles (colab TODO)]], [[https://colab.research.google.com/drive/1gdZD55KiMUAMO1KyPkqRNh2PK93j6sNz?usp=sharing|Tiles (colab solved)]]\\ [[https://colab.research.google.com/drive/1PMfxzrG4CMx1X8TLJcShneyS55RlLzOj?usp=sharing|Dlužníček (Colab TODO)]], [[https://colab.research.google.com/drive/1L1e3XRsSm6Ooobm2y4aNSshwQgJr1Ss1?usp=sharing|Dlužníček (colab solved)]], [[https://youtu.be/Bk3_4xrYfxk?si=ekTr-xUbFhiLuQm-|Video]], [[https://www.youtube.com/watch?v=ttee0c7ut1s&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=4|Solution]]\\ Blog about [[https://orinanobworld.blogspot.com/2011/07/perils-of-big-m.html|perils of big-M]]  |
| 5 | ILP 3 | HW2 | {{ :courses:rm35koa:hw2_koa.pdf |HW2 assignment (pdf)}} {{ :courses:ko:2024_hw2_public.zip | Public instances}}, [[https://youtu.be/olPrgTulvyI?si=tkjOjb4ZjVfALn0Y|Video]] \\ Lazy Constraints: {{ :courses:rm35koa:05_tsp_koa.pdf |Handout (pdf)}}, [[https://www.youtube.com/watch?v=3dtkmEwB_N0|Video]], [[https://colab.research.google.com/drive/1ReW-ejA9FIMNOtIvBq-WYJZnmmy0RqoU?usp=sharing|Colab Notebook]], {{ :courses:ko:circle_approx.py.zip |Circle approximation (zip)}}, {{ :courses:ko:circle_wolfram.nb.zip |Wolfram notebook (optional)}}\\ [[https://colab.research.google.com/drive/1MIG7gFD5jYnZw1JAffZ-kJ1riApEtrPZ?usp=sharing|Peaking Power Plants (colab TODO)]], [[https://www.youtube.com/watch?v=2eu-TRY6I88&list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J&index=5|Video]], [[https://colab.research.google.com/drive/1jS5QlfEGb_9IwLYSAKz_WzcqCdY76EJC?usp=sharing|Peaking Power Plants (colab solved)]], [[https://youtu.be/ZxXRYcBDrM8?si=UoqzolNtdIGAbMMg|Solution (video)]] |
| 6 | Unexpected 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 (pdf)}}, [[https://colab.research.google.com/drive/1E1zBjFBRltK2wXKiLSQ1nsDKR78TY7kf?usp=sharing | Colab (TODO)]], [[https://colab.research.google.com/drive/1exzncvmKiv6D99DIOzoWmJQ6DnJMiwuX?usp=drive_link|Colab (solution)]] \\ Rubik's Cube: [[https://www.youtube.com/watch?v=Q-6QToN62Rc|Video]], {{ :courses:ko:2024_rubik.pdf |Handout (pdf)}},[[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]], {{ :courses:ko:2024_adversarial_dnn_and_ilp.pdf | Handout (pdf)}}, [[https://colab.research.google.com/drive/1KvE7-hgS8X2F7GUfQsfRVwoVAXvbGehw?usp=drive_link|Colab]] |
| 7 | Metaheuristics + consultations	 |  | [[ 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_cocontest_public_instances_threshold.zip |Public instances threshold}}  |
| 8 | SPT | CC-O | {{ :courses:rm35koa:lab08_spt.pdf |Handout (pdf)}}, [[https://colab.research.google.com/drive/1JUOs4AwLuRITQXWFIviusFKBZ6wI6MhF?usp=sharing|Function approximation (colab)]] {{ :courses:ko:czech_republic.txt |}}, [[https://perso.crans.org/frenoy/matlab2012/seamcarving.pdf|Content-aware image resizing]], [[https://trekhleb.dev/js-image-carver/|Online demo]] |
| 9 | Max flow | HW3 | Max-Flow: {{ :courses:rm35koa:09_lab_maxflow.pdf |Handout (pdf)}}, [[https://www.youtube.com/watch?v=pWUKhsZt18E|Video]], {{ :courses:rm35koa:koa_maxflow_lazy_separation.pdf |Lazy separation notes (optional)}} \\ HW3: {{ :courses:rm35koa:09_hw3_flows.pdf |HW3 assignment (pdf)}}, [[https://www.youtube.com/watch?v=Gxb6gMVosuc| Initial feasible flow for FF (video)]], {{ :courses:ko:2024_hw3_public.zip | Public instances}}  |
| 10 | Min-cost flow |  | Min-cost flow: {{ :courses:rm35koa:lab10_mincostflow.pdf |Handout (pdf)}}, {{ :courses:rm35koa:lab10_mcf_tracking.pdf |Object tracking (pdf)}}, [[https://youtu.be/8D63o5ruIFQ?si=wPEBZDQ-ZWDtAnLV|Object tracking (video)]] |
| 11 | DP/approximation | | Min-cost flow: [[https://colab.research.google.com/drive/1OCeWhzMf-05FBkZb-bcaV3NjtKH451za?usp=sharing|Image reconstruction (colab)]]  \\ Multicommodity flows: [[https://colab.research.google.com/drive/1zyIa5artTqO4qhpEb0B8J948-Y0rkfPn?usp=drive_link|Pipe puzzle (colab)]] \\ DP: {{ :courses:rm35koa:2024_handout_dp.pdf |Handout (pdf)}}, [[https://colab.research.google.com/drive/1UbFZmjT4Z1wCrsj3Sqc3AF8gFQe6vvbk?usp=sharing|Optimal coin system design (colab)]]  |
| 12 | cancelled	 | |Optional materials: [[https://colab.research.google.com/drive/1HYPZZb6Oio_8ziI_l7Tu7MIn3DHsYlMe?usp=sharing|Nonogram (colab TODO)]], [[https://drive.google.com/file/d/1tzyS0-mNRREKp29nKntbf1Fj8fsJ8eIx/view?usp=sharing|Game of Life sythetize (colab solved)]],  [[https://www.youtube.com/watch?v=xP5-iIeKXE8&ab_channel=PhillipBradbury|Game of Life (video)]], [[https://playgameoflife.com/|Game of Life (game)]] \\ [[https://colab.research.google.com/drive/1lVejrAC7xGuDgTSsBm1lLeGmR4_XqXU7?usp=sharing|Computational proof of Euler's impossible puzzle (colab)]] |
| 13 | Scheduling	 | HW4 |  {{ :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]] |
| 14 | Reserve, CP masterclass  | | CP: [[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)}} \\ Circle packing: [[https://colab.research.google.com/drive/1zf-bvRD7LZR2oYN7GkYo0ZErfZ1FzTUe?usp=sharing| Colab (solved)]]  \\ Cocontest: {{ :courses:rm35koa:cocontest2024_results.pdf |Results (pdf)}} |
===== 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 [[https://svti.fel.cvut.cz/cz/services/vpn.html | FEL VPN (CZ)]]/[[ https://svti.fel.cvut.cz/en/services/vpn.html | FEE VPN (EN)]].