MATP6620/ISYE6760 Combinatorial Optimization & Integer Programming

Homework 3.

Solutions

Due: Thursday, March 4, 2021, by end of day.

Penalty for late homeworks: 10% for each day or part of a day.

The following graph G = (V,E) is used in question 1.

- Consider a node packing problem on the above graph, with each vertex having weight equal to 2 more than
its degree. The LP relaxation includes the clique constraints ∑
_{v∈C}x_{v}≤ 1 for each maximal clique C in the graph. The point x_{A}= 0.4, x_{B}= 0.6, x_{C}= 0.4, x_{D}= 0.5, x_{E}= 0.4, x_{F}= 0.5, x_{G}= 0.1, x_{H}= 0.4, and x_{J}= 0.1 is feasible in the LP relaxation.- Show that the given point is not in the convex hull of feasible solutions, by giving a valid constraint that is violated by this point.
- Find an optimal solution to the node packing problem for this graph. Prove your solution is optimal.

Solution:

- Vertices A,B,C,H,F constitute an odd hole, giving the valid constraint
The left hand side of this constraint evaluates to 2.3 for the given point.

- If x
_{G}= 1 then the largest possible value for the left hand side of the constraint in part (a) is 1, so the constraint can be lifted to(1) The vertices D,E,J form a clique, so we also have the valid constraint

Thus, any packing can use at most 3 vertices.

(We could also argue this using the odd hole constraint formed by {C,D,E,F,H}, which can be lifted with both G and J, so at most 2 of the 7 vertices {C,D,E,F,G,H,J} can be used. Also, at most one of {A,B} can be used.)

The vertices and their degrees are:

degree vertices 5 C 4 F,G,H,J 3 A,D,E 2 B We claim the node packing A,C,E with value 17 is optimal.

First note, any packing with just 2 vertices has value at most 13. So the optimal packing must contain 3 vertices.

Vertices C and F constitute a maximal packing, so they cannot both be part of an optimal packing. Vertex C is adjacent to all of G, H, and J, so any packing containing C with 3 nodes cannot have value larger than 17.

F, G, H form a clique, so no packing can contain more than 2 of the vertices of degree 4.

So no packing has value larger than 17.

Alternatively:

Solving the LP relaxation of the node packing problem with the lifted odd hole constraint (1) and the clique inequalities gives the integral solution. Here are the AMPL model and data files, and the AMPL output.

- Consider the constraints
- By considering the different possibilities for x, show that t
_{1}+ t_{2}≥ 1. - The constraints can be modeled equivalently as
Show that the valid constraint t

_{1}+ t_{2}≥ 1 has Chvatal rank equal to 2.

Solution:

- Four choices for x, with the minimum possible corresponding choices for t:
- Rank is no larger than 2:
Write constraints as:

(6) (7) In the second round, 0.5(6) + 0.5(7) implies

as required.

Rank is at least 2:

The point x = (0.5,0.5) and t = (0,0) satisfies (2)–(5). This point is a convex combination of the integer points x = (0,0), t = (0,0) and x = (1,1), t = (0,0). So any valid linear combination of (2)–(5) must be satisfied by at least one of these points, and so the rounded version must also be satisfied by at least one of the points.

Alternatively, since the point x = (0.5,0.5) and t = (0,0) is feasible in the LP relaxation, the maximum value of -t

_{1}- t_{2}in the LP relaxation is 0. Thus, by the proposition in the notes, the best rank one inequality is only -t_{1}- t_{2}≤ 0, so the desired inequality has CG rank at least two.

- By considering the different possibilities for x, show that t
- The optimal tableau to the linear programming relaxation of the integer program
where x

_{3}and x_{4}are the slack variables in the two constraints. Find the Gomory and strong Gomory cutting planes implied by the two constraints. Express these constraints in terms of the original variables x_{1}and x_{2}and draw them on a graph of the feasible region.Solution:

First constraint: Fractional parts: f

