Solving a Linear Programming Problem which Requires Integer Solutions

[bagasme]

TL;DR Summary

Solving a linear programming related to quantities of plants

Hello,

In grade 11 of high school, I encountered this linear programming problem on my textbook:

Spoiler: Problem

Every six months, a decorative plants seller order Aglanonemas (A) and Sansevierias (S) to an agent, which respectively give profit of $500 and $350. The agent requires that plant A must be ordered by minimum of 20% from total plant orders. However, the seller have garden which is only sufficient for 10 As and 15 Ss. Assumed that all plants are sold out and the profit is maximized. How many As and Ss should be ordered?

The "alternative solution" described in the textbook as follows:

Let:
- $x$ : amount of plant A
- $y$ : amount of plant S
- $L$ : garden area
- $L_x$ : area of garden for one plant A
- $L_y$ : area of garden for one plant B

Since the plant order requirement is 20% of total orders are for plant A, we write: $$x \geq \frac 1 5 \left( x + y \right) \text{or } 4x - y \geq 0$$
However, the garden capacity is only for 10 A plants and 15 S plants, that is $$ x \cdot (\frac 1 {10} L) + y \cdot (\frac 1 {15} L \leq L) \text{ or } 3x + 2y \leq 30$$
The objective function is $Z = 5x + 3.5y$ (in the order of $100).

The complete linear problem equations are:
\begin{cases}
4x - y \geq 0 \\
3x + 2y \leq 30 \\
x \geq 0 \\
y \geq 0 \\
Z = 5x + 3.5y \text{ } \text{(maximize)}
\end{cases}

Solving the problem (using graphical method), the solutions are: $B(2\frac 8 {11}, 10\frac {10} {11})$ with $Z = 51.818182 \text{ or } Z = 5181.8182$. However, the correct solution requires positive integers, because the solution is about amount of goods (plants), which can't be fractional. How can I solve this problem, and would it become integer programming problem? The correct solution is 3 A plants and 10 S plants, with $5000 optimum value.

Cheers, Bagas

 

[fresh_42]

The integer values define a lattice and we can apply algorithms which operate only on this lattice. This isn't an easy subject.

In a case as above where the target function behaves smooth and locally monotone (increasing or decreasing), i.e. there are no sudden jumps, singularities or other weird behaviour, we can solve the problem with continuous variables and simply test all values of the target function at the surrounding lattice points.

 

[FactChecker]

we can solve the problem with continuous variables and simply test all values of the target function at the surrounding lattice points.

This is an integer programming problem. In this case, there is a lot of truncation of the continuous solution to get integers ($2\frac 8 {11}$ => 2 and $10\frac {10} {11}$ => 10). So, depending on the slopes of the constraints and the objective function, one might have to test integer value lattice points farther from the continuous solution.

 

[pasmith]

Summary: Solving a linear programming related to quantities of plants

Hello,

In grade 11 of high school, I encountered this linear programming problem on my textbook:

Spoiler: Problem

Every six months, a decorative plants seller order Aglanonemas (A) and Sansevierias (S) to an agent, which respectively give profit of $500 and $350. The agent requires that plant A must be ordered by minimum of 20% from total plant orders. However, the seller have garden which is only sufficient for 10 As and 15 Ss. Assumed that all plants are sold out and the profit is maximized. How many As and Ss should be ordered?

The "alternative solution" described in the textbook as follows:

Let:
- $x$ : amount of plant A
- $y$ : amount of plant S
- $L$ : garden area
- $L_x$ : area of garden for one plant A
- $L_y$ : area of garden for one plant B

Since the plant order requirement is 20% of total orders are for plant A, we write: $$x \geq \frac 1 5 \left( x + y \right) \text{or } 4x - y \geq 0$$
However, the garden capacity is only for 10 A plants and 15 S plants, that is $$ x \cdot (\frac 1 {10} L) + y \cdot (\frac 1 {15} L \leq L) \text{ or } 3x + 2y \leq 30$$
The objective function is $Z = 5x + 3.5y$ (in the order of $100).

The complete linear problem equations are:
\begin{cases}
4x - y \geq 0 \\
3x + 2y \leq 30 \\
x \geq 0 \\
y \geq 0 \\
Z = 5x + 3.5y \text{ } \text{(maximize)}
\end{cases}

Solving the problem (using graphical method), the solutions are: $B(2\frac 8 {11}, 10\frac {10} {11})$ with $Z = 51.818182 \text{ or } Z = 5181.8182$. However, the correct solution requires positive integers, because the solution is about amount of goods (plants), which can't be fractional. How can I solve this problem, and would it become integer programming problem? The correct solution is 3 A plants and 10 S plants, with $5000 optimum value.

Cheers, Bagas

