ron2794's blog

By ron2794, 11 years ago, In English

i have a simple equation of two variables say x and y such that x + y < 10^5 (this is a sort of constraint that i must obey). x and y can take only integer values.

now all i want to do is to maximise the equation consisting of these two variables x and y.

SO I have an equation like :

Ax + By (which i want to maxmise)

with constraints : x + y <= 10^5

where x,y can take only integer values

I googled a bit and this seems to be the case of integer linear programming which they say that is easier as compared to linear programming.

I am not able to figure out the algorithm that i need to know to maximise the equation efficiently. A simple brute force is not at all desirable to me, so I need something cool.

can you help me in figuring out the algorithm that i need to learn.(a brief explanation would be appreciated)

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ok, question could be a little clearer. :)

You probably have an inequality like a * x + b * y < 10^5. This can be solved like linear diophantine equation, however I have once written a very straight forward algorithm (it solved the task, but I did not even try to prove it) with limitations close to yours (<10^5).

If you are not interested in non-proven simplicity read more abount diophantine equations and procedures for solving them (inequalities can be solved alike).

Sorry if I've missed the point.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no, i have equation like : Ax + By and I want to maximise above with following constraints : X + Y < 10^5

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      If A and B are both positive ( which I suspect is the case ) then the answer is simply max(A,B) * 10^5, otherwise the answer is unbounded.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The algorithm will depend on the type of equations you have. If all your equations are linear, you can apply simplex method. http://en.wikipedia.org/wiki/Simplex_algorithm (In order to handle maximum, you can multiply your Minimize statement by (-1) and solve the same problem).

I'm not very familiar with the methods used for arbitrary equations, you can try to google non-linear optimization.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i just have a linear equation of type :

    Ax + By (which i want to maximise ) with simple constraint of : x + y <= 10^5

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 16   Vote: I like it 0 Vote: I do not like it

      Ok,sorry. In case you have only two variables we can try to solve it geometrically. Create one line for y=10^5-x. AX+BY can be viewed as a family of lines Y=(Z-AX)/B with the same slope -A/B. You need to find the highest Z such that the triangle formed by lines X=0, Y=0 and Y=10^5-X has a non-empty intersection with Y=(Z-AX)/B, such that the line has at least one point with integer coordinates inside the triangle.

      A simple O(max(X,Y)) way to do it would be to iterate over Z and check the condition above is satisfied. The first (initial value of Z) can be found as a minimum over Z for three lines each of which intersects a vertex from triangle formed by X=0, Y=0 and y=10^5-x.

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can search how to solve linear Diophantine Equation with Extended Euclid Algorithm. Solving this Equation you will get a Parametric equation of A and B. then you can apply either Binary search or any search on A or B ,to get the maximum value for the equation. You can learn How to find solutions of linear Diophantine ax + by = c. In the link below: Link Here

»
9 years ago, # |
  Vote: I like it -20 Vote: I do not like it

when you are saying x + y < 10^5 that mean x + y = 10^5 — 1 is maximum right. now iterate through loop and try it on x and find y then swap them and store maximum value of Ax + By.

code will be look like.

loop i from 1 to 10^5 — 2 : x = i y = (10^5 — 1) — i ans = max(ans, max(Ax + By, Ay + Bx)) correct me if i misunderstood your problem.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Integer linear programming is NP-Hard (there is no known method that solve it in polynomial time).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I assume x >= 0 && y >= 0. If not, and either A or B is negative, then the answer can be infinity.

Since x + y <= 10^5, why not try out all possible x + y values from 1 to 10^5. Say s = x + y and we iterate s from 1 to 10^5. y = s — x. Substitute that in the objective function:

Maximize Ax + B(s — x) = Maximize (A — B)x + Bs such that x <= s. Since x is the only variable here, you can easily determine the max value subject to x <= s && x >= 0. If (A — B) > 0, then x = s, else x = 0.