Limbo
|
#include <LPColoring.h>
Classes | |
struct | ConstrVariableInfo |
information for a variable of a constraint More... | |
struct | NonIntegerInfo |
records the information of non-integer values More... | |
Public Types | |
typedef Coloring< GraphType > | base_type |
typedef base_type::graph_type | graph_type |
typedef base_type::graph_vertex_type | graph_vertex_type |
typedef base_type::graph_edge_type | graph_edge_type |
typedef base_type::vertex_iterator_type | vertex_iterator_type |
typedef base_type::edge_iterator_type | edge_iterator_type |
typedef base_type::edge_weight_type | edge_weight_type |
typedef base_type::EdgeHashType | edge_hash_type |
Public Types inherited from limbo::algorithms::coloring::Coloring< GraphType > | |
enum | ColorNumType { THREE = 3, FOUR = 4 } |
number of colors | |
typedef GraphType | graph_type |
typedef boost::graph_traits < graph_type > ::vertex_descriptor | graph_vertex_type |
typedef boost::graph_traits < graph_type > ::edge_descriptor | graph_edge_type |
typedef boost::graph_traits < graph_type > ::vertex_iterator | vertex_iterator_type |
typedef boost::graph_traits < graph_type >::edge_iterator | edge_iterator_type |
typedef boost::property_traits < typename boost::property_map < graph_type, boost::edge_weight_t > ::const_type >::value_type | edge_weight_type |
typedef boost::property_traits < typename boost::property_map < graph_type, boost::edge_index_t > ::const_type >::value_type | edge_index_type |
Public Member Functions | |
LPColoring (graph_type const &g) | |
constructor More... | |
~LPColoring () | |
destructor | |
uint32_t | lp_iters () const |
void | print_solution (vector< GRBVar > const &vColorBits) const |
Public Member Functions inherited from limbo::algorithms::coloring::Coloring< GraphType > | |
Coloring (graph_type const &g) | |
virtual | ~Coloring () |
destructor | |
virtual double | operator() () |
virtual void | color_num (ColorNumType cn) |
virtual void | color_num (int8_t cn) |
virtual ColorNumType | color_num () const |
virtual void | precolor (graph_vertex_type v, int8_t c) |
virtual bool | has_precolored () const |
virtual double | stitch_weight () const |
virtual void | stitch_weight (double w) |
virtual void | threads (int32_t t) |
virtual int8_t | color (graph_vertex_type v) const |
virtual edge_weight_type | edge_weight (graph_edge_type const &e) const |
virtual edge_weight_type | calc_cost (std::vector< int8_t > const &vColor) const |
void | check_edge_weight (graph_type const &g, edge_weight_type lb, edge_weight_type ub) const |
void | print_edge_weight (graph_type const &g) const |
virtual void | write_graph (std::string const &filename) const |
virtual void | write_graph (std::string const &filename, graph_type const &g, std::vector< int8_t > const &vColor) const |
Protected Member Functions | |
double | coloring () |
void | apply_solution (vector< GRBVar > const &vColorBits) |
void | initialize () |
create the NoStitchGraph (this->m_graph) from the (m_conflict_graph) | |
void | set_optimize_model (vector< GRBVar > &vColorBits, vector< GRBVar > &vEdgeBits, GRBLinExpr &obj, GRBModel &optModel) |
void | set_anchor (vector< GRBVar > &vColorBits) const |
void | adjust_variable_pair_in_objective (vector< GRBVar > const &vColorBits, GRBLinExpr &obj) const |
tune objective for each color bit pair of vertex More... | |
void | adjust_conflict_edge_vertices_in_objective (vector< GRBVar > const &vColorBits, GRBLinExpr &obj) const |
tune objective for each color bit pair along conflict edges More... | |
void | add_odd_cycle_constraints (vector< GRBVar > const &vColorBits, GRBModel &optModel) |
odd cycle trick from Prof. Baldick More... | |
void | solve_model (GRBModel &optModel) |
solve model More... | |
void | get_odd_cycles (graph_vertex_type const &v, vector< vector< graph_vertex_type > > &vOddCyle) |
graph_vertex_type | max_degree_vertex () const |
void | rounding_with_binding_analysis (GRBModel &optModel, vector< GRBVar > &vColorBits, vector< GRBVar > &vEdgeBits) |
uint32_t | post_refinement () |
greedy final coloring refinement | |
bool | refine_color (graph_edge_type const &e) |
void | non_integer_num (vector< GRBVar > const &vColorBits, vector< GRBVar > const &vEdgeBits, NonIntegerInfo &info) const |
void | non_integer_num (vector< GRBVar > const &vVariables, uint32_t &nonIntegerNum, uint32_t &halfIntegerNum) const |
bool | is_integer (double value) const |
uint32_t | check_precolored_num (vector< LPColoring< GraphType >::graph_vertex_type > const &vVertex) const |
Protected Attributes | |
boost::dynamic_bitset | m_vVertexHandledByOddCycle |
members More... | |
uint32_t | m_constrs_num |
record number of constraints | |
uint32_t | m_lp_iters |
record lp iterations | |
Protected Attributes inherited from limbo::algorithms::coloring::Coloring< GraphType > | |
graph_type const & | m_graph |
initial graph | |
std::vector< int8_t > | m_vColor |
coloring solutions | |
ColorNumType | m_color_num |
number of colors | |
double | m_stitch_weight |
stitch weight | |
int32_t | m_threads |
control number of threads for ILP solver | |
bool | m_has_precolored |
whether contain precolored vertices | |
LP based graph coloring.
GraphType | graph type |
Definition at line 67 of file LPColoring.h.
limbo::algorithms::coloring::LPColoring< GraphType >::LPColoring | ( | graph_type const & | g | ) |
|
protected |
odd cycle trick from Prof. Baldick
odd cycle constraints from Prof. Baldick
vColorBits | vertex bits of LP |
optModel | LP model |
Definition at line 511 of file LPColoring.h.
|
protected |
tune objective for each color bit pair along conflict edges
for each color bit pair of vertices of an edge
vColorBits | vertex bits of LP |
obj | objective of LP |
Definition at line 484 of file LPColoring.h.
|
protected |
tune objective for each color bit pair of vertex
for each color bit pair of a vertex
vColorBits | vertex bits of LP |
obj | objective of LP |
Definition at line 466 of file LPColoring.h.
|
protected |
apply coloring solution
vColorBits | LP solutions |
Definition at line 675 of file LPColoring.h.
|
protected |
check number of precolored vertices
vVertex | vertices of the graph |
Definition at line 911 of file LPColoring.h.
|
protectedvirtual |
kernel coloring algorithm; relaxed linear programming based coloring for the conflict graph (this->m_graph)
Implements limbo::algorithms::coloring::Coloring< GraphType >.
Definition at line 579 of file LPColoring.h.
|
protected |
DFS to search for the odd cycles, stored in m_odd_cycles
v | vertex |
vOddCyle | container to store odd cycles |
Definition at line 239 of file LPColoring.h.
|
inlineprotected |
check if a variable is integer or not
value | target value to be checked |
Definition at line 214 of file LPColoring.h.
|
inline |
Definition at line 138 of file LPColoring.h.
|
protected |
Definition at line 332 of file LPColoring.h.
|
protected |
compute number of non-integers and half-integers for both vertex variables and edge variables
vColorBits | vertex bits of LP |
vEdgeBits | edge bits of LP |
info | non-integer information |
|
protected |
compute number of non-integers and half-integers with given variable array
vVariables | variables |
nonIntegerNum | number of non-integers |
halfIntegerNum | number of half-integers |
void limbo::algorithms::coloring::LPColoring< GraphType >::print_solution | ( | vector< GRBVar > const & | vColorBits | ) | const |
|
protected |
refine coloring solution of an edge
e | edge |
Definition at line 819 of file LPColoring.h.
|
protected |
Optimal rounding based on binding constraints
optModel | LP model |
vColorBits | vertex bits of LP |
vEdgeBits | edge bits of LP |
optimal rounding based on the binding analysis but only a part of all vertices can be rounded
Definition at line 691 of file LPColoring.h.
|
protected |
set anchor vertex
vColorBits | vertex bits of LP |
Definition at line 451 of file LPColoring.h.
|
protected |
create basic variables, objective and constraints
vColorBits | vertex bits of LP |
vEdgeBits | edge bits of LP |
obj | objective of LP |
optModel | LP model |
Definition at line 350 of file LPColoring.h.
|
protected |
|
protected |
members
record whether a vertex has already been handled by an odd cycle
Definition at line 222 of file LPColoring.h.