Newer
Older
/********************************************************************************************
Name: DiscretizationSolver
Discrete optimization for graph discretization
Author: J.Omer
Sources: C++
License: GNU General Public License v.2
History:
*********************************************************************************************/
#include "discretizationsolver.hpp"
#include <ctime>
//
ILOLAZYCONSTRAINTCALLBACK2(CyclesLazyConstraints, Instance &, inst, DiscretizationSolver&, solver) {
#ifdef VERBOSE
std::cout << "revorder: check lazy dicycle constraints" << std::endl;
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
// Search for cycles in the current solution digraph
//
// generate the adjacency lists of the vertices corresponding to the current
// cplex solution
float tolerance = 1e-06;
std::map<Vertex*, std::vector<Vertex*> > adjlist;
std::map<Vertex*, int > nbrefs;
for (Vertex* v : inst.vertices_) {
adjlist[v] = std::vector<Vertex*>();
nbrefs[v] = 0;
}
for (Vertex* u : inst.vertices_) {
if (solver.modeltype_ == WITNESS) {
if (getValue(solver.isvertexinclique(u) >= 1 - tolerance)) continue;
}
for (Vertex* v : u->neighbors_) {
if (getValue(solver.isbefore(u, v)) >= 1 - tolerance) {
adjlist[u].push_back(v);
nbrefs[v]++;
}
}
}
//
// search for the root of the digraph
Vertex* root = nullptr;
int minnbrefs = inst.nbvertices_;
if (solver.modeltype_ == WITNESS) {
for (Vertex* v : inst.vertices_) {
if (getValue(solver.isvertexinclique(v) >= 1 - tolerance)) {
root = v;
break;
}
}
} else {
for (Vertex* v : inst.vertices_) {
if (nbrefs[v] < minnbrefs) {
minnbrefs = nbrefs[v];
root = v;
if (minnbrefs < inst.L()) break;
}
}
}
//
// call the enumeration of cycles, returns false if there are none
std::vector<std::vector<Vertex*> > cycles;
bool iscyclic = solver.enumeratecycles(adjlist, root, cycles);
// Look for dicycle inequalities : we restrict the search to the dicycles
// that contain at least one edge in the distance graph
// besides that, the search is performed using brute force
int nbaddedcuts = 0;
IloEnv env = getEnv();
if (iscyclic) {
for (std::vector<Vertex*> path : cycles) {
IloExpr sumedges(env);
int cyclelength = path.size();
Vertex* u = path.back();
for (int i = 0; i < cyclelength; i++) {
Vertex* v = path[i];
sumedges += solver.isbefore(u, v);
u = v;
}
if ((solver.modeltype_ == WITNESS) && (cyclelength <= inst.L() + 1)) {
add(sumedges - solver.isvertexinclique(path.front()) <= cyclelength - 1).end();
nbaddedcuts++;
} else {
add(sumedges <= cyclelength - 1).end();
nbaddedcuts++;
}
}
std::cout << "revorder: number of violated dicycle constraints : " << nbaddedcuts << std::endl;
std::cout << "revorder: the graph is acyclic " << std::endl;
}
// User branch callback that gives priority to branching on clique variables
ILOBRANCHCALLBACK2(BranchOnCliqueVariables, DiscretizationSolver&, solver, IloCplex::MIPCallbackI::NodeId&, nodeId) {
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
if (getBranchType() != BranchOnVariable)
return;
if (nodeId == getNodeId())
return;
nodeId = getNodeId();
// Branch on the fractionnary clique variable closest to 1
IntegerFeasibilityArray feas;
IloNumArray val;
try {
val = IloNumArray(getEnv());
feas = IntegerFeasibilityArray(getEnv());
getValues(val, solver.isclique_);
getFeasibilities(feas, solver.isclique_);
//
// get the clique variable with maximum integer infeasibility
IloInt bestvar = -1;
IloNum maxval = 0.3;
IloInt cols = solver.isclique_.getSize();
for (IloInt j = 0; j < cols; j++) {
if (feas[j] == Infeasible) {
if (val[j] >= 1 - 1.0e-6) {
bestvar = -1;
break;
}
if (std::min(val[j], 1 - val[j]) > maxval) {
bestvar = j;
maxval = std::min(val[j], 1 - val[j]);
}
} else if (val[j] >= 1 - 1.0e-6) {
bestvar = -1;
break;
}
}
//
// if there is at least one fractionnary clique variable create two branches
if (bestvar >= 0) {
// HeuristicNode* data = new HeuristicNode();
// data->fixcliqueindex(bestvar);
makeBranch(solver.isclique_[bestvar], val[bestvar], IloCplex::BranchUp, getObjValue());
makeBranch(solver.isclique_[bestvar], val[bestvar], IloCplex::BranchDown, getObjValue());
std::cout << "revorder: clique " << bestvar << " bounds " << getLB(solver.isclique_[bestvar]) << " " << getUB(solver.isclique_[bestvar]) << ", value " << val[bestvar] << ", feasibility " << feas[bestvar] << std::endl;
std::cout << "revorder: branch callback: branch on the variable isclique_" << bestvar << std::endl;
#endif
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
}
// else {
// Vertex* bestu = NULL;
// Vertex* bestv = NULL;
// for (Vertex* u : solver.inst_->vertices_) {
// std::map<Vertex*, IloNum> isbeforeval;
// float sumrefs = 0;
// for (Vertex* v : u->neighbors_) {
// isbeforeval[v] = getValue(solver.isbefore_[v][u]);
// sumrefs += isbeforeval[v];
// }
// if (sumrefs == solver.inst_->U()) {
// for (Vertex* v : u->neighbors_) {
// if (getFeasibility(solver.isbefore_[v][u]) == Infeasible) {
// if (std::min(isbeforeval[v], 1 - isbeforeval[v]) > maxval) {
// bestu = u;
// bestv = v;
// maxval = std::min(isbeforeval[v], 1 - isbeforeval[v]);
// }
// }
// }
// }
// }
// if (bestu) {
// // HeuristicNode* data = new HeuristicNode();
// // data->fixcliqueindex(bestvar);
// std::cout << "revorder: branch on isbefore_" << bestv->id_ << "_" << bestu->id_ << std::endl;
// makeBranch(solver.isbefore_[bestv][bestu], getValue(solver.isbefore_[bestv][bestu]), IloCplex::BranchUp, getObjValue());
// makeBranch(solver.isbefore_[bestv][bestu], getValue(solver.isbefore_[bestv][bestu]), IloCplex::BranchDown, getObjValue());
// }
// }
} catch (...) {
val.end();
feas.end();
throw;
}
val.end();
feas.end();
Loading
Loading full blame...