Skip to content

Linear and integer programming

27 mayo, 2021

A good programmer intelligently combines the tools available to him to achieve his goal. Therefore, it is very important to know, even if it is “Hearsay”, the greatest number of tools that can be useful to us in the future (time will have to develop them when the time comes).

For those of you who do not know her, today I present you an authentic jewel, the linear programming and his “alter ego”, the still untamed, integer linear programming.

Linear programming

Without going into much detail or mathematical pomp, linear programming “Consists of modeling an optimization problem using only linear inequalities”. Do not panic! Is easier than it looks like.

Let’s break down the previous definition:

  • To model: It consists of transforming the problem to be solved into a set of equations or formulas that define it exactly or approximate it. For example, we can model the needle of a balance with the equation “Needle = plate1 – plate2” where Plato is the weight that each plate supports.
  • Optimization problem: They are those in which several solutions are considered and the way to choose between one or another solution is by indicating that we want to optimize some resource. For example, a car can be made fast, powerful or low consumption, however, increasing one of the three means reducing the other two (eg faster means less powerful and with more consumption).
  • Inequality: like any equation, but in addition to the identity (equality or equivalence), the relations can appear “Greater and less than”, that is, any of: =, <,>, <= and> =. For example, an inequality is 3 x <1 + yx.
  • Linear: Informally, there is a linear relationship between two elements when there is a constant that multiplied by one results in the other. Roughly we could say that they are the simplest equations that we can find. For example, the following is an example of a linear equation: 3 x + 2 y = 1 + 4z.

The fantastic thing about it is that it is not necessary to know anything else, only with these ingredients can we use all the power of linear programming.

Integer linear programming

Integer linear programming is one in which some of the unknowns can only take integer values.

Although it may seem like a small unimportant difference, it actually changes everything. While for linear programming there are algorithms that run in polynomial time, integer linear programming is NP-complete and therefore, no one has been able (nor is it believed to be possible) to find any efficient way to solve them.

In practice, there are very good algorithms that find solutions very quickly. In fact, the probably most widely used algorithm for linear programming (Danzig’s Simplex) has exponential cost (as in LPI) however in practice it gives very good results.

Modeling problems

There are problems in which applying linear programming is straightforward, since the problem itself is posed in terms of inequalities and some optimization condition. A typical example would be “Make a program that maximizes the number of garments that we can make in a factory”They would tell us how much fabric, buttons, etc … each garment needs and that’s it.

The really interesting of linear programming is that we can apply it in situations where, apparently, you need to code the typical custom algorithm.

Sum of bits (example 1)

The other day we commented on the problem of the sum of bits, which consisted in that, given a number X, it was necessary to find two other Y and Z such that, adding them to X, but at the same time the number of bits to 1 that they have is maximum. Can linear programming be applied here? Let’s see how.

Although this is obvious to any programmer, the base 10 representation of a binary number is as follows:

Y = 20 Y0 + 21 Y1 +… = ∑b twob Yb

Where each Yb is the bit b-th.

As it is about maximizing the number of bits of Y and Z it is obvious then that we have to maximize the expression:

b (Yb + zb)

Subject to a single restriction, that the sum of these two numbers must give X, that is:

b twob (Yb + zb) = X

Being, of course, binary the variables Yb Y zb.

It is much simpler than it seems. An almost literal implementation of the aforementioned would be, using Microsoft Solver Foundation:

Of course in this case it is much better to use the other solution we gave (with constant cost), but we have seen how to transform a problem.

Kata Potter (example 2)

The Kata Potter is a discount application problem. There are 5 different books in a collection, depending on the books you buy they give you more or less discount, but the books have to be different, if you buy them the same there is no discount. Thus, if you buy three books but two are the same, they would give you a discount only for two different ones, the third you pay in full.

In this case, there is a simple way to model the problem as a linear programming system. We create some variables for the books of the same type r1, r2, r4, r8 and r16. Then other variables for any pair of books r3, r5, r9, … and so on. It is enough to enumerate the bit masks from 0 to 25-1 to get all possible discount groups.

The result is that Kata Potter has a direct solution using linear programming, and it is this:

Puzzle (example 4)

Another very curious and very useful example is when we have a problem in which we must fit the resources in such a way that they do not overlap (or with limitations), with different shapes (eg Tetris pieces), with different costs (eg certain pieces). they are more expensive than others), etc …

The way to transform this type of problem is to assign a Boolean variable to each possible position of a piece. If two pieces have non-empty intersection, it means that their variables are incompatible, and they would generate a constraint like:

piece1 + piece2 <= 1

Of course, the normal thing is that the intersections are between many pieces, so the restrictions are of the form:

piece1 + piece2 +… + piece10 <= 1
piece1 + piece3 +… + piece9 <= 1
piece2 + piece4 +… + piece8 <= 1

Could you solve the following problem: “Assigned a cost to each piece of Tetris, get the cheapest way to fill a chessboard as long as it is as full as possible”. Cheer up!.

When not to use linear programming

If you want to have a highly optimized version, which is very efficient, before using the linear programming solution (especially if it is integer), you should try to take advantage of possible additional data that allows you to contextualize your problem. Perhaps you can reduce the complexity of your problem by finding strategies that allow you to develop a fast and efficient implementation.

You will spend a lot more time than with linear programming, but you will have had a great time coding.

Advantages of using linear programming

If our problem is suitable to be solved with linear programming, without a doubt one way to save many hours of coding, testing and maintaining code is to apply and use the libraries that we have at our disposal. For example, bookstores may be able to make use of GPGPU to massively parallelize the calculation of solutions.

In addition, any progress made in solving these problems will automatically lead to an improvement in our solutions.

Transforming a problem to another of linear programming is usually much easier than directly facing the initial problem, also, if our problem is in NP, the algorithms developed will give us all the efficiency that is currently available.

So now you know, if you have a difficult problem in front of you, consider using linear programming.

More information | Kata Potter.
More information | lp_solve Open Source, Microsoft Solver Foundation
More information | Wikipedia, Wolfram