Integer chapter 14

Question 1

Motivation for choosing the right model

Answer 1

In integer programming models can have the exact same feasible region, but differ in the feasible region of the LP relaxation. The difference between these feasible regions is impactful. We use the terms strong and weak LP formulations.

A strong LP formulation is one that is much closer to the region of the IP problem.

Question 2

Precisely, what is a stronger model?

Answer 2

If the LP relaxation’s optimal objective function value is far away from the optimal IP solution, then the model is bad/weak. If the two optimal solutions are close together, the model is strong.

Question 3

elaborate on convex hull

Answer 3

Mathematically, a convex hull is all possible convex combinations of a set of points x^(k). Therefore, a convex hull is a convex area. This we know from the definition of a convex combination.

In IP problems, the feasible region typically consists of integer points, which means that the convex hull has a shape of straight linear lines.

Question 4

What is the ultiamte conclusion of convex hulls in regards to IP

Answer 4

If we solve the contiunuous problem:

min z = cx
s.t.
x in Xc

where Xc is the convex hull given by the convex combinations of the feasible points in the IP problem,

we get that hte solution to the LP relaxation is the same as the optimal solution of the IP problem.

Question 5

do we try to find the convex hull in practice?

Answer 5

Not necessarily, but we try to limit the differnece between the LP relaxation feasible region and the convex hull in areas where we find it to be beneficial.

the entire region/border of the convex hull is not interesting. We care about the part where the optimal solution is likely to be.

Question 6

how can we decrease the difference betwee the feasible region (particularily near optimal solution) and the convex hull?

Answer 6

1) Initially choose a strong model formulation
2) Adding problem specific valid inequalities

Question 7

define a valid inequality

Answer 7

a linear inequality that is satisfied for all x in X_IP

Meaning, a constraint that does not affect the feasible region of the IP problem. However, it may make the LP feasible region closer to the convex hull, which is ultimately what we want here.

Question 8

What is the point of valid inequalities

Answer 8

The point of using valid inequalities is to approximate the convex hull better

Question 9

when we want to add valid inequalities, what is the goal?

Answer 9

The goal is to generate constraints that are as strong as possible. Mathematically, we say that the goal is to generate constraints that define a “face” to the convex hull that has as large a dimension as possible.

Question 10

elaborate on the face of a convex hull

Answer 10

So we are already considering a convex hull, which is a result of the space/region/whatever of all convex combinations of the set of feasible integer solutions. Then, to define a specific face of the convex hull, we have to consider a valid inequality (so that the convex hull is not changed), and the valid inequality defines a hyperplane that must intersect with a part of the convex hull. These requirements mean that the hyperplane can never cross the convex hull, and must therefore lie on top of it. If the convex hull has 3 dimensions and has the shape of a “box”, then a face can be defined on the sides, the edges, and vertices, according to the mathematical definition.
In regards to optimization, the faces are strongest when they are in the dimension of the convex hull, less 1. This would mean that in regards to the 2d box, a hyperplane (valid inequality) lying on one of the entire surface areas define a face we are very interested in, as it cover much ground that help us reduce the difference between the feasible region of the LP relaxation and the convex hull

Question 11

Mathematically define a face

Answer 11

IF ∑aj xj <= b is a valid inequality to X_IP, then the set:

F = {x: x in X_C, ∑ajxj = b}

few points to notice:
1) There is a requirement that the constraint is valid inequality. This ensure that the constraint does not cross the convex hull at any point.
2) Since the hyperplane (valid inequality) never cross the convex hull, and the requirement is that the point must be in the convex hull as well as satisfy the hyperplane, there is a tangential thing going on. This means, that a convex hull of dim “n” can have faces of at most dim “n-1”, but can also have smaller.

Question 12

Define a facet

Answer 12

A Face F of a convex hull X_C with dimension dim(X_C)=n is called a facet if dim(F)=n-1

Question 13

Elaborate on facets

Answer 13

Of utmost importance is regards to finding strong models.

Question 14

broadly about cutting plane methods

Answer 14

approximate the convex hull X_C better and better by finding valid inequalities, which are hyperplanes that cuts away parts of the LP feasible region, but not the convex hull, which means that the IP feasible region remains preserverd.

Question 15

Important part about cuttign plane methods

Answer 15

We want to approximate the convex hull in areas where it is likely that the optimal solution is.

Question 16

What is the actually most important part about cutting plane methods?

Answer 16

If we use an iterative approahc, we actually have to cut the part of the region where the LP relaxation’s optimal solution is. If we dont cut this away with the cut, then the next relaxation will give the same solution, and we wont progress. Therefore, it is important that we reduce this exact part of the difference between LP feasible region and convex hull.

Question 17

Using a general cutting plane method, when do we stop?

Answer 17

We stop when we find an integer solution to one of the LP relaxations

Question 18

Using a general cutting plane method, how do we add the cuts?

Answer 18

We typically use some method that generat ethem, like Gomory’s

Question 19

