6. Linear Programming

6.1. Theory

6.2. Project: Linear Programming and Maximum-Flows

In this project, you will model and solve a maximum flow problem and a maximum matching problem with a linear programming solver. It means that for these two problems must be encoded into the form of

\[\begin{split}\max \quad & cx \\ \text{subject to} \quad & Ax \leq b \\ & x \ge 0\end{split}\]

that can be used by the simplex algorithm.

6.2.1. Implementation

All the files related to this project are in the package linearprogramming. You have to modify three classes:

  1. BigMSimplex.java

  2. FlowMatrices.java

  3. MatchingMatrices.java

6.2.1.1. BigMSimplex

If the vector \(b\) contains negative entries in the formulation above, the simplex method cannot start directly. A first phase, using the simplex on a transformed problem, is required to find a basic feasible solution. Once this basic feasible solution is found, the second phase proceeds with the simplex on the original objective. This method is implemented in the provided TwoPhaseSimplex.java.

In the two-phase simplex method, the initialization is done by introducing new variables, \(x_a\), called artificial variables, so that these new variables form the initial basic feasible solution. The simplex can then begin pivoting operations while minimizing the sum of these artificial variables. More precisely, if the original problem is:

\[\begin{split}\max \quad & cx \\ \text{subject to} \quad & Ax + s = b \\ & s \ge 0 \\ & x \ge 0\end{split}\]

where \(s\) are the slack variables, then the transformed problem for the first phase is:

\[\begin{split}\max \quad & - \mathbf{1}^\top x_a \\ \text{subject to} \quad & Ax + s + x_a = b \\ & s \ge 0 \\ & x \ge 0 \\ & x_a \ge 0\end{split}\]

In the case where a row includes a negative \(b_i\), the row is multiplied by \(-1\) (except for the term \(x_a\)). Thus, we can assume \(b \ge 0\) in all cases and solve the problem using \(x_a\) for the base. Once the objective of the first phase has reached zero after pivoting operations, it means that all artificial variables are set to 0, and the optimization can switches back to the original objective: \(\max cx\).

This TwoPhase simplex method is is very popular. We propose that you implement and test an alternative method, called the Big-M-Simplex to cope with possibly negative value for \(b_i\) entries. This method does not use two phases but still introduces artificial variables. Instead of switching between two objectives, only one objective is used. This method uses a large constant \(M >> 0\) (called Big-M), and solve following problem (in tableau form):

\[\begin{split}\max \quad & cx - M \, (\mathbf{1}^\top x_a) \\ \text{subject to} \quad & Ax + s + x_a = b \\ & s \ge 0 \\ & x \ge 0 \\ & x_a \ge 0\end{split}\]

Given that the second term is much larger than the first, this will enforce a lexicographic optimization of the two objectives: first, minimizing the use of artificial variables (\(\max \, (\mathbf{1}^\top x_a)\)) then maximize the original objective (\(\max cx\)) as a tie-breaker. Similar to the two-phase simplex method, a first basic feasible solution is readily available with \(x_a\) as the base. Your implementation should be completed within BigMSimplex.java.

You can test your code by running the example in DietProblem.java, that solves the Diet problem .

Once your code is ready, you can submit it onto inginious and work on the report.

6.2.1.2. FlowMatrices

Given a FlowNetwork instance, you must compute the coefficient \(A, b, c\) for solving the maximum flow problem with the simplex implementation. To retrieve your solution depending on your matrices, you must also fill in the function assignFlow in addition to the constructor.

6.2.1.3. MatchingMatrices

Given a bipartite graph, you must compute the coefficient \(A, b, c\) for solving the maximum matching problem with the simplex implementation. To retrieve your solution depending on your matrices, you must also fill in the function isEdgeSelected in addition to the constructor.

6.2.2. Gradescope

On Gradescope, find the written assignment for the project 3. Part of your assignment requires to report experimental results under the form of a graph.