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

**NOTE: There is GUROBI 9 in Brute. Features highlighted in release notes of version 10 are not available.**

[[https://www.gurobi.com/documentation/current/refman/detailed_release_notes_10.html | Gurobi 10 release notes]]


===== Plan of the Labs =====

^ Week No. ^ Title ^ Notes ^ Materials ^
| 1 | Introduction, Gurobi installation, LP basics | | {{ :courses:rm35koa:grading_and_rules_koa_2023.pdf |Grading and rules (pdf)}} \\ {{ :courses:rm35koa:01_gurobi.pdf |Gurobi installation guide (pdf)}} \\ {{ :courses:rm35koa:gurobi-examples.zip |Gurobi examples (zip)}} \\ {{ :courses:rm35koa:lp_basics_wolfram_notebook.zip | LP Basics (Wolfram notebook)}}  |
| 2 | Semestral work, ILP basics | | {{ :courses:rm35koa:cocontest_koa_2023.pdf |Cocontest assignment (pdf)}} \\ {{ :courses:rm35koa:ilp_basics.pdf |ILP basics (pdf) }}, {{ :courses:rm35koa:ilp_basics.ipynb.zip |ILP basics (Jupyter)}}  |
| 3 | ILP 1 |  | **Knights placement:** {{ :courses:ko:ko_test_knights_placement.pdf |Handout (pdf)}} \\ **Catering:** {{ :courses:ko:catering_2023.pdf | Handout}}, {{ :courses:ko:catering.zip | Jupyter}}, [[https://www.youtube.com/watch?v=zELw0vFn1Ag|Video]], [[https://youtu.be/_KrRTK3aWMQ|Solution (video)]], {{ :courses:ko:catering-solution.zip |Solution (jupyter)}} \\ [[https://orinanobworld.blogspot.com/2011/07/perils-of-big-m.html|Notes and issues with big M]] \\ **Tiles:** {{ :courses:ko:tiles.pdf | Handout}} {{ :courses:ko:tiles.zip | Jupyter}}, {{ :courses:ko:tiles_sol.zip | Solution (jupyter)}} |
| 4 | ILP 2 | | **Settle up:** {{ :courses:ko:settle-up.pdf | Handout}}, {{ :courses:ko:settle-up.zip | Jupyter}}, [[https://www.youtube.com/watch?v=Bk3_4xrYfxk|Video]], {{ :courses:rm35koa:settle_up_models.zip |Solution (jupyter)}}, [[https://youtu.be/ttee0c7ut1s|Solution (video)]] \\ **Call center:** {{ :courses:rm35koa:callcenter_koa_.pdf |Handout (pdf)}}, {{ :courses:ko:call_center_scheduling_todo.ipynb.zip |Call center (jupyter)}} \\ **Peaking power plants:** {{ :courses:rm35koa:peaking_power_plants.pdf |Handout (pdf)}}, {{ :courses:rm35koa:peaking_power_plants_todo.ipynb.zip |Handout (jupyter)}}, [[https://youtu.be/2eu-TRY6I88|Video]],  {{ :courses:rm35koa:peaking_power_plants.ipynb.zip |Solution (jupyter)}}, [[https://youtu.be/ZxXRYcBDrM8|Solution (video)]] \\ **Tents in the forest:** {{ :courses:ko:tents_in_the_forest.pdf |Handout (pdf)}}, {{ :courses:ko:tents_in_the_forest.ipynb.zip |Handout (jupyter)}}, [[https://youtu.be/U7_vIpIT3Ew|Video]] |
| 5 | ILP 3 | HW1 | **HW1:** {{ :courses:rm35koa:05_tsp.pdf |Assignment}}, [[https://youtu.be/olPrgTulvyI|Video]], {{ :courses:ko:hw2_public.zip |Public instances (zip)}}, \\ **Lazy constraints:** {{ :courses:rm35koa:main.pdf |Handout (pdf)}}, [[https://youtu.be/3dtkmEwB_N0|Video]], {{ :courses:ko:circle_wolfram.nb.zip |Circle approximation (Wolfram notebook)}}, {{ :courses:ko:circle_approx.py.zip |Circle approximation (python)}}  |
| 6 | Interesting ILP applications | | **Game of Fivers:** [[http://rtime.felk.cvut.cz/~novakan9/ko/fivers.html|Game]], [[https://youtu.be/RTqgBaKgQHE|Video]], {{ :courses:ko:06_ilp.pdf |Handout (pdf)}}, {{ :courses:ko:game_of_fivers_todo.ipynb.zip |Handout (jupyter)}} \\ **Rubik's cube:** [[https://youtu.be/Q-6QToN62Rc|Video]], {{ :courses:ko:rubik.pdf |Handout (pdf)}}, {{ :courses:ko:use_an_ilp_to_solve_the_cube_of_rubik.ipynb.zip |Handout (jupyter)}} \\ **Verification of DNNs:**  [[https://youtu.be/VFHqi7hL7E8|Video]], {{ :courses:ko:adversarial_dnn_and_ilp.pdf |Handout (pdf)}}, {{ :courses:ko:adversarial_dnn_and_ilp.ipynb.zip |Handout (jupyter)}} |
| 7 | Metaheuristics + consultations	 | | **Metaheuristics:** {{ :courses:ko:ko_metaheuristics_student.zip | Handout (jupyter)}}  \\ **CoContest:** {{ :courses:ko:2023public_threshold.zip | Threshold public instances}}  |
| 8 | SPT | | **Materials on SPT:** {{ :courses:ko:lab_07_spt.pdf |Handout (pdf)}}, {{ :courses:ko:czech_republic.txt |}}, {{ :courses:ko:image_approximation_skeleton.zip |}}, [[https://dl.acm.org/doi/10.1145/1275808.1276390|Content-aware image resizing]]|
| 9 | Max flow | HW2 | **Max-Flow:** {{ :courses:rm35koa:maxflow-handout.pdf |Handout (pdf)}}, [[https://youtu.be/pWUKhsZt18E|Lab materials (video)]]\\ **HW2:** {{ :courses:rm35koa:08_flows.pdf |Assignment (pdf)}}, [[https://youtu.be/Gxb6gMVosuc|Initial feasible flow for FF (video)]], {{ :courses:ko:hw3_public_instances.zip |Public instances (zip)}}  |
| 10 | Min-cost flow |  | **Min-cost flow:** {{ :courses:rm35koa:handout_mincost_flow.pdf |Handout (pdf)}} \\ **Image reconstruction:** {{ :courses:rm35koa:reconstruction_minflow.pdf | Handout (pdf)}}, {{ :courses:rm35koa:image_reconstruction_jupyter.zip |Handout (jupyter)}} \\ **Object tracking:** {{ :courses:ko:09_mcf.pdf |Handout (pdf)}} \\ **Multicommodity flows:** [[https://www.gamescrush.com/line-puzzle-pipe-art-game|Pipe art puzzle]] |
| 11 | Lab canceled - Monday schedule | | **Optional materials:** {{ :courses:ko:handout_dynprog.pdf |Dynamic programming (pdf)}}, {{ :courses:ko:nonograms.pdf |Nonograms (pdf)}}, {{ :courses:ko:nonograms.zip | Nonograms (zip)}} |
| 12 | Consultation and Scheduling - Bratley's algorithm	 | HW3 | **Bratley and HW3:** {{ :courses:rm35koa:bratley_hw3.pdf |Assignment (pdf)}}, [[https://youtu.be/kbQ0J6I72Ww|Lab materials and HW3 (video)]], {{ :courses:ko:hw4_bratley_public_instances.zip |Public instances (zip)}},  [[http://schedulingzoo.lip6.fr/|Scheduling ZOO]]   |
| 13 | Modeling master class	 | |  **Advanced modeling:** {{ :courses:ko:masterclass.pdf |Handout (pdf)}}, {{ :courses:ko:masterclass_jupyter.zip |Handout (jupyter)}},\\ **CP overview:** {{ :courses:ko:cpoptimizer.pdf |Presentation (pdf)}} |
| 14 | Reserve, ungraded assessments  | | **Game of Life**: {{ :courses:ko:game_of_life_ilp_generator.pdf |Handout (pdf)}}, {{ :courses:ko:game_of_life_ilp_generator.ipynb.zip |Handout (jupyter)}} |
===== 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)]].