Homework Exercise 6

Due: by 6pm on Tue 18 Nov
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

Your company has recently discovered that several of its problems can be solved using linear programming. Your company doesn't want to write their own solver program, since many efficient programs are available for sale. But your boss has been reading his spam again and went out and purchased the MELPSE system (Most Efficient Linear Program Solver Ever!) in a fit of misdirected leadership.

As expected, the claim is slightly overstated, and the package comes with some limitations. From the advertisement:

"MELPSE is the fastest and most streamlined LP solver ever! Using the latest technology, it will find the best non-negative values for all your variables, get the biggest value for your objective function, and it will even make sure that A x ≤ b!"

In fact, this is all that MELPSE can do: it only supports non-negative variables (it implicitly enforces a constraint xi ≥ 0 on all variables xi), only allows maximization of the linear objective function, and insists that all constraints are in the form ∑i=1...n aj,i xi ≤ bj (where aj,i and bj are real numbers, perhaps negative).

The linear programs you need to solve are usually minimization problems, where variables occasionally take negative values, and some constraints are expressed with equality or greater-than-or-equal. The boss has already spent your entire budget, so to save your team you will need to figure out how to use the MELPSE system to solve your problems.

  1. One of your problems fits the restrictions of MELPSE except that you need to minimize your objective function. Describe precisely how to convert your program into one MELPSE can solve; that is, describe how to create an equivalent LP where the objective is being maximized. Briefly explain how to use a solution to your new program to find a solution to your original problem.

  2. Another of your problems contains some constaints of the form

    a1 x1 + a2 x2 + ... + an xn ≥ b.

    Describe precisely how to convert these to constraints of the form

    a'1 x1 + a'2 x2 + ... + a'n xn ≤ b'

    as required by MELPSE.

  3. This problem also has constraints of the form

    a1 x1 + a2 x2 + ... + an xn = b.

    Describe precisely how to create an equivalent LP that can be solved by MELPSE (or in the form of question 2).

  4. From the previous parts we know how to solve a minimization problem with "≥" or "=" constraints. We can assume that all constraints are in the form a1 x1 + a2 x2 + ... + an xn ≤ b.

    But we have a problem where one of the variables, xi, could be negative. Describe precisely how to construct an equivalent LP where we replace xi with two new variables which can only take non-negative values. (Hint: think subtraction.) Briefly explain how to use a solution to your new program to find a solution to the original problem.

  5. Let's put it all together: Write an efficient high-level algorithm that will convert a linear program that might be a minimization problem, might contain greater-than-or-equal or equality constraints, and may contain variables lacking a non-negativity constraint, into an equivalent linear program that can be solved by MELPSE. Give a good bound on the size (the number of variables and number of constraints) of your new linear program, briefly justify that it is equivalent to the original one, and explain how to find a solution to the original problem from a solution to your new problem.