8.8. Challenges with Integer Linear Programming

So, we done simplex and we find the solution, so are we done, so turns out that we might with an answer which is not something that we can actually used. For instance, we might it an answer will says h 3 is equal to 10.6. So, this is the, we must hire a fractional number of people in a month. Now, obviously, we cannot do this at the same time we have not any of our constraints express that the values must be integers.

After applying the simplex method to solve the linear programming problem, we may arrive at a solution where some variables, such as the number of workers to hire, come out as fractional numbers (like 10.6 workers). This poses a challenge because it's impractical to hire a fraction of a worker; you cannot hire 10.6 workers. The constraints in the original problem require whole (integer) numbers, so this might invalidate the solution.

Imagine trying to bake cookies. If the recipe calls for 2.5 cups of flour, you have a problem because you can't use half a cup in a meaningful way if you're measuring with standard containers. Instead, you need to round it up or down to a whole number like 2 or 3 cups, which may lead to either too few or too many cookies.

So, what can be do about this, well we can take this 10.6 and we can look for the errors integer 10 or a 11 and reevaluate what happens to the cost, if we make it even integer. So, this is called integer rounding, now if the values are big now direct 10, 11 the two digit value say, then rounding is relatively small displacement and the quality of the optimum will not change must based on it is. But, if the numbers are small, if I am rounding between say I am going to take it from 0.51 hour 0 of 1.52 or 1 then the effect of the rounding is quite can be quite task.

To address the problem of fractional solutions, we can use a technique called integer rounding. This involves taking the fractional number (like 10.6) and adjusting it to the nearest whole number (either 10 or 11) to see how it would affect our costs. If the original numbers are large, rounding might not significantly affect the outcome. However, if the numbers are small, even a small rounding difference can lead to substantial changes in the results, potentially making the solution impractical.

Consider measuring ingredients for a recipe again. If you need 1.5 cups of sugar and decide to round down to 1 cup, you might end up with cookies that lack sweetness. Conversely, rounding up to 2 cups could lead to overly sweet cookies. This example shows how small changes in ingredient amounts can significantly affect the final product.

So, this is the general problem with linear programming which is linear programming cannot guarantee that you have the integer solutions, when you want an integer solution you can use rounding to achieve an integer solution, but you have to be careful that the rounding actually gives you one optimum. Now, why not just insist that you want an integer solution. So, can you not set up this same problem and solve it, but require the solutions to be integers, unfortunately this terms out to be quite a hard probe.

Linear programming inherently does not ensure that all solutions are integers. While rounding can be applied to create integer solutions from fractional results, this must be done carefully to ensure that we still achieve an optimal solution. A more challenging aspect arises when attempting to directly solve a problem with integer requirements; this is known as integer linear programming. Unlike standard linear programming, integer linear programming is significantly more complex and lacks efficient solving methods that guarantee optimality in polynomial time.

Imagine you're trying to organize seats for a concert. You can’t have a fraction of a seat; every seat must be whole. If your calculations suggest you need 200.5 seats, you must decide to use either 200 or 201, causing potential issues with seating arrangements. Trying to find the most efficient seating arrangement that exactly fits the whole seats without gaps or overlaps is the real challenge, similar to how integer linear programming works.

So, we have found we have claim rather that when we set up general linear programming problem, we can solve them efficiently. So, simplex is not an efficient solution, but an effective solution, but there are interior point methods and other polynomial time algorithms for linear programming. But, if you change the rules of the game and say I do not want to arbitrary solution; that means, constraints, but I want to one we are all the values that I get an integers, then we have the, so call integer linear programming. And integer linear programming unfortunately is not solvable efficiently or it is not known divisible efficiently.

Standard linear programming problems can be solved efficiently using methods like the simplex algorithm or interior point methods. However, when the requirements are altered to obtain integer solutions (integer linear programming), the process becomes much more difficult. Currently, no known efficient algorithms can guarantee a solution for all integer linear programming problems in a polynomial timeframe, making it a complicated field of study.

Think of building a custom bookshelf. If you want to split 7 shelves into sections where each section must hold an integer number of books, it becomes a complex problem of figuring out how to fit an exact number of whole books (integer solutions) rather than fractions, which makes planning and construction tricky. You wouldn't want to design a shelf that could hold 7.3 books—every shelf must hold a whole number of books.

--