_{3}= , f_{4}= , f_{0}= .Gomory cut:

In terms of the original variables, x

_{3}= 14 - x_{1}- 2x_{2}and x_{4}= 8 + x_{1}- 6x_{2}, so we haveor

(8) Mixed integer Gomory cut:

or equivalently

In terms of the original variables, we have

or

(9) Second constraint: Fractional parts: f

_{3}= , f_{4}= , f_{0}= .Gomory cut:

In terms of the original variables, we have

or

(10) Mixed integer Gomory cut: Since f

_{3}≤ f_{0}and f_{4}≤ f_{0}, the mixed integer Gomory cut is identical to the original Gomory cut.Graph:

- Let x ∈ B
^{n}satisfy the constraints(11) Show that the constraint

(12) is valid. Give a fractional point with 0 ≤ x ≤ e that satisfies the original n(n - 1)∕2 constraints but violates the new constraint. Show that the new constraint has Chvatal rank no larger than O(log n).

Solution:

- Any binary vector that violates (12) must have at least two components with value 0, say
x
_{p}= x_{q}= 0, with 1 ≤ p < q ≤ n. Then this point violates the corresponding constraint of form (11). - Each x
_{i}= 0.5 satisfies (11) and violates (12). - We use induction to show the constraint has rank no more than O(log(n)). Let k be an integer with
2 < k < n. Assume we know
(13) for all subsets C ⊆{1,…,n} with |C| = k. Let J ⊆{1,…,n} with k < |J| < 2k - 1. We show the inequality

(14) can be derived in one step. We need two parameters:

Thus by induction the inequality (13) has Chvatal rank as follows:

k Chvatal rank 2 0 3 1 4 or 5 2 6,7,8,9 3 10,…,17 4 … This can be expressed compactly by saying the rank is no larger than ⌈log

_{2}(k - 1)⌉ for k = 2,3,…If |J|≥ 2k then (14) cannot be obtained in one step from all the inequalities (13). In particular, if we set each x

_{i}= 1 - 1∕k then all of the inequalities (13) are satisfied, and the left hand side of (14) evaluates toThus, rounding cannot give (14) in one step.

A proof that the rank is at least O(log(k)) is a consequence of Theorem 4.12 in [1].

- Any binary vector that violates (12) must have at least two components with value 0, say
x
- The AMPL model of the LP relaxation of a random weighted node packing problem with 15 nodes is
contained in the file

http://www.rpi.edu/~mitchj/matp6620/hw3/nodepack.modThe initial model contains only the adjacency constraint that just one endpoint of an edge can appear in the node packing. Pick a seed and then solve the problem using a cutting plane algorithm:

- Solve the LP relaxation.
- If the solution is integral, STOP.
- If necessary, add one or more valid inequalities to the LP. These inequalities can be clique inequalities or odd hole inequalities.
- Return to Step (a).

(It is highly likely that you will need to use both clique inequalities and odd hole inequalities, and that these inequalities will be sufficient to solve the problem.)

(Hint: The graph consists of the cycle 1 - 2 - 3 - 4 -…- 14 - 15 - 1, plus some extra edges. You might be able to see the structure by displaying adjacency.)

Solution:

Here is the model file with the seed 3242. Solving this problem required the addition of two clique constraints and 4 odd hole constraints, with each clique containing 3 nodes and each odd hole containing 5 nodes. Here is the output file with the seed 3242.

- The Project:

Along with your solutions to this homework, hand in a brief description of what you would like to do for the project part of this course.

[1] R. Müller and A. S. Schulz. Transitive packing: a unifying concept in combinatorial optimization. SIAM Journal on Optimization, 13(2):335–367, 2002.

John Mitchell |

Amos Eaton 325 |

x6915. |

mitchj at rpi dot edu |

Office hours: Monday and Thursday 1pm–2pm. |

webex: https://rensselaer.webex.com/meet/mitchj |