====== 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. There are no strict deadlines, however, you will be penalized by -1 points 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 ^ Handouts ^ Other materials ^ | 1 | Introduction, Gurobi installation | | {{ :courses:ko:01_gurobi.pdf |}}| {{ :courses:ko:grading_and_rules.pdf |}}, {{ :courses:ko:gurobi-examples.zip |}}, {{ :courses:ko:lp_basics_wolfram_notebook.zip |}}| | 2 | Semester Project, LP and ILP basics | |{{ :courses:ko:semester_project_cocontest_2020.pdf |Cocontest assignment}}, {{ :courses:ko:02_simple_problems.pdf |}} | [[https://cw.fel.cvut.cz/old/_media/courses/a4b33opt/opt.pdf|Linear Programming, Duality (in Czech)]], [[http://stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|Convex optimisation, Linear Programming, Duality (in English)]], {{ :courses:ko:lab02_codes.zip |}}, {{ :courses:ko:2020-cocontest-optimal-public.zip |}} | | 3 | ILP 1 | HW1, deadline for choosing semester project |{{ :courses:ko:03_ilp.pdf |}} | [[https://orinanobworld.blogspot.com/2011/07/perils-of-big-m.html|Notes and issues with big-M]], {{ :courses:ko:hw1_public_instances.zip |}}, {{ :courses:ko:lab03_codes.zip |}}, {{ :courses:ko:settle_up_models.ipynb.zip |}}| | 4 | **Cancelled** | | | | | 5 | ILP 2 | |{{ :courses:ko:lab_5_peaking_power_plants.pdf |}}, {{ :courses:ko:lab5_catering.pdf |}}, {{ :courses:ko:lab_5_settle_up.pdf |}} | [[https://www.youtube.com/playlist?list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J|Problem introduction videos & solutions]] \\ {{ :courses:ko:05_ilp_jupyters.zip |}}, {{ :courses:ko:05_solutions.zip |}}| | 6 | ILP 3 - Unexpected applications + Shortest Paths | | **Lab's exercise**: \\ {{ :courses:ko:tents_in_the_forest.pdf |}} \\ **Other interesting applications**: \\ {{ :courses:ko:06_fivers.pdf |}}, {{ :courses:ko:game_of_fivers.pdf |}} \\ {{ :courses:ko:adversarial_dnn_and_ilp.pdf |}} \\ {{ :courses:ko:rubiks_optimal_ilp.pdf |}} \\ **Shortest paths**: \\ {{ :courses:ko:06_stp.pdf |}} | **Lab's exercise**: \\ [[https://www.youtube.com/playlist?list=PLhMDoPPJXZWQr3a4IOw0FYVWEMq9w3t0J|Problem introduction videos & solutions]] \\ {{ :courses:ko:tents_in_the_forest.zip | Tents in the Forest: Jupyter}} \\ **Other interesting applications**: \\ [[http://rtime.felk.cvut.cz/~novakan9/ko/fivers.html|Game of Fivers]], {{ :courses:ko:game_of_fivers.zip | Game of Fivers: Jupyter (solved)}} \\ [[https://link.springer.com/article/10.1007/s10601-018-9285-6|Optimal adversarial examples for a DNN via ILP]], {{ :courses:ko:adversarial_dnn_and_ilp.zip |}} \\ {{ :courses:ko:rubiks_optimal_ilp_jupyter.ipynb.zip |}} \\ **Shortest paths**: \\ [[https://dl.acm.org/citation.cfm?id=1276390|Content-aware image resizing via SPT]] \\ {{ :courses:ko:czech_republic.txt |}}, {{ :courses:ko:image_approximation_skeleton.zip |Czech republic approximation (skeleton)}} | | 7 | Network Flows | HW2 | **Lab's exercise and HW:** \\ {{ :courses:ko:maxflow-handout.pdf | Network flows handout (self study)}} \\ {{ :courses:ko:hw2-assignment.pdf | Assignment of HW2}} \\ **Additional materials:** \\ {{ :courses:ko:ilp_rubik.pdf | Optimal solver of Rubik's cube using ILP }} | **Lab's exercise and HW:** \\ [[https://youtu.be/pWUKhsZt18E| Lab materials and HW2 assignment (video)]], [[https://youtu.be/Gxb6gMVosuc| How to find an initial feasible flow for FF algorithm (video)]] \\ {{ :courses:ko:hw2_public_instances.zip | Public instances for HW2 }} \\ **Additional materials:** \\ [[https://youtu.be/Q-6QToN62Rc| Optimal solver for Rubik's cube explained (video)]], {{ :courses:ko:ilp_rubik.zip | ILP for Rubik's cube (jupyter) }} | | 8 Tuesday | Consultations | | | | | 8 Thursday | **Cancelled** | ::: | ::: | ::: | | 9 | Minimum Cost Flows | HW3 | **Lab's exercise and HW:** \\ {{ :courses:ko:handout_mincost_flow.pdf | Network flows 2 handout (self study)}} \\ {{ :courses:ko:09_mcf.pdf | Assignment of HW3}} \\ {{ :courses:ko:reconstruction_minflow.pdf | Image reconstruction by min-cost flows}} \\ **Additional materials:** \\ {{ :courses:ko:game_of_life_ilp_generator.pdf | Game of Life Pattern Synthetizator}} \\ {{ :courses:ko:handout_dynprog.pdf | Dynamic programming handout (self study)}} | [[https://youtu.be/8D63o5ruIFQ| Lab materials and HW3 assignment (video)]] \\ {{ :courses:ko:hw3_public_instances.zip | Public instances for HW3 }} \\ {{ :courses:ko:image_reconstruction_jupyter.zip |}}\\ **Additional materials:** \\ {{ :courses:ko:game_of_life_ilp_generator.ipynb.zip | Game of Life Pattern Synthetizator via ILP (jupyter) }} | | 10 | Practical Test \\ Traveling Salesman Problem | HW4 | **Lab's exercise** \\ {{ :courses:ko:tsp-self-study.pdf | TSP handout (self study)}} \\ {{ :courses:ko:10_tsp.pdf | Assignment of HW4}} | [[https://youtu.be/olPrgTulvyI| Lab materials and HW4 assignment (video)]] \\ [[https://youtu.be/3dtkmEwB_N0| Lazy constraints generation (video)]] \\ {{ :courses:ko:hw4_public_instances.zip | Public instances for HW4 }} \\ {{ :courses:ko:circle_approximation.py | Circle approximation }} | | 11 | Bratley's problem | HW5 | {{ :courses:ko:11_bratley_handout.pdf | Bratley's algorithm handout (self study), assignment of HW5}} | [[https://youtu.be/kbQ0J6I72Ww| Lab materials and HW5 assignment (video)]], {{ :courses:ko:hw5_public_instances.zip | Public instances for HW5 }} | | 12 Tuesday | **Cancelled** | | {{ :courses:ko:nonograms.pdf | Nonograms}} | {{ :courses:ko:nonograms.zip | Nonograms (jupyter)}} | | 12 Thursday | Consultations | ::: | ::: | ::: | | 13 | Consultations | | | | | 14 | Constraint programming | | | | | 15 | Practical test| | | | ===== 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.