/
GRBInterface.h
197 lines (165 loc) · 5.82 KB
/
GRBInterface.h
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#ifndef GRBINTERFACE_H
#define GRBINTERFACE_H
#include "gurobi_c++.h"
#include "KGraph.h"
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include<climits>
#include <unordered_map>
//Boolify function
vector<bool> boolify(vector<long> &S, long n);
vector<bool> boolify(double *y, long n);
//Printing function
void PrintVectorLong(vector<long>&S);
//Variable fixing function
vector<long> FindNonCriticalNodes(KGraph &g);
//Check if a vertex is simplicial
bool IsSimplicial(KGraph &g, long i);
//Calculate number of vertex pairs with distance at most k in graph G-D (obj(G-D)) where G is unweighted
long obj(KGraph &g, vector<long> &deleted, long k);
long obj(KGraph &g, vector<bool> &nondeleted, long k);
//Calculate number of vertex pairs with distance at most k in graph G-D (obj(G-D)) where G is weighted
long obj_weighted(KGraph &g, vector<long> &deleted, long k);
long obj_weighted(KGraph &g, vector<bool> &nondeleted, long k);
//Data structure to store variables d(v,s) and p(v,s) for fractional separation
struct d_and_p
{
vector < vector<double> > d;
vector< vector<long> > p;
};
//Function to calculate variables d(v,s) and p(v,s) for fractional separation
d_and_p d_and_p_function(KGraph &goriginal, KGraph &gpower, long i, long k, double *y);
//Betweenneess Centrality function
vector<long> FindTopTBetweennessCentralityNodes(KGraph &g, long T);
//Betweenneess Centrality function for weighted graphs
vector<long> FindTopTBetweennessCentralityNodesWeighted(KGraph &g, long T, long k);
//DCNP Heuristic to find distance-based critical nodes
vector<long> DCNP_Heuristic(KGraph &g, long s, long B);
//DCNP Heuristic to find distance-based critical nodes in weighted graphs
vector<long> DCNP_Heuristic_Weighted(KGraph &g, long s, long B);
/*To solve DCNP when distances are measured in terms of hops
* Thin formulation with integer separation is used. */
vector<long> Thin_I(KGraph &g, long k, long b, vector<long> &Heuristic_sol, bool &subopt, vector<bool> &Initial);
void ConstraintGenerator1(KGraph &g, GRBModel &model, unordered_map<long, long> hash_edges, GRBVar *X, GRBVar *Y);
void ConstraintGenerator2(KGraph &g, GRBModel &model, unordered_map<long, long> hash_edges, GRBVar *X, GRBVar *Y);
void ConstraintGenerator3(KGraph &g, GRBModel &model, unordered_map<long, long> hash_edges, GRBVar *X, GRBVar *Y);
void ConstraintGenerator4(KGraph &g, GRBModel &model, unordered_map<long, long> hash_edges, GRBVar *X, GRBVar *Y);
/*To solve DCNP when distances are measured in terms of hops
* Thin formulation with fractional separation is used. */
vector<long> Thin_F(KGraph &g, long k, long b, vector<long> &Heuristic_sol, bool &subopt, vector<bool> &Initial);
/*To solve DCNP when distances are measured in terms of hops and k=3
* Path-like formulation is used */
vector<long> Path_like_k3(KGraph &g, long b, vector<long> &Heuristic_sol, bool &subopt);
/*To solve DCNP when distances are measured in terms of hops and k=4
* Path-like formulation is used */
vector<long> Path_like_k4(KGraph &g, long b, vector<long> &Heuristic_sol, bool &subopt);
/*To solve DCNP when distances are measured in terms of hops
* Recursive formulation is used. */
vector<long> Recursive(KGraph &g, long k, long b, vector<long> &Heuristic_sol, bool &subopt);
/*To solve DCNP in edge-weighted graphs.
* Thin formulation with integer separation is used.*/
vector<long> Thin_Weighted(KGraph &g, long k, long b, vector<long> &Heuristic_sol, bool &subopt);
/*** callback functions for DCNP***/
class GeneralCallbackClass : public GRBCallback
{
protected:
GRBVar* xvars; // x variables
double* x; //x values
GRBVar* yvars; //y variables
double* y; //y values
KGraph* g; //original graph
KGraph* gs; //power graph pointer
long n; //number of nodes of power graph = number of nodes of original graph
long gs_m; // number of edges of power graph
public:
GeneralCallbackClass(GRBVar* grb_x_, GRBVar* grb_y_, KGraph* g_, KGraph* gs_) : xvars(grb_x_), yvars(grb_y_), g(g_), gs(gs_)
{
n = g->n;
gs_m = gs->m;
x = new double[gs_m];
y = new double[n];
}
virtual ~GeneralCallbackClass()
{
delete[] x;
delete[] y;
}
protected:
void populate_x_MIPSOL()
{
x = getSolution(xvars, gs_m);
}
void populate_y_MIPSOL()
{
y = getSolution(yvars, n);
}
void populate_x_MIPNODE()
{
x = getNodeRel(xvars, gs_m);
}
void populate_y_MIPNODE()
{
y = getNodeRel(yvars, n);
}
};
class IntegerSeparation : public GeneralCallbackClass
{
private:
unordered_map<long, long> hashing;
long k;
long b;
public:
static long numCallbacks;
static double TotalCallbackTime;
static long numLazyCutsInteger;
IntegerSeparation(GRBVar* grb_x, GRBVar* grb_y, KGraph* g, KGraph* gs, unordered_map<long, long> hash_edges, long k1, long b1) : GeneralCallbackClass(grb_x, grb_y, g, gs)
{
hashing = hash_edges;
k = k1;
b = b1;
}
protected:
void callback();
};
class IntegerSeparationWeighted : public GeneralCallbackClass
{
private:
unordered_map<long, long> hashing;
long k;
long b;
public:
static long numCallbacks;
static double TotalCallbackTime;
static long numLazyCutsInteger;
IntegerSeparationWeighted(GRBVar* grb_x, GRBVar* grb_y, KGraph* g, KGraph* gs, unordered_map<long, long> hash_edges, long k1, long b1) : GeneralCallbackClass(grb_x, grb_y, g, gs)
{
hashing = hash_edges;
k = k1;
b = b1;
}
protected:
void callback();
};
class FractionalSeparation : public GeneralCallbackClass
{
private:
unordered_map<long, long> hashing;
long k;
long b;
public:
static long numCallbacks;
static double TotalCallbackTimeInteger;
static double TotalCallbackTimeFractional;
static long numLazyCutsInteger;
static long numLazyCutsFractional;
FractionalSeparation(GRBVar* grb_x, GRBVar* grb_y, KGraph* g, KGraph* gs, unordered_map<long, long> hash_edges, long k1, long b1) : GeneralCallbackClass(grb_x, grb_y, g, gs)
{
hashing = hash_edges;
k = k1;
b = b1;
}
protected:
void callback();
};
#endif