| 1 |
/*===========================================================================*/ |
| 2 |
/* */ |
| 3 |
/* This file is part of a demonstration application for use with the */ |
| 4 |
/* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ |
| 5 |
/* the Set Partitioning Problem. */ |
| 6 |
/* */ |
| 7 |
/* (c) Copyright 2005-2013 Marta Eso and Ted Ralphs. All Rights Reserved. */ |
| 8 |
/* */ |
| 9 |
/* This application was originally developed by Marta Eso and was modified */ |
| 10 |
/* Ted Ralphs ([email protected]) */ |
| 11 |
/* */ |
| 12 |
/* This software is licensed under the Eclipse Public License. Please see */ |
| 13 |
/* accompanying file for terms. */ |
| 14 |
/* */ |
| 15 |
/*===========================================================================*/ |
| 16 |
|
| 17 |
#ifndef _SPP_CG_H |
| 18 |
#define _SPP_CG_H |
| 19 |
|
| 20 |
/* system include files */ |
| 21 |
#include <stdio.h> |
| 22 |
#include <sym_proto.h> |
| 23 |
|
| 24 |
/* SPP include files */ |
| 25 |
#include "spp_constants.h" |
| 26 |
#include "spp_types.h" |
| 27 |
#include "spp_cg_params.h" |
| 28 |
|
| 29 |
typedef struct FNODE { /*describes a node of the fractional graph*/ |
| 30 |
int *nbrs; /* pointer into all_nbr */ |
| 31 |
double *edgecosts; /*1-x_i-x_j, needed for odd holes, in the same |
| 32 |
order as the adj list, pointer into |
| 33 |
all_edgecost */ |
| 34 |
int degree; /*degree of the node*/ |
| 35 |
int ind; /*origind of the node, ie. the index of this |
| 36 |
variable in the initial problem the lp and |
| 37 |
the cut generator store*/ |
| 38 |
double val; /*the value of this variable in the current |
| 39 |
lp solution*/ |
| 40 |
}fnode; |
| 41 |
|
| 42 |
typedef struct FRAC_GRAPH { /*graph corresponding to the current fractional |
| 43 |
solution. two nodes are adjacent iff their |
| 44 |
columns are non-orthogonal*/ |
| 45 |
int nodenum; /*# of nodes = # of fractional values in current sol*/ |
| 46 |
int edgenum; /*# of edges in the graph*/ |
| 47 |
double density; /*density= edgenum/(nodenum choose 2)*/ |
| 48 |
int min_deg_node; |
| 49 |
int min_degree; |
| 50 |
int max_deg_node; |
| 51 |
int max_degree; |
| 52 |
fnode *nodes; /*pointers to the nodes*/ |
| 53 |
int *all_nbr; /* array of all the neighbors. */ |
| 54 |
double *all_edgecost; /* array of all the costs */ |
| 55 |
char *node_node; /*node-node incidence matrix of the graph, stored |
| 56 |
row-ordered in a long vector*/ |
| 57 |
}frac_graph; |
| 58 |
|
| 59 |
|
| 60 |
/* a level-graph is derived from another graph by taking one of the nodes |
| 61 |
of the graph as root and listing its connected component in a BFS |
| 62 |
fashion. |
| 63 |
lnodenum is the number of nodes in the level-graph |
| 64 |
levelnum is the number of BFS levels |
| 65 |
root is the root of the level-graph |
| 66 |
lnodes is a list of node indices (wrt the original graph) in the order |
| 67 |
they have been marked during BFS |
| 68 |
lbeg is the position of each level within lnodes (like matbeg for |
| 69 |
matind) |
| 70 |
level_of_node is a list of levels for the nodes of the original graph. |
| 71 |
it is -1 if the node is not in the level-graph (i.e., not |
| 72 |
in the connected component of the root) */ |
| 73 |
typedef struct LEVEL_GRAPH { |
| 74 |
int lnodenum; |
| 75 |
int levelnum; |
| 76 |
int root; /* lnodes[0] = root */ |
| 77 |
int *lnodes; /* length: lnodenum */ |
| 78 |
int *lbeg; /* length: levelnum + 1 */ |
| 79 |
int *level_of_node; /* length: nodenum of orig. graph */ |
| 80 |
}level_graph; |
| 81 |
|
| 82 |
typedef struct CUT_COLLECTION { |
| 83 |
int size; |
| 84 |
int max_size; |
| 85 |
cut_data **cuts; /* a collection of cuts that have been sent |
| 86 |
to the lp */ |
| 87 |
double *violation; /* degree of violation for these cuts */ |
| 88 |
int *mult; /* the multiplicity of the cut -- just STAT */ |
| 89 |
}cut_collection; |
| 90 |
|
| 91 |
typedef struct SPP_CG_TMP { |
| 92 |
int *itmp_m; |
| 93 |
int **istartmp_m; |
| 94 |
/* the following must be reallocated if nodenum grows */ |
| 95 |
int *itmp_8nodenum; |
| 96 |
double *dtmp_2nodenum; |
| 97 |
char *ctmp_2nodenum; |
| 98 |
cut_data *cuttmp; |
| 99 |
}spp_cg_tmp; |
| 100 |
|
| 101 |
|
| 102 |
/* |
| 103 |
tmp: temporary data structures, space is allocated for them only once |
| 104 |
at the beginning and freed at the end only. Some fields are |
| 105 |
variable length |
| 106 |
soln: pointer to the current lp solution. needed only to simplify the |
| 107 |
arguments passed on to functions invoked from find_cuts |
| 108 |
cm_frac, rm_frac: column and row ordered versions of the problem matrix |
| 109 |
restricted to the columns in the fractional solution. matbeg, matind |
| 110 |
and rmatind are variable length. |
| 111 |
fgraph: pointer to the fractional graph that corresponds to the current |
| 112 |
lp solution. Fields are variable length. |
| 113 |
lgraph: a BFS enumeration of a connected component of fgraph, starting from |
| 114 |
a special node, the root. Fields are variable length. |
| 115 |
cut_coll: a local cut pool that contains the cuts that have been sent back |
| 116 |
to the lp. Originally allocated for 20 cuts but it is reallocated |
| 117 |
later as needed. |
| 118 |
|
| 119 |
*/ |
| 120 |
typedef struct SPP_CG_PROBLEM { |
| 121 |
spp_cg_params *par; |
| 122 |
spp_cg_tmp *tmp; |
| 123 |
int dg_id; /* tid of the graph drawing process */ |
| 124 |
char wname[MAX_FILE_NAME_LENGTH +1]; |
| 125 |
/* name of window in which frac solns are displd */ |
| 126 |
char lname[MAX_FILE_NAME_LENGTH +1]; |
| 127 |
/* name of window in which level graph is displd */ |
| 128 |
col_ordered *cmatrix; |
| 129 |
|
| 130 |
int max_sol_length; /* space is allocated for fgraph and |
| 131 |
rmatrix according to this value */ |
| 132 |
col_ordered *cm_frac; |
| 133 |
row_ordered *rm_frac; |
| 134 |
frac_graph *fgraph; |
| 135 |
frac_graph *cfgraph; |
| 136 |
level_graph *lgraph; |
| 137 |
cut_collection *cut_coll; |
| 138 |
|
| 139 |
int *num_cuts; |
| 140 |
int *alloc_cuts; |
| 141 |
cut_data ***cuts; |
| 142 |
|
| 143 |
|
| 144 |
|
| 145 |
}spp_cg_problem; |
| 146 |
|
| 147 |
void allocate_var_length_structures PROTO((spp_cg_problem *spp, int max_ln)); |
| 148 |
void free_var_length_structures PROTO((spp_cg_problem *spp)); |
| 149 |
void construct_fractional_graph PROTO((spp_cg_problem *spp, int number, |
| 150 |
int *indices, double *values)); |
| 151 |
void construct_cm_frac PROTO((spp_cg_problem *spp)); |
| 152 |
void construct_rm_frac PROTO((spp_cg_problem *spp)); |
| 153 |
void construct_complement_graph PROTO((frac_graph *fgraph, |
| 154 |
frac_graph *cfgraph)); |
| 155 |
void construct_level_graph PROTO((frac_graph *fgraph, int root, |
| 156 |
level_graph *lgraph)); |
| 157 |
int register_and_send_cut PROTO((spp_cg_problem *spp, cut_data *new_cut, |
| 158 |
double violation, double etol)); |
| 159 |
|
| 160 |
void extend_clique_on_fgraph PROTO((spp_cg_problem *spp, cut_data *new_cut, |
| 161 |
double *pviolation)); |
| 162 |
void translate_cut_to_indices PROTO((spp_cg_problem *spp, cut_data *cut)); |
| 163 |
void rotate_odd_hole PROTO((int length, int *indices, int *itmp)); |
| 164 |
|
| 165 |
int enumerate_maximal_cliques PROTO((spp_cg_problem *spp, int pos, double etol)); |
| 166 |
void spp_delete_node PROTO((spp_cg_problem *spp, int del_ind, |
| 167 |
int *pcurrent_nodenum, int *current_indices, |
| 168 |
int *current_degrees, double *current_values)); |
| 169 |
int choose_next_node PROTO((spp_cg_problem *spp, int current_nodenum, |
| 170 |
int *current_indices, int *current_degrees, |
| 171 |
double *current_values)); |
| 172 |
int find_violated_star_cliques PROTO((spp_cg_problem *spp, double etol)); |
| 173 |
int find_violated_row_cliques PROTO((spp_cg_problem *spp, double etol)); |
| 174 |
int greedy_maximal_clique PROTO((spp_cg_problem *spp, cut_data *new_cut, |
| 175 |
int length, int *indices, int pos, double etol)); |
| 176 |
int find_violated_odd_holes PROTO((spp_cg_problem *spp, double etol)); |
| 177 |
double find_chordless_oh PROTO((spp_cg_problem *spp, frac_graph *fgraph, |
| 178 |
int u, int w, int *oh)); |
| 179 |
void min_path_to_root PROTO((spp_cg_problem *spp, frac_graph *fgraph, |
| 180 |
int u, int *path_u, double *pcost)); |
| 181 |
double lift_nonviolated_odd_hole PROTO((spp_cg_problem *spp, int oh_len, |
| 182 |
int *oh, double lhs_oh, int *phub_len, |
| 183 |
int *hubs, int *hub_coef)); |
| 184 |
int max_lhs_of_lifted_odd_hole PROTO((spp_cg_problem *spp, int oh_len, |
| 185 |
int *oh, int hub, int hub_len, int *hubs, |
| 186 |
int *hub_coef, char *label, int pos)); |
| 187 |
int find_violated_odd_antiholes PROTO((spp_cg_problem *spp, double etol)); |
| 188 |
double lift_nonviolated_odd_antihole PROTO((spp_cg_problem *spp, int oah_len, |
| 189 |
int *oah, double lhs_oah, |
| 190 |
int *phub_len, int *hubs, |
| 191 |
int *hub_coef, double etol)); |
| 192 |
void translate_cut_to_indices PROTO((spp_cg_problem *spp, cut_data *cut)); |
| 193 |
void rotate_odd_hole PROTO((int length, int *indices, int *itmp)); |
| 194 |
|
| 195 |
#endif |