What are some examples of problems that are well suited for linear Integer programming?

Question

I always wrote software for solving business problems. I came across LIP while I was going through one of the SO posts. I googled it, but I can’t link how I can use it to solve business problems. Appreciate if someone can help me understand in non-specialized terms.

Answer 1

ILP can be used to solve almost any problem associated with creating multiple solutions, each of which has only a few possible results, all known in advance, and in which you can describe the overall “quality” of any combination of options using a function that is independent of “interaction” between elections. To see how this works, the easiest way is to restrict variables, which can only be 0 or 1 (the smallest useful range of integers). Now:

• Each solution requiring a yes / no response becomes a variable
• The objective function should describe the thing that we want to maximize (or minimize) as a weighted combination of these variables
• You need to find a way to express each constraint (a combination of options that cannot be done at the same time) using one or more constraints of linear equality or inequality

Example

For example, suppose you have 3 employees, Anne, Bill, and Karl, and 3 jobs, Dust, Printing, and Packaging. All people can perform all tasks, but each of them has different levels of efficiency / ability for each task, so we want to find the best task for each of them in order to maximize overall effectiveness. We want each person to do exactly 1 job.

Variables

One way to solve this problem is 9 variables, one for each combination of worker and job. The variable x_ad will be set to 1 if Anne should Dust in the optimal solution, and 0 otherwise; x_bp will get a value of 1 if Bill should pack in the optimal solution, and 0 otherwise; etc.

Objective function

The next thing to do is to formulate the objective function that we want to maximize or minimize. Suppose that based on the latest performance estimates of Anna, Bill, and Karl, we have a table of 9 numbers that says how many minutes each of them needs to complete each of the three tasks. In this case, it makes sense to take the sum of all 9 variables, each of which is multiplied by the time necessary for this particular employee to perform this specific work, and try to minimize this amount, that is, minimize the total time spent on doing all the work.

Limitations

The last step is to give constraints that ensure that (a) everyone does exactly 1 job, and (b) every job does exactly 1 man. (Note that in fact, these steps can be performed in any order.)

To make sure that Anne performs exactly 1 task, we can add the restriction x_ad + x_at + x_ap = 1. Similar restrictions can be added for Bill and Karl.

To make sure that there is exactly 1 person, we can add a constraint that is x_ad + x_bd + x_cd = 1. Similar restrictions can be added for input and packaging.

In total, there are 6 limitations. Now you can put this problem with 9-variable 6-constraints into the ILP solver, and it will return the values ​​of the variables for one of the optimal solutions - exactly 3 of them will be 1, and the rest will be 0. 3, which 1 tells you which people must do the job!

ILP is a common

As it happens, this particular problem has a special structure that allows it to be more efficiently solved using a different algorithm. The advantage of using ILP is that variations of the problem can be easily included: for example, if there really were 4 people and only 3 tasks, then we will need to hide the restrictions so that each person performs no more than one job, and not exactly 1 position . This can be expressed simply by changing the equal sign in each of the 1st 3 restrictions on the sign less or equal.

Answer 2

First read the linear programming example from Wikipedia.

Now imagine a farmer producing pigs and chickens, or a factory producing toasters and vacuum cleaners - now the outputs (and possibly restrictions) are integers, so these beautiful graphs will go crookedly step by step. This is a business application that is easily presented as a linear programming problem.

I used integer linear programming before deciding how to glue together n equally distributed images to maximize the screen space used to display these images, and formalism may present coverage problems such as planning, but integer linear programming business applications seem more natural applications .

User SO flolo says: Use cases where I have often seen this: in a digital circuit diagram, you have objects for placing / displaying on certain parts of the chip (FPGA-Placeacing) - this can be done using ILP. Also in the HW-SW code, a partition problem often arises: which part of the program should still work on the processor and which part should be accelerated at the hardware level. This can also be resolved using ILP.

Answer 3

A sample problem with ILP would look something like this:

• maximize 37 ∙ x1 + 45 ∙ x2

Where

• x1, x2, ... must be positive integers

... but there is a set of constraints in the form

• a1 ∙ x1 + b1 ∙ x2 <k1
• a2 ∙ x1 + b2 ∙ x2 <k2
• a3 ∙ x1 + b3 ∙ x2 <k3
• ...

---

Now, a simpler articulation of the Wikipedia example:

• The farmer has an area of ​​land L , which can be planted either with wheat, or barley, or a combination of the two.
• The farmer has F grams of fertilizer and P grams of insecticide.
• Each m² of wheat requires F1 grams of fertilizer and P1 grams of insecticide
• Each m² of barley requires F2 grams of fertilizer and P2 grams of insecticide

Now,

• Let a1 denote the selling price of wheat per 1 m²
• Let a2 denote the selling price of barley per 1 m²
• Let x1 denote the area of ​​land to be planted with wheat.
• Let x2 denote the area of ​​land to be planted with barley
• x1, x2 are positive integers (suppose we can set the resolution to 1 m²)

So,

• profit a1 ∙ x1 + a2 ∙ x2 - we want to maximize it
• Since the farmer has a limited land area: x1 + x2 <= L
• Since the farmer has a limited amount of fertilizer: F1 ∙ x1 + F2 ∙ x2 <F
• Since the farmer has a limited amount of insecticides: P1 ∙ x1 + P2 ∙ x2 <P

a1, a2, L, F1, F2, F, P1, P2, P - all constants (in our example: positive)

We are looking for positive integers x1, x2 , which maximize the expressed expression, given the indicated restrictions.

Hope this is understandable ...

Answer 4

ILP "on its own" can directly model many things. If you are looking for LP examples, you are likely to find many well-known cases of textbooks, such as a diet problem.

Given a set of pills, each with a vitamin content and daily vitamin quota, find the cheapest shake that matches the quota.

Many of these problems naturally have instances that require varialbe to be integers (maybe you can't split the tablets in half)

A really interesting material, however, is that in fact a large number of combinatorial problems come down to LP. One of my favorites is the assignment problem.

Given a set of N workers, N tasks and N on N matirx, describing how each employee charges for each task, determines which task to give each employee in order to minimize costs.

Most solutions that naturally arise have exponential complexity, but when using linear programming, there is a polynomial solution.

---

When it comes to ILP, ILP has the added benefit / complexity of being NP-complete. This means that it can be used to model a very wide range of problems (logical feasibility is also very popular in this regard). Since there are many good and optimized ILP lattices, it is often possible to translate an NP-complete problem there into ILP instead of developing your own algorithm yourself.

Answer 5

You can easily apply a linear program wherever you want to optimize, and the objective function is linear. You can make schedules (I mean large, like train companies that need to optimize the use of vehicles and tracks), production (optimize winnings), almost everything. It is sometimes difficult to formulate your problem as IP and / or sometimes you are faced with a problem that is your solution, which you must produce, for example. 0.345 car for optimal victory. This, of course, is impossible, and therefore you limit even more: your variable for the number of cars must be integer. Even when it now sounds easier (because you have endless choices for your variable), it's actually more complicated. At this point, he gets NP-hard. Which actually means that you can solve ANY problem from your computer using ILP, you just need to convert it.

For you, I would recommend an introduction to reading some basic (I) LP files. From my point of view, I don’t know a single good website (but if you understand, you will find it), I can recommend linear programming from Chvatal as a book. It has very good examples and also describes real-world use cases.

Answer 6

The other answers here have great examples. Two of the gold standards for using integer programming and more general operations research are

• Interfaces magazine published by INFORMS (Institute for Operations Research and Management Sciences)
• Winners of the Franz Edelman Award for Excellence in Operations Research and Management Sciences.

Interfaces publish research that uses operations research that is applicable to real-world issues, and the Edelman Award is a highly competitive award for the business use of operations research methods.