Question

1. It is impossible for a linear program with unbounded feasible region to have a unique optimal solution.
True or False?

2. It is impossible for an integer program to have infinitely many optimal solutions.
True or False?

3. When we solve an integer program with a minimization objective using Branch and Bound, we can discard a subproblem for which the optimal objective value of the associated LP is larger than the objective value of the incumbent solution.
True or False?

4. If x = 1, y = 2 and x = 3, y = 6 are both optimal solutions to a bounded linear programming problem with two variables x and y, then x = 2, y = 4 must be an optimal solution to the problem.
True or False?

Answer 1

a) False. It is possible to have unique solutions optimal solutions even when the feasible region is unbounded. For eg. In the case of we need to minimize the value of the equation x+y with the constraints x>0, y>0, x+y>=6 and x-y >=2.

We can clearly see that the feasible region is unbounded. However, there exists a unique solution at x=4 and y=2.

b) False. It is possible for the integer problem to have infinitely many solutions for eg. for equations x+y >=2 and 3x+3y >= 6, we can have infinitely many solutions

c) True, since the minimization objective would be achieved for the incumbent solution and not the other LP solution.

d) True, because it lies in the same line as the optimal solution.