Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package models;
import ilog.concert.IloException;
import ilog.concert.IloLinearNumExpr;
import ilog.concert.IloNumVar;
import ilog.cplex.IloCplex;
import ilog.cplex.IloCplex.Status;
import java.util.HashSet;
import java.util.Set;
import socialnet.Graph;
/**
* FlowModel implements a MIP model for the problem based on flows between
* nodes.
*
* @author Paul A. Rubin (rubin@msu.edu)
*/
public final class FlowModel implements AutoCloseable {
private static final double HALF = 0.5; // for rounding tests
private final int nVertices; // number of vertices in the graph
private final int nEdges; // number of edges
// CPLEX objects.
private final IloCplex mip; // the MIP model
private final IloNumVar[] select; // indicators for selecting vertices
private final IloNumVar[] flowF; // forward edge flows
private final IloNumVar[] flowR; // reverse edge flows
/**
* Constructor.
* @param graph the graph to solve
* @param nSelect the number of nodes to select
* @throws IloException if the model cannot be constructed
*/
public FlowModel(final Graph graph, final int nSelect) throws IloException {
nVertices = graph.getnVertices();
nEdges = graph.getnEdges();
// Initialize the model.
mip = new IloCplex();
// Create the variables.
select = new IloNumVar[nVertices];
flowF = new IloNumVar[nEdges];
flowR = new IloNumVar[nEdges];
for (int i = 0; i < nVertices; i++) {
select[i] = mip.boolVar("select_" + i);
}
for (int i = 0; i < nEdges; i++) {
flowF[i] = mip.numVar(0, nVertices, "forward_" + i);
flowR[i] = mip.numVar(0, nVertices, "backward_" + i);
}
// The objective is to minimize the sum of all flows.
mip.addMinimize(mip.sum(mip.sum(flowF), mip.sum(flowR)));
// The number of nodes selected must match the requirement.
mip.addEq(mip.sum(select), nSelect, "selection_count");
// At every node, there must be exactly one unit more of outflow than of
// inflow unless the node is selected.
int m = nVertices - nSelect; // "big M"
for (int i = 0; i < nVertices; i++) {
// Form an expression of the form flow out of i minus flow into i.
IloLinearNumExpr expr = mip.linearNumExpr();
// Check each edge incident at i.
for (int j : graph.incidentAt(i)) {
if (graph.isHead(i, j)) {
// The forward direction enters i, the reverse direction leaves i.
expr.addTerm(1.0, flowR[j]);
expr.addTerm(-1.0, flowF[j]);
} else {
// The forward direction leaves i, the reverse direction enters i.
expr.addTerm(-1.0, flowR[j]);
expr.addTerm(1.0, flowF[j]);
}
}
// Flow out - flow in must be >= 1 - m * select[i].
mip.addGe(expr, mip.diff(1.0, mip.prod(m, select[i])), "balance_" + i);
}
}
/**
* Solves the model.
* @param timeLimit the time limit for the solver (in seconds)
* @return the final solver status
* @throws IloException if the solution fails
*/
public Status solve(final double timeLimit) throws IloException {
mip.setParam(IloCplex.DoubleParam.TimeLimit, timeLimit);
mip.solve();
return mip.getStatus();
}
/**
* Gets the final objective value.
* @return the objective value
* @throws IloException if there is no objective value
*/
public double getObjValue() throws IloException {
return mip.getObjValue();
}
/**
* Gets the set of nodes selected by the solution.
* @return the set of selected nodes
* @throws IloException if no solution exists
*/
public Set<Integer> getSolution() throws IloException {
HashSet<Integer> sol = new HashSet<>();
double[] x = mip.getValues(select);
for (int i = 0; i < nVertices; i++) {
if (x[i] > HALF) {
sol.add(i);
}
}
return sol;
}
/**
* Closes the model.
*/
@Override
public void close() {
mip.close();
}
}