IP bank

Question 1

elaborate on how we can model a non convex feasible region

Answer 1

The thing about non convex regions is that we cannot formulate a feasible region that is “either in this or in this etc” using regular LP. However, with IP, we can.

WE think of as “either we force set A of constraints to hold, or set B to hold”. We can also generalize it further.

The typical to do this is to add M(1-indicatorVariable) to the constraints. In the case where we have only two regions, this is fine.
the indicator variable will be set to choose one of them.

If we have many regions, where one of them must be chosen, we can do this:
for each region, we have an indicator variable.
Then we have a constraint that say that the sum of hte indicator variables MUST be equal to 1. This force one set of constraints to apply.

Question 2

elaborate on how we can model a non convex function using IP

Answer 2

Assume it is piecewise linear. If not, we assume that we can appxoimate it using a piecewise linear approach.

Then we need a set of weights, and a set of indicator variables. We also need slopes/coefficients that will be the A-matrix.

and some pmore idk

Question 3

Elaborate on knapsack problems

Answer 3

Extremely important: the knapsack problem is differnet for min and max problems.

For max, all the constraints must be <=.
for min problems, all constraints must be >=.
This allows us to make use of the knapsack property of the ratio between objective function coeffciients and corresponding technology coeffcients ot make greedy decisions.

The problem is generally defined as selecitng a set of objects, with the aim of maximizng value, subject to capacity constraints.