MAX (X+Y) for enclose area where X, Y are positive integers but bigger or equal to 1.

W

westin

Junior Member
Joined
Sep 11, 2021
Messages
68
Hi all,

If there is an area enclose by any two linear equations( the two equations are always smaller than something like below) and the x- axis and y-axis so it forms a quadrilateral.

how do i find the max(x+y) where x and y has to be an integer and x and y has a minimum value of 1.
Is there any fast way instead of brute force as x and y can be very large?

1677285617302.png
 
Max(X+Y).png
This is a better representation of the constraints. The vertices of the feasible region are the optimal solutions to the objective functions via the Corner Point Theorem. Furthermore, since we're considering integers only, that narrows down to [imath](1,4)[/imath] and [imath](1,1)[/imath].
 
hi, i have watched this video regarding corner point theorm

However, if the vertices are not integers. how do I find the max(X+Y) integer? Like below, the max_x and max_y are (2,2) but they are not the corner points. thank you in advance for the help.

1677291551760.png
 
westin said:
hi, i have watched this video regarding corner point theorm

However, if the vertices are not integers. how do I find the max(X+Y) integer? Like below, the max_x and max_y are (2,2) but they are not the corner points. thank you in advance for the help.

View attachment 35102
Click to expand...
A few things. To add further restrictions to your inequality use {} as shown on the left.

Max(x+y)_2.png

The region where both inequalities overlap is the feasible region (the orange).
max(x+y)_3.png

The answer should be (4,1).
 
thank you the help. how about this? if all corner points are not integer, how should I find the max(x+y), should I just round down the each vertex and find the maximum value. for example,
(1,3.5) becomes (1,3)
(2.5, 2.75) becomes (2,2)
(3.67,1) becomes (3,1)
(1,1) becomes (1,1)

therefore, we can conclude that both ((2,2) and (3,1) can be the maximum(x+y)

is this assumption correct? Thanks.!

1677292993616.png
 
westin said:
thank you the help. how about this? if all corner points are not integer, how should I find the max(x+y), should I just round down the each vertex and find the maximum value. for example,
(1,3.5) becomes (1,3)
(2.5, 2.75) becomes (2,2)
(3.67,1) becomes (3,1)
(1,1) becomes (1,1)

therefore, we can conclude that both ((2,2) and (3,1) can be the maximum(x+y)

is this assumption correct? Thanks.!

View attachment 35105
Click to expand...
It doesn't work like that. (3,2) is actually the max in this case. I thought you were asking about a specific question, but it seems like you're looking for a general approach. The first 2 are Linear Programming (LP) questions, whereas the last one you are asking about is Integer Programming (IP).

For IP questions, in practice, we implement algorithms to seek optimal solutions. Here are some of them:
  1. Branch and bound algorithm
  2. Cutting plane
  3. Branch and cut
 
hi actually you are right that (3,2) is the actual max. in that case, is it ok to round up and down each X, Y coordinates provided they are within the feasible region then find the max(X+Y).

for example.

(1,3.5) becomes (1,3)
(2.5, 2.75) becomes (2,3), (2,2) and (3,2)
(3.67,1) becomes (3,1)
(1,1) becomes (1,1)

then find the max(x+y). in this case (3,2) has a max of 5. which is the most optimal integer answer. Do you think this assumption is ok and will cover the max solution?

1677295236652.png
 
westin said:
hi actually you are right that (3,2) is the actual max. in that case, is it ok to round up and down each X, Y coordinates provided they are within the feasible region then find the max(X+Y).

for example.

(1,3.5) becomes (1,3)
(2.5, 2.75) becomes (2,3), (2,2) and (3,2)
(3.67,1) becomes (3,1)
(1,1) becomes (1,1)

then find the max(x+y). in this case (3,2) has a max of 5. which is the most optimal integer answer. Do you think this assumption is ok and will cover the max solution?

View attachment 35106
Click to expand...
In my experience when seeking integers, I've always used algorithms. I think it should be ok if you check all integer solutions on the borders of the feasible region.
 
since this always form a quad with x,y>=1 and two inequalites with the form ax+by <=k (where a, b, k are positive). would this be easier? or is there a faster way in other method. I need to implement this in C++ and time complexity is key. thank you so much for the help!
 
westin said:
since this always form a quad with x,y>=1 and two inequalites with the form ax+by <=k (where a, b, k are positive). would this be easier? or is there a faster way in other method. I need to implement this in C++ and time complexity is key. thank you so much for the help!
Click to expand...
There is a handful of C++ open-source software that does this already. I suggest you look into them. The one I'm familiar with is Gurobi.
Try this.

C++: 
#include <iostream>
#include "gurobi_c++.h"

int main(int argc, char *argv[])
{
    try {
        // Create a Gurobi environment and model
        GRBEnv env = GRBEnv();
        GRBModel model = GRBModel(env);

        // Create variables x and y
        GRBVar x = model.addVar(0.0, GRB_INFINITY, 0.0, GRB_CONTINUOUS, "x");
        GRBVar y = model.addVar(0.0, GRB_INFINITY, 0.0, GRB_CONTINUOUS, "y");

        // Set objective function to maximize x + y
        GRBLinExpr obj = x + y;
        model.setObjective(obj, GRB_MAXIMIZE);

        // Add constraints 5x + 9y <= 45 and 4x + y <= 8
        model.addConstr(5*x + 9*y <= 45, "c1");
        model.addConstr(4*x + y <= 8, "c2");

        // Set variable types to integer
        x.set(GRB_INTEGER);
        y.set(GRB_INTEGER);

        // Set time limit for optimization
        model.getEnv().set(GRB_DoubleParam_TimeLimit, 30.0);

        // Use branch and cut algorithm to solve the problem
        model.optimize();

        // Print the solution
        std::cout << "Optimal objective value: " << model.get(GRB_DoubleAttr_ObjVal) << std::endl;
        std::cout << "x = " << x.get(GRB_DoubleAttr_X) << std::endl;
        std::cout << "y = " << y.get(GRB_DoubleAttr_X) << std::endl;

    } catch (GRBException e) {
        std::cerr << "Error code = " << e.getErrorCode() << std::endl;
        std::cerr << e.getMessage() << std::endl;
    } catch (...) {
        std::cerr << "Error during optimization" << std::endl;
    }

    return 0;
}
 
thank you . however, this is on coding problems that do not allow using it. I hope this corner point theorem works. you are very resourceful. thank you very much!
 
BigBeachBanana said:
It doesn't work like that. (3,2) is actually the max in this case. I thought you were asking about a specific question, but it seems like you're looking for a general approach. The first 2 are Linear Programming (LP) questions, whereas the last one you are asking about is Integer Programming (IP).

For IP questions, in practice, we implement algorithms to seek optimal solutions. Here are some of them:
  1. Branch and bound algorithm
  2. Cutting plane
  3. Branch and cut
Click to expand...
I never heard of Integer Programming before.
 
You must log in or register to reply here.
Top