(4,9) satisfies 4(4) - 9 = 7 > 0 and 3(4) + 2(9) = 30, and you've swapped a y for an x thus increasing Z by 1.5.

A bounded region of $\mathbb{R}^n$ contains only a finite number of points in $\mathbb{Z}^n$. Thus in principle maximizing a function is a question of producing a list of those points and sorting it by the value of the function. This may not be the most efficient algorithm, but it will work.

 

[FactChecker]

Thus in principle maximizing a function is a question of producing a list of those points and sorting it by the value of the function. This may not be the most efficient algorithm, but it will work.

I would not worry about a list and sorting. Just retain the best solution to date and you will be left with the best solution at the end. It works well on this sized problem and it teaches the point that integer programming is more complicated than it first appears. But this approach is quickly overwhelmed by surprisingly small problems. If the goal is to learn integer programming techniques, the "brute-force" approach misses the point.

 

[bagasme]

This is an integer programming problem. In this case, there is a lot of truncation of the continuous solution to get integers ($2\frac 8 {11}$ => 2 and $10\frac {10} {11}$ => 10). So, depending on the slopes of the constraints and the objective function, one might have to test integer value lattice points farther from the continuous solution.

But the textbook said that the correct solutions are 3 and 10 (by rounding concept).

 

[FactChecker]

But the textbook said that the correct solutions are 3 and 10 (by rounding concept).

As @pasmith pointed out, x=4, y=9 gives a better feasible solution. So the book answer is not the best. This is a good example of the difficulty with integer programming problems. If there are a few more variables (and in real applications, there are sometimes hundreds), it gets very difficult to find the optimal solution. Integer programming is a large and fascinating subject. For now, you probably should just accept the book's approach and see what is next.

 

[fresh_42]

A drawing always helps:

The blue dot is the continuous optimum, the black ones near are feasible lattice points.
And although $(3,10)$ is closer to the continuous optimum, which is always at a vertex, there is still room left to optimize $Z$ in the direction of the arrow, because $(4,9)$ is feasible, too.

If we add the restriction, that $Z$ has to be an integer value, too, then $(3,10)$ is the solution.

 

[bagasme]

As @pasmith pointed out, x=4, y=9 gives a better feasible solution. So the book answer is not the best. This is a good example of the difficulty with integer programming problems. If there are a few more variables (and in real applications, there are sometimes hundreds), it gets very difficult to find the optimal solution. Integer programming is a large and fascinating subject. For now, you probably should just accept the book's approach and see what is next.

Yet the textbook just said that we need to be careful when solving integer programming problems. Also, according to the book, rounding concept is required for integer programming.

 

[FactChecker]

Yes, you need to be careful. The rounding concept is basic for these problems, but you still need to be careful.

 

[bagasme]

Yes, you need to be careful. The rounding concept is basic for these problems, but you still need to be careful.

So what are suggestions for solving integer programming problems, that is the solutions must be integers except objective function?

 

[FactChecker]

It is a very tough subject. It might lead you far from what the book and class want you to worry about at this time. You can look at this and see if you want to study it now.

Many people, myself included, would use the clever computer programs that are available for solving them and not try to understand the details. I am not expert enough to help you further.

 

[fresh_42]

So what are suggestions for solving integer programming problems, that is the solutions must be integers except objective function?

Roughly speaking: start at a feasible lattice point and determine in which direction the objective function optimizes. Go there and repeat. This way you get a path through the lattice which should yield the optimum.

Of course this can be more complicated for higher dimensions, feasible sets which are not connected or not convex, or nonlinear objective functions, especially if they are otherwise weird. It is an entire branch of mathematics (or computer science), which algorithm works best under which conditions. The above example is extremely easy: the feasible set is a convex simplex, the objective function linear, and it is two dimensional, so it can be drawn.

 

[bagasme]

It is a very tough subject. It might lead you far from what the book and class want you to worry about at this time. You can look at this and see if you want to study it now.

Many people, myself included, would use the clever computer programs that are available for solving them and not try to understand the details. I am not expert enough to help you further.

Alright, so that integer programming is special case for linear programming, right?

 

[FactChecker]

Alright, so that integer programming is special case for linear programming, right?

It's closely related. I am not sure if linear programming is the basis of practical integer programming algorithms.

 

[fresh_42]

Alright, so that integer programming is special case for linear programming, right?

No. Integer means a discrete feasible set, linear refers to the objective function. In your case, the relevant algorithm is called simplex algorithm.

 

[bagasme]

So can we close this thread (Q.E.D)?

 

[FactChecker]

No. Integer means a discrete feasible set, linear refers to the objective function.

Linear programming requires that the objective function and the constraints be linear.

In your case, the relevant algorithm is called simplex algorithm.

The simplex algorithm is for linear programming, not directly for integer programming. It may be part of some integer linear programming algorithms, but it would need to be heavily modified.