Competition - post a photo you've taken of nature >>

Linear Programming - Integer Solutions (A Level)

Is there an easy way to find the integer solution to a linear programming problem?
It's easy when you're dealing with relatively low numbers, but if the problem deals with hundreds, you can't clearly see all the integer points on a graph, and testing them all would take ages.

(edited 3 years ago)

Reply 1

mqb2766

Original post by Zuvio

Is there an easy way to find the integer solution to a linear equation?
It's easy when you're dealing with relatively low numbers, but if the problem deals with hundreds, you can't clearly see all the integer points on a graph, and testing them all would take ages.

Can you upload a specific question?

Reply 2

Zuvio

Original post by mqb2766

Can you upload a specific question?

Maximise P = x + y
Subject to 9x + 5y < 4500
3x + y < 1200
8x + 7y < 5600
x, y > 0
(all < and > are or equal to, but. i can't type that symbol)

Reply 3

ghostwalker

Original post by Zuvio

Maximise P = x + y
Subject to 9x + 5y < 4500
3x + y < 1200
8x + 7y < 5600
x, y > 0
(all < and > are or equal to, but. i can't type that symbol)

Unless I made a slip, that can be solved as normal, and the solution is integer; (x,y) = (0,800). So, no further work required.

Reply 4

Zuvio

Original post by ghostwalker

Unless I made a slip, that can be solved as normal, and the solution is integer; (x,y) = (0,800). So, no further work required.

Ok, so i honestly just wrote out a random problem and didn't try to solve it, but what would you do with a problem like this if the solution wasn't an integer point?
e.g. you change the 3rd condition to 7x + 9 y < 5500

(edited 3 years ago)

Reply 5

ghostwalker

Original post by Zuvio

That gives a solution of (265,405)

Instead, let's try

7x +8.5y\leq 5500

Our solution now becomes (254.054, 437.838) to 3dec.pl. So, non-integer.

What do we do?

The shape of the feasible region is convex, and we can fall back on the integer part, i.e. to (254,437), as a first step.

Our objective will be maximised when x,y have one of the two forms

(x,437), where x >= 254, or (254,y) where y >= 437.

We're going to need to check both.

First part, (x,437)

We check each constraint to find what's the largest value x can be when y=437. You'd need to take the minimum of all those values and then the integer part.

Or you can simply solve the LP setting y=437, which would be far easier. And again take the integer part of the x value. To produce one possible solution.

Repeat with (254,y), in a similar fashion to get a second solution.

The greater of the two is your final solution.

Sorry, rather torturous to describe.

Reply 6

mqb2766

Not a level, but I guess the difficulties could be when the active constraint was almost parallel to the contour of the cost function. The non integer solution could occur at one end vertex, but the integer solution could occur at the other end vertex or even along the active constraint. Will try and sketch later.

Edit ...

The grid represents the integer solutions. The feasible region by the red boundary and the cost function (contour) by the blue dashed line. We want to minimise the cost, so lower values (y intercept) are better. The optimal non integer solution is (1) as it is the first point where the cost contour and the feasible region intersect. But if we slide the cost function up slightly, the first integer solution is (2), which is "far" from (1). The integer optimal solution isn't necessarily where constraints intersect either (as it will be for the non integer solution) and could occur along a single constraint.

In general, integer programming is hard (np complete), though I don't know all relevant stuff for integer linear programming. When the active constraint(s) and the cost contour are "distinctly not parallel", you should get the integer/non-integer solutions being close. In answer to your original question, it's not necessarily easy, even with a small number of variables, if the problem is ill posed (small changes to the problem produce a large change in the solution).