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
package socialnet;
import ilog.concert.IloException;
import ilog.cplex.IloCplex.Status;
import java.util.Set;
import models.AssignmentModel;
import models.DistanceModel;
import models.DistanceModel2;
import models.DistanceModel3;
import models.FlowModel;
/**
* SocialNet tests various models for a social network-based optimization
* problem posed on OR Stack Exchange.
*
* Link: https://or.stackexchange.com/questions/8674/is-this-ilp-formulation-
* for-group-closeness-centrality-a-column-generation-appro
*
* @author Paul A. Rubin (rubin@msu.edu)
*/
public final class SocialNet {
/**
* Dummy constructor.
*/
private SocialNet() { }
/**
* Runs the experiments.
* @param args the command line arguments (unused)
*/
@SuppressWarnings({ "checkstyle:magicnumber" })
public static void main(final String[] args) {
// Parameters for the test graph.
int nVertices = 2000; // vertex count
int nEdges = 10000; // target edge count (actual may be higher)
int nSelected = 20; // size of the group of selected vertices
long seed = 220714; // random number seed
int prog = 1000; // frequency of progress reports
// Generate a graph instance.
Graph graph = new Graph(nVertices, nEdges, seed, prog);
System.out.println(graph);
// Set a time limit for each run (in seconds).
double timeLimit = 600;
// Try the flow model.
System.out.println("\n*** Trying flow model. ***\n");
try (FlowModel fm = new FlowModel(graph, nSelected)) {
Status status = fm.solve(timeLimit);
System.out.println("\nFinal solver status = " + status
+ "\nFinal objective value = " + fm.getObjValue());
// Check and print the solution.
Set<Integer> sol = fm.getSolution();
System.out.println(graph.check(sol));
} catch (IloException ex) {
System.out.println("The flow model blew up:\n" + ex.getMessage());
}
// Try the original distance model.
System.out.println("\n*** Trying original distance model. ***\n");
try (DistanceModel dm = new DistanceModel(graph, nSelected)) {
Status status = dm.solve(timeLimit);
System.out.println("\nFinal solver status = " + status
+ "\nFinal objective value = " + dm.getObjValue());
// Check and print the solution.
Set<Integer> sol = dm.getSolution();
System.out.println(graph.check(sol));
} catch (IloException ex) {
System.out.println("The distance model blew up:\n" + ex.getMessage());
}
// Try the distance model with Rob's modification.
System.out.println("\n*** Trying modified distance model. ***\n");
try (DistanceModel2 dm = new DistanceModel2(graph, nSelected)) {
Status status = dm.solve(timeLimit);
System.out.println("\nFinal solver status = " + status
+ "\nFinal objective value = " + dm.getObjValue());
// Check and print the solution.
Set<Integer> sol = dm.getSolution();
System.out.println(graph.check(sol));
} catch (IloException ex) {
System.out.println("The distance model blew up:\n" + ex.getMessage());
}
// Try the distance model with a mix of binary and continuous variables.
System.out.println("\n*** Trying mixed integer distance model. ***\n");
try (DistanceModel3 dm = new DistanceModel3(graph, nSelected)) {
Status status = dm.solve(timeLimit);
System.out.println("\nFinal solver status = " + status
+ "\nFinal objective value = " + dm.getObjValue());
// Check and print the solution.
Set<Integer> sol = dm.getSolution();
System.out.println(graph.check(sol));
} catch (IloException ex) {
System.out.println("The distance model blew up:\n" + ex.getMessage());
}
// Try the assignment model.
System.out.println("\n*** Trying assignment model. ***\n");
try (AssignmentModel am = new AssignmentModel(graph, nSelected, prog)) {
Status status = am.solve(timeLimit);
System.out.println("\nFinal solver status = " + status
+ "\nFinal objective value = " + am.getObjValue());
// Check and print the solution.
Set<Integer> sol = am.getSolution();
System.out.println(graph.check(sol));
} catch (IloException ex) {
System.out.println("The assignment model blew up:\n" + ex.getMessage());
}
}
}