Semester Project

During the semester each student will work on a semester project. There are two different types of semester projects and each student has to choose one of them.

1. Contest: all students participating in the contest will implement a solver for one specific combinatorial optimization problem. The students' solvers will be tested in Brute on a set of instances. The goal is to find the best solutions (with respect to objective function) for the given instance in specified time limit. The evaluation is combination of finding good solutions and the achieved rank relative to other students. Each student participating in the contest can acquire some minimum number of points even if his solver is not very efficient relative to other students. For more information about the grading rules, please refer to the PDF below containing the contest description.
2. Research on chosen topic: student chooses a non-trivial problem from the combinatorial optimization area on which he/she will work during the semester (the problem has to be approved by the student's lab teacher). This assignment is especially suitable for students who need to solve a problem for some company, project, their diploma thesis etc. The assignment has two parts: (i) written report (description of the problem, survey of related work, explanation of the used method for solving the problem etc.) and (ii) implementation. The evaluation is combination of fulfillment of formal requirements and assessment of work quality by the student's lab teacher.

Assignment: cocontest_2021.pdf

Instances CC-OPT: public_instances_cc_2021.zip

Instances CC-THR: public_instances_cc_threshold_2021.zip (updated 07/04/2021 @ 12:15)

The student's work is individually evaluated by his/her lab teacher. Formal requirements are

1. Topic needs to be approved by a lab teacher.
2. Report is written in the provided template (ko_template_latex.zip, ko_template.doc, ko_template.odt).
3. Report is written in decipherable Czech or English (for English parallels, only English is allowed).
4. The number of pages of the report is 4-8.
5. Clear description of the problem.
6. Related works section is a continuous text with references to the literature (at least 3 relevant scientific articles) including correct citations.
7. Clear description of the selected method, which should be non-trivial. Students are encouraged to discuss the suitability of the selected method with his/her lab teacher. Examples of unsuitable methods: greedy algorithms for bin-packing.
8. Experiments are meaningful. The Experiments section contains description of instances, experimental environment and discussion about the results (interpretation).

The report has 3 milestones that have to be uploaded to UploadSystem (deadlines are in UploadSystem). Each milestone consists of

• Milestone 1, assignment SP_RP_M1: Problem statement and categorization, related works, MILP formulation
• Milestone 2, assignment SP_RP_M2: Description of algorithms design and their implementation
• Milestone 3, assignment SP_RP_M3: Experiments and conclusion of the work

The evaluation of the work is done after submission of milestone 3.

For your information, below you may find examples of good research reports

1. Settle up Problem. The application now has over 250k active users world-wide.
2. Branch and bound for routing problems
3. Electric vehicle routing problem
4. Scheduling in TSN with class 2 traffic
5. Optimization-based algorithm for autonomous car parking in narrow environments
6. Bounded Wang tiling
7. Traveling deliveryman problem
8. Interactive image coloring
9. Parallel knapsack problem on Xeon Phi