MATP6640/DSES6770 Linear Programming, Homework 5.

Due: 11.59pm on Sunday, March 31, 2024 on LMS.
10% penalty for each day late.

  1. Consider the primal-dual pair of linear programs:
    minx ∈ℝ3 3x1 + 3x2 + 2x3 max 17y1 + y2 subject to x1 + x2 + x3 = 17 (P ) s.t. y1 + 3y2 ≤ 3 (D ) 3x - x + x = 1 y - y ≤ 3 1 2 3 1 2 x1, x2,x3 ≥ 0 y1 + y2 ≤ 2

    Show that y = (1,-1) is on the central trajectory for this problem. What is the corresponding primal point?

  2. Take one step of the affine method from the primal point you found in Question 1.
  3. Take one step of the primal-dual interior point method from the point you found in Question 1.
  4. (Wright, Chapter 2, Question 6, page 47.) Construct standard form feasible linear programs with finite optimal value with n ≤ 3 and
    1. B = ∅
    2. B = {1,…,n}.
  5. Pick three problems from the netlib LP test suite, at http://www.netlib.org/lp including the problem boeing1. Solve each problem using both a simplex algorithm and an interior point algorithm. Do you get the same primal solution with each algorithm? What if you don’t crossover to get a BFS? (Differences less than 10-8 can be ignored.)

    Hand in the primal solution for each problem, and discuss whether the three solutions differ for each of the models you chose. If the solutions have too many variables it is fine to select a few variables to display.

    The problems are in MPS format at the netlib link. Options for solving them include:

    (A) Most of the problems are also available in AMPL format on Box at

    https://rpi.box.com/s/5ucl9wog8ey4pcgxnridpehvqc4b74ng

    The 00README.txt file explains how to run the AMPL models.

    A list of cplex options available in AMPL is available here:

    https://dev.ampl.com/solvers/cplex/options.html

    Of particular interest are baropt to run an interior point code, crossover to find an optimal BFS after baropt finds a point on the optimal face, and dualopt and primalopt to run different versions of simplex. The commands pgradient and dgradient allow different pricing options within primal simplex and dual simplex, respectively. You can use these options in ampl with the syntax option cplex_options ’...’;

    (B) Alternatively, you can run cplex directly, without using ampl, in which case you would read in the MPS file. Standalone versions of cplex can be obtained through the IBM Academic Initiative, by downloading CPLEX Studio.

    Useful commands in cplex include read, optimize, and display. You can choose the solver in cplex by issuing the command set lpmethod at the prompt. You can change options in the barrier solver (including the use of crossover) with the command set barrier; unfortunately, crossover seems to no longer give the option of not using it.

    (C) My first PhD student, Brian Borchers, has code available to convert MPS files into MATLAB format.

  6. Hand in a progress report of your work to date on the course project.
    John Mitchell 518–276–6915
    Amos Eaton 325 mitchj at rpi dot edu
    Office hours: Tues 2.30-4pm, AE 325 (masks required) or webex.
    Thurs 1–2pm, webex: https://rensselaer.webex.com/meet/mitchj