Lately I have been using linear programming, for work. Linear programs differ much from procedural programming. They are a way of stating an optimisation problem in a very effective way.
A linear program consist of variables, a target function, and constraints. Both the target function and the constraints are expressed in terms of variables. The target function is the expression which you aim to maximise or minimise in line of the constraints you specified.
It is not called linear by chance, both the target function and the constraints have to be linear i.e. of the form \(a + b * x <=> c\) where \(a,b\) and \(c\) are constants. Here we only have one variable \(x\) but you can have as many as your solver can handle. The variable can be of several types. It can be an integer, a boolean (restriction on integer with only values 0 and 1), or a real number. Restricting the variable to a boolean enables to describe optimisation problems which can involve mappings.
Lets say we want to map the elements of two sets \(A\) and \(B\). That both sets and all the combinations of elements are enough so we need a computer but not enough for all the combinations to be too many to enumerate in practice. We also assume that we can calculate the cost of a given mapping. That is that the cost \(c_11\) of \(a_1\) being mapped to \(b_1\) is computable in practice. We can then define a target function as the sum of the costs of the active mappings \(target =\sum_i,j m_{ij}*c_{ij}\). The variable \(m_{ij}\) is 0 if \(a_i\) and \(b_j\) are mapped. We can then specify as constraints any other rules that we may want. At one stage the constraints may become constraints about the mappings themselves. We can very simply imaging that the costs are altered if two elements are mapped.
For the sake of the argument lets say that we want to decrease the cost by a constant \(z\) if \(a_1\) is mapped to \(b_1\) and \(a_2\) is mapped to \(b_2\). That is modifying the target function to be \(target =\sum_{i,j} m_{ij}*c_{ij} - m_{11} * m_{22} *z\) This last statement would all be fine if you could multiply the two variables \(m_{11}\) and \(m_{22}\). You need for both mappings to exist i.e. be 1 in order for \(z\) to be subtracted from the target function. The thing with linear programs is that you can not multiply two variables, the problem definition would then cease to be linear. We would not be able to solve the mapping with the same techniques.
Here we are then truly stuck. We can not perform an and. We can not multiply the two boolean variables, which is another way of saying the same. But no, there is a way of doing it.
What we need is a set of constraints that hold emulating the truth table of an and. That is given three variables \(a\), \(b\) and \(c\). We want \(c\) to be equal 1 only when both \(a\) and \(b\) are 1 and 0 otherwise. Bear in mind that the variables can only take one of two values 0 or 1. And that the value that the variable takes has always to be the maximal if we maximise, or the minimal otherwise.
We will present here the method if we are maximising.
Since all the constraints have to hold, the trick is to first find a constraint that will give us the result we want. That is when both variables are 1 the result is also worth 1 $a + b <= 1 +c $ is such a constraint. Pretty but there is a but. The problem is now that for all other cases of either \(a\), \(b\) or both being 0 the constraint also holds for \(c\) being 1. Which is not what we want. OK, not a cool thing, but we can define other constraints which will prevent those cases from occurring.
This can be done with the help of the two following constraints. \(c < = a\) and \(c < = b\). This means that when \(a\) or \(b\) are 0 \(c\) has to be 1. Technically the constrains as stated hold for \(a = 0, c = 0\) but since we are maximising \(c\) is forced to take the value 1, in such scenario. (NOTE: To better understand this last point look at the subtle role that the free variables play in the SIMPLEX algorithm.) If we then combine all the constraints we have:
| $a + b < = 1 +c $ |
| \(c < = a\) |
| \(c < = b\) |
Which hold for the following values of \(a\), \(b\), and \(c\)
| \(a = 0, b = 0, c = 0\) |
| \(a = 1, b = 0, c = 0\) |
| \(a = 0, b = 1, c = 0\) |
| \(a = 1, b = 1, c = 1\) |
But not for:
| $a = 0, b = 0, c = 1$ |
| $a = 1, b = 0, c = 1$ |
| $a = 0, b = 1, c = 1$ |
| $a = 1, b = 1, c = 0$ |
Which is exactly how the truth table of an and looks like. So we have found a way to emulate an and, which is the multiplication of two boolean variables in a linear program.
Impossible is just another word, for look-around.
No comments:
Post a Comment