EasyAssignmentProblemToLP.java 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
* instead of this version.
*
*
******************************************************************************/
public class EasyAssignmentProblemToLP {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
// 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);
}
}
}
}
}
Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne. Last updated: Sun Mar 13 14:05:37 EDT 2022.
