MATP6640/DSES6770

Linear Programming

Spring 2010

Midterm Exam, Tuesday, April 6, 2010.

Please do all three problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.

Throughout, the standard primal-dual LP pair is

where A is m × n and the vectors are dimensioned appropriately.

- (30 points)

The linear programhas x

_{B}IR^{3}, x_{ N}IR^{1}, b IR^{3}, and c, B, and N dimensioned appropriately. The matrix B is invertible, and matrices L and U are known with LB = U, andLet

Solve the following questions without finding B explicitly.

- (10 points) Show that the basic feasible solution for basis B has x
_{B}= (3, 2, 4)^{T }. - (10 points) Use complementary slackness to show that the corresponding dual
solution is y = (7,-10,-2)
^{T }. - (10 points) For what values of c
_{N}is this solution optimal?

- (10 points) Show that the basic feasible solution for basis B has x
- (30 points)

A set of exams {1,…,n} is to be given, with only one exam given at a time. Exam i has duration l_{i}and a day has length L. An exam must start and finish on the same day. It is desired to schedule the exams in as few days as possible. Let S^{j}⊆{1,…,n} be a set of exams that can be scheduled in a single day and let a_{j}IR^{n}be the incidence vector of this set. Each set S^{j}must observe the restriction that no student sits more than one exam in a single day. This restriction can be modeled using a set of pairs P of exams, with (p,q) P corresponding to at least one student taking both exams p and q.- (10 points)

Show that the problem can be modeled as the following integer program:where the sum is taken over all valid subsets S

^{j}⊆{1,…,n}, and e denotes the vector of ones. - (20 points)

In a column generation approach to solve the LP relaxation of (IP), a primal solution and a dual solution are generated as optimal solutions for the current set of columns. How do you determine whether and solve the full LP relaxation?

- (10 points)
- (10 points)

Consider the LP:Show that , 1, 3) is on the central trajectory for this problem, with

= (2^{T }= 36 for some dual feasible . - (30 points; each part is worth 10 points.)

Recall the standard primal-dual pair of linear programming problems (P) and (D) from the cover page. Now consider the linear programming problemwhere t is a scalar.

- Suppose the optimal solution to (HLP) is (,ỹ, ), with > 0. How would you use this solution to find optimal solutions to (P) and (D)?
- Show that (HLP) is self-dual, that is, the dual to (HLP) is again the problem (HLP).
- Let (,, ) be a solution to both (HLP) and its dual that is strictly
complementary and has = 0. Show that either there exists a vector x ≥ 0 with
Ax = 0 and c
^{T }x < 0 or there exists a vector y with A^{T }y ≤ 0 and b^{T }y > 0. What can you conclude about (P) and (D)?