patternMinor
An integer linear program
Viewed 0 times
linearintegerprogram
Problem
I have the following problem:
Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where the only pairs $(x, y)$ that are considered for which $x$ and $y$ are positive integers and $ax + by \leq n$.
I'll be very grateful for any tips about which method could be used to solve this.
Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where the only pairs $(x, y)$ that are considered for which $x$ and $y$ are positive integers and $ax + by \leq n$.
I'll be very grateful for any tips about which method could be used to solve this.
Solution
If you google for Integer Linear Programming, you'll find that the problem is in general NP-complete. However, your subproblem with just one restriction and two variables isn't difficult to solve.
Have a look at https://en.wikipedia.org/wiki/Cutting-plane_method and especially Gomory's method: You first use the Simplex algorithm to find the optimal solution without considering that the solution should be integers. If by coincidence your optimal solution is integer, you solved the integer linear programming problem. Otherwise, you use Gomory's method to find another restriction which isn't fulfilled by the non-integer solution you found, but by every integer solution of the original problem. You solve the system with the new equation, and repeat until you have an integer solution.
Have a look at https://en.wikipedia.org/wiki/Cutting-plane_method and especially Gomory's method: You first use the Simplex algorithm to find the optimal solution without considering that the solution should be integers. If by coincidence your optimal solution is integer, you solved the integer linear programming problem. Otherwise, you use Gomory's method to find another restriction which isn't fulfilled by the non-integer solution you found, but by every integer solution of the original problem. You solve the system with the new equation, and repeat until you have an integer solution.
Context
StackExchange Computer Science Q#62627, answer score: 2
Revisions (0)
No revisions yet.