Back to Homepage

Operations Research Programming Languages
Course requirements
Lesson 1
Lesson 2
Lesson 3
Lesson 4
Lesson 5
Lesson 6
Lesson 7
Lesson 8
Lesson 9
Lesson 10
Lesson 11
Lesson 12
Lesson 13
Lesson 14

Course requirements

I. Summary

Attendence: You have to attend at least 70% of the lectures (that is 10 lectures out of 14). There is an exception however: If you are ill, then stay home. You can bring a medical certificate afterwards and I will accept your absence. (Please go through the material on your own in this case. You can send me e-mails if you have any questions at pfeiferd at math dot bme dot hu.)
Test: On Lesson 13, we will have a test that is worth 50 points. This will be an open-book test. You can use your notes and the internet, but not your friends. (Do not communicate through facebook/Discord/etc. either!) You will need to use your own laptop to complete the test. You may not use generative AI to solve the exam problem.
Homework: You will have to form a team of 3-4 students and choose one of the Homeworks below. This is a difficult modelling exercise. Each team has to choose a different homework. The choice of teams and the choice of homework has to be done by the end of Lesson 9. Please send me the team names, team members, and the chosen homework to pfeiferd at math dot bme dot hu. Each homework consists of two parts. One XPress Mosel file and one presentation (Power Point, LaTeX, PDF, etc.). On the last lecture (Lesson 14), you will have to present your homework. This is also worth 50 points.
Grading: The course is worth a total of 100 points (50 from the test, 50 from the homework). In order to pass, you will need to obtain at least 10 points from the test and at least 10 points from the homework. The final grade will be the following:

Grade	Grade name	Points
5	Excellent	85-100
4	Good	70-84
3	Satisfactory	55-69
2	Passing	40-54
1	Unsatisfactory	0-39

II. About the test

You have to use your own laptop.
You may run your code on the university server through PuTTY.
It is an open book test. You can use your notes and the internet, but not your friends. (Do not communicate through facebook/Discord/etc. either!) You may not use generative AI to solve the exam problem.
Total points: 50.
Total time: 90 minutes.
Send the solutions to me via e-mail, to pfeiferd at math dot bme dot hu. Title the e-mail "ORPL Test - NAME, NEPTUN", where NAME is your name, and NEPTUN is your Neptun code. Attach the Mosel files you created.
There will be two test retakes:
- Retake 1: December 19, 2025, 1:15 - 2:45 PM, H601
If you choose to retake the test, your new result will overwrite your previous result.

III. Homeworks

You have to form teams of 3 to 4 people.
Each team has to choose a homework from the modelling problems below. Each team has to choose a different homework.
Your choice of team and choice of homework has to be made by the end of Lesson 9. Send me your team names, team members and choice of homework to pfeiferd at math dot bme dot hu.
If two teams happen to choose the same homework, the earlier team will be granted their choice. I will mark the homeworks on this page if they are taken.
Each homework consists of two parts: Creating a Mosel model that solves the given problem, and creating a presentation (Power Point, LaTeX, PDF, etc.).
Both the Mosel model and the presentation has to be sent to me by the start of Lesson 14.
On Lesson 14, each team will have to present their model. Every team member has say something in the presentation (preferably an equal amount). The presentation should end with a code demonstration. I will give the model parameters for your code.
Each presentation has to contain the following: Most important constraints modelled (in mathematical notation, e.g. sums, forall constraints, implications, etc.); the solver(s) used; the modelling theorem(s) used; modelling difficulties/challenges; and credits (who has done what).

III./1. Homework choice 1: Crossword

Parameters: The size (width times height) of the crossword.

