An integer linear program

Question

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.

• D.W.: 1. What's the source for this problem? It's good practice to always attribute your sources and give credit to where you got this from. Is this from a live coding contest? 2. Are you taking a class? What material do you know that might be relevant? I know of multiple possible approaches, at different levels of mathematical and algorithmic sophistication; giving us some information about what you already know will help us tailor answers to your level of understanding.
• D.W.: 3. What approaches have you already considered? What's the best algorithm you've come up with so far? This site works best when you show us what progress you've already made, rather than copying the problem statement and expecting us to hand you a solution on a platter. You mentioned integer linear programming. Have you tried using an off-the-shelf ILP solver? 4. The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
• Raphael: The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
• Raphael: @RodrigoDeAzevedo Thanks for the edit, but how is this title any better?
• Rodrigo de Azevedo: @Raphael "Integer Linear Programming" (ILP) was the previous title. ILP is a problem, whereas the question is on an instance of ILP. I think the difference is stark.

Answer 1

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.