Riki's Desi

Introduction to optimization problems

There are a lot of real-life problems that are very difficult to solve without the help of a well programmed computer. Many of those problems have a combinatorial essence. Combinatorial means that, to solve the problem, we have to associate to a discrete set of elements an other set of elements, whatever they represent. The absolute best solution for many of this non trivial problems cannot be found in a reasonable amount of time, because the only way to find the best solution is to try all the possible combinations. It is easy to guess that even for apparently simple problems, the size of the space where one has to find the solution grows exponentially.

Nevertheless optimization problems are very important in the today's society. Let's make a concrete example: a postman has to deliver some letters. What is the least expensive path that he has to follow to deliver them all? There is no simple answer. One can think a little bit about the path, and build a reasonable solution to the problem, but there is no way to say, in general, if this solution is the best without trying them all. But wait... can a computer solve the problem better than a person? Yes! It can try many more paths than a single human being...

How to find a good solution?

We have to say to the computer in some way what a good solution is for us. Remember that the computer understands only number and relations between abstract objects. So we have to define a function of our trial solution that calculate a number. This number is the score of the trial solution. That is: given a trial solution of our very complicated problem, we have to calculate a number that says how much this trial solution is good. The computer then, generating many trial solutions, will find the one with the lowest score.

In the case of the postman, the cost function is very simple: the number of kilometers that he do to deliver all the post. In general, the cost function can be a very complicated function, with many parameters. The human being that wants to solve the problem with a computer has to tell all the parameters, to teach the computer what it has to do.

In general to solve an optimization problem with a computer we need:

• a model of all our possible solutions
• a function that given a particular trial solution calculates the cost of the solution (a number)
• an algorithm to generate possible solutions
• all the parameters of the function (user dependent)

Given a problem, I can write a program for you that solves it. But you, final user, have to say to the computer what do you want: you have to find the parameters that you like more. Those can be found thinking a little and doing some experiments. After you found them, you don't have to change anything more. And finding some sets of good parameters is a lot simpler than finding a good solution to your problem.

The referees and the matches problem

This one, I think it is terrible. Good referees have to do difficult matches. You have to pay for every kilometer. You want that all the referees have more or less the same number of matches. You want that a referee do not see always the same team. Referees can travel in pairs. Not all referees can do all the championships. Some referees do not like each other. You don't want matches without a referee. ... There are tons of constraints and minimization task.

I wrote a program that do all this for you, and outputs the best result that it found with a simple analysis of the solution, given the constraints.

Riki's FinalRef

The program, written in C++ and python, consists in two main parts: a solver and a web interface that run on a server. No installation procedure is required. The web interface has a browser interface, and a REST API interface. An example python REST client is provided. Both the browser interface and the REST API provides the same functionality. Input and outputs are simple CVS and json files. The user can have some fun in creating his own parameters or he can chose between a sets of predefined ones. The program takes in account the following facts (more can be added):

• number of refs in a match
• distance in days between matches of the same ref
• equal distribution of the number of matches to the refs
• distance in days between matches with the same team for the same ref
• refs pairs/triplets/... that have preferably matches together
• refs that hate each other
• teams and refs that are not compatible (for whatever reason)
• every ref is allowed to have matches only in a subset of all the championships
• total kilometers (with eventual intermediate meeting point that is calculated)
• good refs have difficult matches
• refs unavailability and availability
• manually entered assignments (those are always satisfied)

I stress that it is not guarantee that if you add a new constraint, it will be satisfied. Often it is not possible. That's why every constraint has an associated penalty score. The program will look for a solution with a low enough penalty score. The program shows a report of what went not so good and what went very bad at the end of the calculation. If something went very bad, maybe some constraint should be relaxed. Typical run times are few minutes.