Thread: Matching problem View Single Post
2021-06-02, 21:24   #8
Walter

"Walter S. Gisler"
Sep 2020
Switzerland

1110 Posts

Quote:
 Originally Posted by Viliam Furik I am looking at the code, but I still can't get how the heck does it decide what's best to continue with... How do the constraints work and how do they affect the next "prediction"?
Viliam, not sure if you are familiar with linear programming/ constraint programming, but it might be a bit confusing at first and requires a slightly different way of thinking. This is certainly not the easiest example to get started with.

The whole idea behind my approach is to describe the correct solution in terms of the knowledge we gain in every step. The knowledge you gain in one single step isn't valuable by itself, but the knowledge you gain in multiple steps combined, tells you a lot about the solution. Think of it as ruling out solutions, rather than moving towards a better solution at every step. At the beginning, the possible solution space is $n!$. With every iteration and every constraint that we add, we cut off some of the solutions and therefore reduce the solution space, until we are left with only one single unique solution.

Let's look at a much easier example with n=3; let's assume the correct solution is [1, 2, 3]

If our first guess is [3,1,2], the number of correct guesses is 0.

Based on this, we can not only rule out [3,1,2], but also [3,2,1], [1,3,2] and [2,3,1] (because each of them has one position in common with a solution we know is completely wrong), and that's exactly what adding that constraint would do.

About choosing the next solution: as I said, all that the constraints do is to reduce the solution space from $n!$ to a smaller number of solutions. So after adding a constraint, we just let the MIP solver chose one of the remaining solutions in the solution space at random. The whole idea isn't necessarily to chose a better solution in every iteration, so "predict the next solution" isn't quite the right wording.

A common problem that is solved with a binary integer program is Sudoku. It is certainly much easier to understand than this. If you are curious about the method I am using here, this would probably be a good starting point: https://www.mathworks.com/help/optim...lem-based.html