3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Aug 15, 2016 at 21:30
  • 2
    $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    Commented Aug 15, 2016 at 21:30
  • 2
    $\begingroup$ 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! $\endgroup$
    – Raphael
    Commented Aug 15, 2016 at 22:17
  • $\begingroup$ @RodrigoDeAzevedo Thanks for the edit, but how is this title any better? $\endgroup$
    – Raphael
    Commented Oct 17, 2016 at 12:47
  • $\begingroup$ @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. $\endgroup$
    – Rodrigo de Azevedo
    Commented Oct 17, 2016 at 12:52

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.