elaborate on the requirement of Gomory’s method

Answer 19

All coefficients must be integers. Recall that we can achieve this by multiplying with a suitable constant.

The reason why we require integer coefficeints, is that this will make sure that all slack variables have integer values always.

Question 20

Elaborate on the Gomory method

Answer 20

We solve LP relaxation. Take the optimal tableau, and find the basic solution.

We can construct it like this, meanign that for each basic variable we have:

xi + ∑bar(aij)xj = bar(bi), where the sum is the non basics.

We take one of these (one if “i’s”) that have fractional RHS value.

bar(bi) has an integer part and a fractional part. Separate them by flooring bi, and adding the fractional part.
We do the same for bar(aij).
Then we move all the integer parts on the LHS, and fractionals on RHS.
Then we use the fact that we know that LHS is integer, so RHS must be too.
Now we have:

xi + ∑int(bar(aij))xj - int(bar(bi)) = frac(bi) - ∑frac(aij)xj

We know that RHS is integer.
We also know that RHS is less than 1, since frac(bi) is less than 1, and frac(aij)xj is positive.
Therefore, RHS <= 0.
This is what we use to make the valid inequality:

xi + ∑aijxj <= bi, where they are the integer parts. Called Gomory’s cut. refers to integer cut. There is also the fractional cut that represent the same cut but with differnet values.

The idea is to find one of the components (basic variable) of the optimal solution. Then we remove the fractional part, and keep the integer part. Keeping the integer part makes sure we dont cut away any of the convex hull. However, we cut away the fractional part, so we reduce the LP feasible region.
We also remove the LP optimal solution, which makes sure we progress our method.

Question 21

In gomorys method, when we have several basic variables with fractional RHS’ to choose from, which do we choose?

Answer 21

Typically the one with the largest fractional value

Question 22

Define a cover

Answer 22

We say that a set “S” is a cover if ∑aj [j in S] > b.

A cover refers to a set of variables whose sum of coefficients is greater than b, where b is the RHS value. This means that if all variables are binary, setting them to 1 will satisfy the condition.

Question 23

What is a minimal cover+

Answer 23

minimal cover is a cover where the selection is so tight that removing as much as one of the members (regardless of which) would make the set no longer be a cover.

Question 24

Give teh feasible region of a binary knapsack problem

Answer 24

X = {x in {0,1} : ∑aj xj <= b}

Question 25

Elaborate on minimal covers in relation to knapsack

Answer 25

A minimal cover represent a subset of variables that does not satisfy the knapsack constraint. However, from the definition of a minimal cover, the cover will satisyfy the knapsack constraint if we were to remove one of its members.

Inutitively, a minimal cover can be regarded as the smallest set that is too large to be included in the knapsack.

Question 26

What is the thoerem that gives a valid inequality for knapsack problems

Answer 26

If S is a minimal cover, then the constraint

∑xj [j in S] <= |S| - 1

is a valid inequality for X.

The reason for this is that when we sum over the variables in the minimal cover set S, then we know that we can include all of them, except for one. Since the 0/1 knapsack problem only allows for binary variables, we can treat it like a sum.

Question 27

Can we make a cover cosntraint better/stronger?

Answer 27

Yes, by considering the “augmented cover constraint”.

Question 28

elaborate on augmented cover constraint

Answer 28

Augmented cover constraint refer to the constraint:

If S is a cover of X, then the augmented cover constraint

∑xj [j in E(S)] <= |S|-1

is a valid inequality if E(S) = S union {j : aj >= ai, for all i in S}

Question 29

elaborate on lifting

Answer 29

lifting is a way to strengthen a valid inequality by making some of the coefficeints larger in the cosntraint.

For instance:

Consider original constraint:
4x1 + 2x2 + 2x3 + 3x4 <= 4

and valid inequality:

x1 + x2 + x3 + x4 <= 2

This is a valid inequality. Since if either x1 or x4 has value 1, then all other variables must be 0, we can lift therse coefficients to 2:

2x1 + x2 + x3 + 2x4 <= 2

We find this by looking at the original constraint. The coefficients of 4 and 3 make it so that if one of them are selected, no one else can be selected. Therefore, we can raise the coefficient in the valid inequality to tighten them even more.

Question 30

elaborate on formulating an optimization problem that decides if there exists a cover inequality to the problem, and if the reply is “yes”, it determines the strongest constraint

Answer 30

We start with the first part.

“Determine if there exists a cover inequality to the problem”.

We use the definition of cover inequality.
If S is a minimal cover, then the constraint
∑xj [j in S] <= |S| - 1
is a valid inequality for X.
Also, we know that the set S is a cover if
∑aj [j in S] > b

We can structure this like this:

∑aj [j in S] > b, AND ∑(1-xj^LP) [j in S] < 1

Basically, this say that
1) set S is a cover
2) Forcing each variable to be 1 in the LP solution

So, if we can answer whether these two conditions exist for a set S, then we know that there exists a cover inequality to the problem.