Integer Programming for Graph Theory and Others with Python: 04 — Array Sorting and No Objective Function
In today’s episode, we will look into Array Sorting. Integer Programming (mixed with Linear Programming) can be used to find solutions for problems such as the N-Queens game, among other combinatorial problems. The thing about some problems is that, although we are used to maximizing profit or minimizing cost, we do not need to.
No Objective Function
Let’s look at a problem where you have 3 Integer Variables. Any combination of 3 Integers can fit in those variables. When you add constraints not all sets of 3 Integers are valid anymore. At the moment you have a set of solutions (than can be more than 1, just 1 or even none, rendering the problem impossible to solve). When you add an objective function you are basically picking the best solution out of the solutions’ set you previously had.
But what if you don’t need the best solution? What if there is no “best” or “worst”? What if you just want something that fits?
This is the case for some problems, including Array Sorting.
Array Sorting
This is another problem, like the Shortest Path Problem, that can be solved either with IP or specific algorithms. In this case, there is no advantage of using IP to solve this, since (from the top of my head) I can’t imagine any slight tweak to the problem so that IP could be useful. Let’s just do this for the sake of exercising our model construction imagination:
For the sake of simplicity, we will sort an array with 4 integers ascendingly.
array = [8,2,6,1]What we need now is to decide which item corresponds to which position in the sorted array. For that, we need to create 4Integer Variables (because the Array we’re sorting has 4items) for each of the sorted array’s items. (sorry for the repeated code, it can be simplified with for-loops)
Now, the next step is to guarantee that only one position of the sorted array can be attributed to one of the items of the original array and the other way around. The next image illustrates the thought process: each row can only have one X and the same goes for each column:
Here is the code for this part:
To conclude the formulation, we need to guarantee that the 1st item of the sorted array is smaller or equal to the 2nd item, and the 2nd to the 3rd, and the 3rd to the 4th. To accomplish that, we must multiply the variables with their respective value of the original array, and sum each set of 4 and declare them as smaller or equal than the next set. You can see it clearly in the next chunk of code:
Congratulations! Here is the IP model to solve the Array Sorting Problem. If we run the solver, we can check that the following variables will have the value 1: 1_4 , 2_2 , 3_3 , 4_1. This solution means that the 4th item of the original array will have the 1st position on the sorted array, and the 2nd item of the original will have the 2nd position of the sorted, and so on.
As announced, there is no need for an objective function, since any solution is good as long as it satisfies the constraints. In this specific problem, the only case where you could have more than 1 valid solution is if you have repeated items in the original array, so it would be valid to choose either one of the identical items to assume each others’ position in the sorted array.
Next Episode: Maximum Flow Problem
Thank you once again!
