===========================================================================
CSC 373                     Homework Exercise 6                   Fall 2008
===========================================================================

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 x_i >= 0 on all variables
x_i), only allows maximization of the linear objective function, and
insists that all constraints are in the form
    \sum_{i=1...n} a_{j,i} x_i <= b_j
(where a_{j,i} and b_j 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

        a_1 x_1 + a_2 x_2 + ... + a_n x_n >= b.

    Describe precisely how to convert these to constraints of the form

        a'_1 x_1 + a'_2 x_2 + ... + a'_n x_n <= b'

    as required by MELPSE.


3.  This problem also has constraints of the form

        a_1 x_1 + a_2 x_2 + ... + a_n x_n = 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 a_1 x_1 + a_2 x_2 + ... + a_n x_n <= b.

    But we have a problem where one of the variables, x_i, could be
    negative.  Describe precisely how to construct an equivalent LP where
    we replace x_i 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.