# EasyAssignmentProblemToLP.java

Below is the syntax highlighted version of EasyAssignmentProblemToLP.java from §6.5 Reductions.

```/******************************************************************************
*  Compilation:  javac EasyAssignmentProblemToLP.java
*  Execution:    java EasyAssignmentProbelmToLP n
*  Dependencies: LinearProgramming.java
*
*  Solve an n-by-n assignment problem (maximum weighted bipartite matching)
*  by reducing it to linear programming.
*
*  Warning: in practice, use Assignment.java which runs in n^3 log n time
*
*
******************************************************************************/

public class EasyAssignmentProblemToLP {

public static void main(String[] args) {

int n = Integer.parseInt(args);

// cost vector
double[] c = new double[n*n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
c[i*n+j] = StdRandom.uniform();    // cost of assigning i-j

// RHS vector
double[] b = new double[2*n];
for (int i = 0; i < 2*n; i++)
b[i] = 1.0;

// constraint matrix
double[][] A = new double[2*n][n*n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
A[i][i*n+j] = 1.0;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
A[j+n][i*n+j] = 1.0;
}
}

// solve linear program
LinearProgramming lp = new LinearProgramming(A, b, c);

// print weight of max weight perfect matching
double weight = lp.value();
StdOut.println(weight);

// print max weight perfect matching
double[] x = lp.primal();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (x[i*n+j] == 1.0) {
StdOut.println(i + "-" + j);
}
}
}

}
}
```