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.

what is the best path?

What is the best path for the postman?

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:

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):

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.