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)
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.
no, i have equation like : Ax + By and I want to maximise above with following constraints : X + Y < 10^5
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.
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.
i just have a linear equation of type :
Ax + By (which i want to maximise ) with simple constraint of : x + y <= 10^5
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.
Integer programming is NP-Hard.
http://en.wikipedia.org/wiki/Integer_programming
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
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.
Integer linear programming is NP-Hard (there is no known method that solve it in polynomial time).
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.