Your task is to create a random filled out crossword of the given size. Each word in the crossword has to start and end with an empty cell (that's where the word hint will be placed). Penalize empty cells - most of the table should be filled with letters.

You can use any online wordlist of at least 1000 words. For example: Wordlist from spreadthewordlist.com

You will have to format the wordlist so it can be imported into XPress. You may split the wordlist into several lists containing words with equal length, if that helps.

The program should output a filled out crossword, with empty cells marked by some character other than the 26 characters of english.

Example input: width=23, height=23

Example output:

Hint: Generating random numbers in XPress . For example, if your wordlist contains 30000 words, then i:=integer(round((30000*random)+0.5)) generates an index somewhere between 1 and 30000. Then wordlist(i) returns a random word.

III./2. Homework choice 2: Chess

CHOSEN BY TEAM SEBASTIAN, RASHEED AND LASZLO

Parameters: Number of knights ($k$), number of bishops ($b$), number of rooks ($r$), number of queens ($q$). Your task is to fit the given number of pieces onto a chessboard such that no piece is under attack by any other piece. If the problem is infeasible, the code should print out infeasible.

The program should print out an 8x8 chessboard, with empty locations marked by O, knight locations marked by K, bishop locations marked by B, rook locations marked by R, and queen locations marked by Q.

Example input: $k=0,b=0,r=0,q=8$

Example output:

(This is the famous "8 queens problem". You can test your solutions on this specific problem first, because there are known solutions for it.)

III./3. Homework choice 3: Time table

CHOSEN BY TEAM LINERMINDS

Your task is to set up a time table for all classes and all teachers in a middle school. Each class has some number of required lessons each week, and each teacher can teach some kind of class at certain levels. The requirements are as follows:

Class	Required lessons per week
9/a	Literature (3), Grammar (2), Spanish (3), History (2), Mathematics (3), Physics (1), Biology (2), Geography (2), Gymnastics (3), Music (1), Art (2)
9/b	Literature (3), Grammar (2), German (3), History (2), Mathematics (3), Physics (2), Biology (2), Geography (1), Gymnastics (3), Music (1), Art (2)
10/a	Literature (3), Grammar (1), Spanish (3), History (3), Mathematics (3), Physics (2), Biology (2), Geography (2), Gymnastics (3), Music (1), Art (1), Computer Science (1)
10/b	Literature (3), Grammar (1), German (3), History (3), Mathematics (4), Physics (2), Biology (2), Geography (1), Gymnastics (3), Music (1), Art (1), Computer Science (1)
11/a	Literature (3), Spanish (4), History (3), Mathematics (3), Physics (2), Biology (3), Chemistry (2), Geography (1), Gymnastics (3), Music (1), Art (1), Computer Science (1)
11/b	Literature (3), German (4), History (3), Mathematics (4), Physics (2), Biology (2), Chemistry (2), Geography (1), Gymnastics (3), Music (1), Art (1), Computer Science (1)
12/a	Literature (3), Spanish (4), History (3), Mathematics (4), Physics (2), Biology (2), Chemistry (3), Geography (1), Gymnastics (2), Music (1), Art (1), Computer Science (1)
12/b	Literature (3), German (4), History (3), Mathematics (4), Physics (3), Biology (2), Chemistry (2), Geography (1), Gymnastics (2), Music (1), Art (1), Computer Science (1)

The available teachers are as follows:

Teacher	Proficiency (for grades)
Alan Smith	History (9-12)
Bertha Mayer	German (9-12), Art (9-10)
Cecil Greenwell	Biology (9-10), Chemistry (11-12)
Doris Sheerly	Literature (9-12), Grammar (9-10)
Emanuel Harris	Gymnastics (9-12)
Francis Hill	Music (9-12)
Giselle Turner	Mathematics (9-11), Physics (11-12)
Harry Griffin	Geography (9-12)
Irene Sholtz	Biology (11-12), Physics (9-10)
Juan Lopez	Spanish (9-12)
Keith Clark	Mathematics (11-12), Physics (11-12)
Marilyn Prinston	Literature (11-12), Grammar (9-10), Art (11-12)
Nathan Roth	Literature (9-10), History (11-12)
Olivia Stephens	Biology (9-12)
Peter Williams	Mathematics (12), Computer Science (9-12)
Rachel Adams	Gymnastics (9-12)
Samuel Machiston	Art (9-12)

Additional requirements:

Each class has to have at least 4 and at most 6 lessons every weekday (Mon-Fri).
Classes cannot have an hour off between lectures.
The lunch time also has to be optimized. Lunch can happen either between lectures 4-5, lectures 5-6, or right after lecture 6. Classes who do not have a 6th lecture cannot have lunch after lecture 6. Moreover, the cafeteria has a maximum capacity of 4 classes.
Gymnastics class cannot occur right after lunch.
If there is no feasible solution, then remove a constraint and solve it until there is a feasible solution. Optionally hire 1 additional teacher if necessary. (In reality, these sort of changes would be discussed with the middle school.)

Optional requirements (try to fulfil as many as possible!):

Each teacher should have as many days off as possible (where they don't have any lectures).
Each teacher and each class shouldn't walk that far from their previous classroom.
Fridays should have the least amount of lectures.

Additionally, a classroom has to be specified for each lecture. The layout of the middle school is as follows:

Classroom requirements:

The rooms where lectures can be given: Any of the 6 Classrooms, Art, Computer Science, Geography, Physics, Chemistry, Biology, Gymnastics 1 & 2.
Any classroom listed in the previous point except for the Computer Science room can be used for the following "generic" lectures: Literature, Grammar, Spanish, German, History, Mathematics, Music.
The following lectures can only be taught in their specific room: Art, Computer Science, Geography, Physics, Chemistry, Biology, Gymnastics.

Output:

A time table for each class (9/a-12/b), showing what lecture will be on what day at what time with which teacher in which room.
A time table for each teacher, showing what they will teach to which class on what day at what time in which room.
A time table for each room, showing when and what classes will be taught in it.

III./4. Homework choice 4: Shape finding

CHOSEN BY TEAM MEHSHAN AND ZAIN

Parameters: Number of sides ($s$), area ($a$), boundary size ($b$). Your task is to find a shape that is fully inside $[0,1]^2$ with the desired number of sides (=vertices) ($\ge 3$), desired area ($\le 1$), and boundary size!

The area of a shape given by its sequence of vertices can be calculated with the absolute value of the "Shoelace formula"!
Make sure it is a single shape, not a union of multiple shapes!
Make sure its edges don't cross each other! (Each pair of line segments should be at least a given $\varepsilon > 0$ distance away from each other.)
No 3 consecutive vertices should be collinear! (The middle point of the 3 should be at least a given $\varepsilon > 0$ distance away from the line connecting the first and the third point.)
Optinally set the first vertex to $(0,0)$ for a more consistent output!

Bonus points if you can write an application in another programming language that takes the output of XPress, and draws out the shape! Otherwise simply print out the coordinates of each of the vertices, along with the obtained area and boundary size!

Example input: $s=5,a=0.125,b=3.5$

Example output:

III./5. Homework choice 5: Neural Network

Your task is to train a Neural Network on the MNIST Database of handwritten digits using LP / IP / MILP / NLP! Requirements:

The Neural Network should contain exactly one input layer, one hidden layer and one output layer.
Split the data into a train, validation and test sets! The Neural Network may only learn on the train set. You can validate your results while tuning the Network on the validation set. During the presentation, you'll have to use a random digit from the test set!
Convert the data into matrices or flattened vectors that Mosel can read! (You'll probably want to use a different programming language to do the conversion automatically.)
The outputs should be probabilities of how likely the program thinks it sees a given digit. These probabilities should sum to 1.
Predefine some activation functions for the hidden layer and the output layer. (You don't have to optimize for these.)
Set up two decision variable matrices with $A \in \mathbb{R}^{? \times 28^2}, B \in \mathbb{R}^{10 \times ?}$ values. Remember that forward propagation between two layers can be described with a single matrix multiplication!
Predefine some error function to test if the calculated outputs are close to the actual outputs. Minimize this error function.
The output should be the calculated weights. Make another program that does a single forward propagation step through the Neural Network with an arbitrary input, and prints out the probabilities and which digit it thinks the input was! (=The maximum probability digit.)

Optionally:

You may want to use minibatches. You can define and alter the basis solution by presenting more and more data to the model.
Print out which digits XPress found the most difficult to recognize.
Print out an accuracy score on the validation set and compare it to known results!

III./6. Homework choice 6: Pipe game

Parameters: Board size, and the whole board.

Your task is to find a solution to the "Pipe game" for any arbitrary input. The Pipe game is an $n \times m$ board of pipe pieces. Each pipe piece can be straight or curved, with a total of 6 possibilities:

A straight pipe going from left to right.
A straight pipe going from up to down.
A curved pipe going from left to down.
A curved pipe going from down to right.
A curved pipe going from right to up.
A curved pipe going from up to left.

Water is going to be poured through the pipes, from the upper left pipe to the lower right pipe. Your task is to find the minimum number of rotations for the pipes such that the water can freely flow from the upper left to the lower right pipe - the pipe system has to be connected.

Example input:

Example output:

We only had to make 4 rotations in the above case, which is the minimum number required.

Additional requirements:

The upper left and lower right pipe can be rotated in any direction, they do not have to face left/right.
The exercise can be infeasible (example: only straight pipes). The program should write out something like "There is no solution." if it is infeasible.
Try to draw out the solution with ASCII art or create another program that can take the solution from XPress and draw out the pipes. Bonus: Mark which pipes were rotated.

Example data (100 random examples, the first one is the one drawn above):

Download the pipes.dat Data file from here

Hints:

Create variables after reading in the data. It is useful to create separate variables for straight and curved pipes.
Create variables for whether or not a pipe is wet. By default, the top left pipe is wet. Any pipe touching another wet pipe rotated correctly is also wet. If the bottom right pipe is wet, the condition of the Pipe Game is met.
You will likely need the modulo function mod.

III./7. Homework choice 7: Metro lines

HOMEWORK CHOSEN BY TEAM FERENC AND KINGA

Parameters: Station map, travel demands, number of metro lines ($N$), maximum turn degree ($t$), maximum number of stops ($S$), cost per km of rail constructed ($c$), ticket price ($p$), profit return years ($y$).

Your task is to plan out $N$ new metro lines in a city (that currently has no metro lines)! The map of the stations is given with elements (name, latitude, longitude). Additionally, a travel demand list is given of passengers wanting to go from point A to point B. This list has elements (name A, latitude A, longitude A, name B, latitude B, longitude B). Note that the names of each station may not be unique.

Additionally, due to mechanical constraints, the metro line cannot curve by more than $t°$ between each station. (Common $t°$ values are $10°, 20°, \dots, 60°$.) Moreover, we would like to avoid extremely long metro lines, so there is a limit ($S$) on the number of stops each line could have. (Common $S$ values are $20, 25, 30$.)

Two example datasets are given, but feel free to construct your own! These are the actual names and coordinates of the greater London and greater Paris metropolitan area stations:

Download the london.dat Data file from here.
Download the paris.dat Data file from here.

For example, the "London St-Pancras" station is located at the coordinates (51.5319,-0.1264).

For both datasets, a travel demands list is also given:

Download the london_travel.dat Data file from here.
Download the paris_travel.dat Data file from here.

For example, the first passenger in London wants to travel from "Watton-At-Stone" located at coordinates (51.8572,-0.1195) to "Rickmansworth" located at coordinates (51.6404,-0.473).

If you are unsure how to read in data of arbitrary size, download this example.

Additional requirements:

Pre-calculate the distance matrix and use it when necessary!
Note that the distances are given in latitudes-longitudes! There are approximately 111 kilometers in 1 latitude or 1 longitude.
Add a cost for building a metro line! The cost of building a section of a line should be proportional to its length ($c$ times its length)! (Typical values of $c$ are in the range 600 million to 2.5 billion Euros per km.)
A statistics calculation shows that in a month, about 100 thousand times as many passengers will use any given line as in the travel demand data. Each ticket costs $p$ Euros. The metro line company wants to make a profit in $y$ years. So any rail line that isn't expected to make a profit shouldn't be built.
It is possible to transfer between metro lines. When transferring, a new ticket has to be used.
The results should print out the exact stations (with coordinates) that each metro line goes through.
Optionally, make another program in a different programming language that takes the output of the XPress code and draws out each metro line!

Example input (map of the greater London metropolitan area, $N=6, t=60, S=30$):

Example output:

III./8. Homework choice 8: Sphere packing

Parameters: Is the large shape a sphere or a box ($p\in\{\text{S},\text{B}\}$), radius of the large sphere ($R$), sidelengths of the large box ($a,b,c$), number of small spheres to pack ($n$), radiuses of $n$ small spheres ($r_1,\dots,r_n$)

Your task is to pack $n$ spheres of radius $r_1,\dots,r_n$ into a larger shape which could either be a sphere of radius $R$ or a box of sidelengths $a,b,c$ (the user decides which one to choose).

The packed spheres cannot intersect, but they can touch each other or the sides of the larger shape.
The problem should be encoded in a single program, not 2 separate programs.
If the problem is infeasible for the current sizes of $R$ or $a,b,c$, then the program should print out infeasible.
Optionally, if the problem is infeasible, the program should find the smallest factor $k$ that the problem is feasible for a sphere of radius $kR$ or a box of sidelengths $ka,kb,kc$.
Optionally, make another program in a different programming language that takes the output of the XPress code and shows a 3D image of the output. To make it even nicer, you can make it rotatable (alternatively take a picture from multiple angles).

Example data (you may use these to test your program - the data is scaled so that the interesting case occurs around $R\approx 1$ or around $a\approx b\approx c\approx 1$):

Download the sphere_packing.dat Data file from here.

If you are unsure how to read in data of arbitrary size, download this example.

Example input: $p=\text{B},R=1,a=1,b=1,c=1,n=200$, and $r_1,\dots,r_n$ are given.

Example output:

III./9. Homework choice 9: Domino

CHOSEN BY TEAM DE CODERS

Parameters: $a,b\in\mathbb{N}^+$ shape of the board, $S$ set of dominos.

Your task is to fit the given dominos into the board. If it cannot be fit into the area, the program should print out "infeasible". For example we have 6 dominos (2 red, 1 yellow, 1 blue and 2 green) and a given board of size $a=4,b=4$. In this case, there are multiple solutions, and this is one of them:

Each domino can be rotated by any multiple of 90°, or flipped over (giving the domino of the opposite chirality), for a total of potentially 8 orientations (sometimes only 4, 2 or 1).
The whole board does not have to be covered, we simply require all dominos to fit into the area.
Two dominos cannot overlap.
Part of a domino may not stick out of the board.
Optionally: Write a program in a different programming language that takes the output of the XPress code and draws out the solution!

Each domino can be thought of as a binary matrix. For example the yellow domino in the above example may be encoded as: $$Y = \begin{bmatrix}1 & 1 & 1 \\ 0 & 1 & 0\end{bmatrix}$$ Solve the problem for the following 2 cases (both for an $8\times 8$ and a $4\times 16$ board). (Both problems do have a solution!):

Also attempt to solve the problem for the case of a $2\times 32$ board! (It obviously wouldn't have a solution, for example, the green pieces won't fit, so the program should print out "infeasible".)

The program should be able to solve the problem for any size of board, and any input set of dominos. The user should be able to modify some part of the code to define their own dominos!

IV. Lessons so far

V. Practice book

Download the practice book from here.