ipchromaticgraph.cpp
3.42 KB
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
#include <iostream>
#include <algorithm>
#include <time.h>
#include <cfloat>
#include "ipchromaticgraph.h"
IpChromaticGraph::IpChromaticGraph (const std::vector < unsigned int >& vertices,
const std::vector < std::pair < unsigned int, unsigned int > >& edges,
unsigned int k,
unsigned int ncores) :
vertices_(vertices), edges_(edges), k_(k)
{
ip_ = new IP(IP::MAX, int(ncores));
size_t i, j, size, size2;
// Creating variables and objective function
for(i=0, size = vertices_.size(); i != size; i++) // vertices
{
varColorUsed_.push_back(ip_->make_variable(0));
varVC_.push_back(std::vector < int > ());
for(j = 0; j != k_; j++) // color
{
varVC_[i].push_back(ip_->make_variable(1.0));
}
}
ip_->update();
// Creating constraints
int row;
// One color per vertex
for(i=0, size = vertices_.size(); i != size; i++)
{
row = ip_->make_constraint(IP::FX, 1.0, 0.0);
for(j = 0; j != k_; j++)
{
ip_->add_constraint(row, varVC_[i][j], 1.0);
}
}
// The color must be different between two adjacent vertices
for(i=0, size = edges_.size(); i != size; i++)
{
for(j = 0; j != k_; j++) // color
{
row = ip_->make_constraint(IP::UP, 0.0, 1.0);
ip_->add_constraint(row, varVC_[edges_[i].first][j], 1.0);
ip_->add_constraint(row, varVC_[edges_[i].second][j], 1.0);
}
}
// varColorUsed is equal to 0 if the color is not used and vice versa
for(i=0, size = vertices_.size(); i != size; i++) // vertices
{
for(j = 0; j != k_; j++) // color
{
row = ip_->make_constraint(IP::UP, 0.0, 0.0);
ip_->add_constraint(row, varVC_[i][j], 1.0);
ip_->add_constraint(row, varColorUsed_[j], -1.0);
}
}
}
int IpChromaticGraph::solve (std::vector < unsigned int >& solution)
{
time_t start, end; // returns elapsed time in sec
double total_time;
start = clock();
int status = ip_->solve();
end = clock();
total_time = double(end - start)/double(CLOCKS_PER_SEC);
printf("\nElapsed time SOLVE IP: %0.3f \n", total_time);
if(status == 0)
{
// Recover decision variable values for sub-graph solution
for (unsigned int i = 0, size = uint(varVC_.size()); i != size; i++)
{
for (unsigned int j = 0; j != k_; j++)
{
if(ip_->get_value(varVC_[i][j]) > 0.5)
solution.push_back(i);
}
}
}
return status;
}
void IpChromaticGraph::add_bj_ct(const std::vector < unsigned int >& solution)
{
int row = ip_->make_constraint(IP::LO, 0.0, 0.0);
int B(0);
bool found;
for (unsigned int i = 0, size = uint(varVC_.size()); i != size; i++)
{
found = false;
if(std::find(solution.begin(), solution.end(), i) != solution.end())
{
B++;
found = true;
}
for(unsigned int j = 0; j != k_; j++)
{
if(found)
{
ip_->add_constraint(row, varVC_[i][j], 1);
B++;
}
else {
ip_->add_constraint(row, varVC_[i][j], -1);
}
}
}
ip_->chg_constraint(row, IP::UP, -DBL_MAX, B-1);
}