/
spp_cg.h
195 lines (174 loc) · 8.69 KB
/
spp_cg.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
/*===========================================================================*/
/* */
/* This file is part of a demonstration application for use with the */
/* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
/* the Set Partitioning Problem. */
/* */
/* (c) Copyright 2005-2013 Marta Eso and Ted Ralphs. All Rights Reserved. */
/* */
/* This application was originally developed by Marta Eso and was modified */
/* Ted Ralphs (ted@lehigh.edu) */
/* */
/* This software is licensed under the Eclipse Public License. Please see */
/* accompanying file for terms. */
/* */
/*===========================================================================*/
#ifndef _SPP_CG_H
#define _SPP_CG_H
/* system include files */
#include <stdio.h>
#include <sym_proto.h>
/* SPP include files */
#include "spp_constants.h"
#include "spp_types.h"
#include "spp_cg_params.h"
typedef struct FNODE { /*describes a node of the fractional graph*/
int *nbrs; /* pointer into all_nbr */
double *edgecosts; /*1-x_i-x_j, needed for odd holes, in the same
order as the adj list, pointer into
all_edgecost */
int degree; /*degree of the node*/
int ind; /*origind of the node, ie. the index of this
variable in the initial problem the lp and
the cut generator store*/
double val; /*the value of this variable in the current
lp solution*/
}fnode;
typedef struct FRAC_GRAPH { /*graph corresponding to the current fractional
solution. two nodes are adjacent iff their
columns are non-orthogonal*/
int nodenum; /*# of nodes = # of fractional values in current sol*/
int edgenum; /*# of edges in the graph*/
double density; /*density= edgenum/(nodenum choose 2)*/
int min_deg_node;
int min_degree;
int max_deg_node;
int max_degree;
fnode *nodes; /*pointers to the nodes*/
int *all_nbr; /* array of all the neighbors. */
double *all_edgecost; /* array of all the costs */
char *node_node; /*node-node incidence matrix of the graph, stored
row-ordered in a long vector*/
}frac_graph;
/* a level-graph is derived from another graph by taking one of the nodes
of the graph as root and listing its connected component in a BFS
fashion.
lnodenum is the number of nodes in the level-graph
levelnum is the number of BFS levels
root is the root of the level-graph
lnodes is a list of node indices (wrt the original graph) in the order
they have been marked during BFS
lbeg is the position of each level within lnodes (like matbeg for
matind)
level_of_node is a list of levels for the nodes of the original graph.
it is -1 if the node is not in the level-graph (i.e., not
in the connected component of the root) */
typedef struct LEVEL_GRAPH {
int lnodenum;
int levelnum;
int root; /* lnodes[0] = root */
int *lnodes; /* length: lnodenum */
int *lbeg; /* length: levelnum + 1 */
int *level_of_node; /* length: nodenum of orig. graph */
}level_graph;
typedef struct CUT_COLLECTION {
int size;
int max_size;
cut_data **cuts; /* a collection of cuts that have been sent
to the lp */
double *violation; /* degree of violation for these cuts */
int *mult; /* the multiplicity of the cut -- just STAT */
}cut_collection;
typedef struct SPP_CG_TMP {
int *itmp_m;
int **istartmp_m;
/* the following must be reallocated if nodenum grows */
int *itmp_8nodenum;
double *dtmp_2nodenum;
char *ctmp_2nodenum;
cut_data *cuttmp;
}spp_cg_tmp;
/*
tmp: temporary data structures, space is allocated for them only once
at the beginning and freed at the end only. Some fields are
variable length
soln: pointer to the current lp solution. needed only to simplify the
arguments passed on to functions invoked from find_cuts
cm_frac, rm_frac: column and row ordered versions of the problem matrix
restricted to the columns in the fractional solution. matbeg, matind
and rmatind are variable length.
fgraph: pointer to the fractional graph that corresponds to the current
lp solution. Fields are variable length.
lgraph: a BFS enumeration of a connected component of fgraph, starting from
a special node, the root. Fields are variable length.
cut_coll: a local cut pool that contains the cuts that have been sent back
to the lp. Originally allocated for 20 cuts but it is reallocated
later as needed.
*/
typedef struct SPP_CG_PROBLEM {
spp_cg_params *par;
spp_cg_tmp *tmp;
int dg_id; /* tid of the graph drawing process */
char wname[MAX_FILE_NAME_LENGTH +1];
/* name of window in which frac solns are displd */
char lname[MAX_FILE_NAME_LENGTH +1];
/* name of window in which level graph is displd */
col_ordered *cmatrix;
int max_sol_length; /* space is allocated for fgraph and
rmatrix according to this value */
col_ordered *cm_frac;
row_ordered *rm_frac;
frac_graph *fgraph;
frac_graph *cfgraph;
level_graph *lgraph;
cut_collection *cut_coll;
int *num_cuts;
int *alloc_cuts;
cut_data ***cuts;
}spp_cg_problem;
void allocate_var_length_structures PROTO((spp_cg_problem *spp, int max_ln));
void free_var_length_structures PROTO((spp_cg_problem *spp));
void construct_fractional_graph PROTO((spp_cg_problem *spp, int number,
int *indices, double *values));
void construct_cm_frac PROTO((spp_cg_problem *spp));
void construct_rm_frac PROTO((spp_cg_problem *spp));
void construct_complement_graph PROTO((frac_graph *fgraph,
frac_graph *cfgraph));
void construct_level_graph PROTO((frac_graph *fgraph, int root,
level_graph *lgraph));
int register_and_send_cut PROTO((spp_cg_problem *spp, cut_data *new_cut,
double violation, double etol));
void extend_clique_on_fgraph PROTO((spp_cg_problem *spp, cut_data *new_cut,
double *pviolation));
void translate_cut_to_indices PROTO((spp_cg_problem *spp, cut_data *cut));
void rotate_odd_hole PROTO((int length, int *indices, int *itmp));
int enumerate_maximal_cliques PROTO((spp_cg_problem *spp, int pos, double etol));
void spp_delete_node PROTO((spp_cg_problem *spp, int del_ind,
int *pcurrent_nodenum, int *current_indices,
int *current_degrees, double *current_values));
int choose_next_node PROTO((spp_cg_problem *spp, int current_nodenum,
int *current_indices, int *current_degrees,
double *current_values));
int find_violated_star_cliques PROTO((spp_cg_problem *spp, double etol));
int find_violated_row_cliques PROTO((spp_cg_problem *spp, double etol));
int greedy_maximal_clique PROTO((spp_cg_problem *spp, cut_data *new_cut,
int length, int *indices, int pos, double etol));
int find_violated_odd_holes PROTO((spp_cg_problem *spp, double etol));
double find_chordless_oh PROTO((spp_cg_problem *spp, frac_graph *fgraph,
int u, int w, int *oh));
void min_path_to_root PROTO((spp_cg_problem *spp, frac_graph *fgraph,
int u, int *path_u, double *pcost));
double lift_nonviolated_odd_hole PROTO((spp_cg_problem *spp, int oh_len,
int *oh, double lhs_oh, int *phub_len,
int *hubs, int *hub_coef));
int max_lhs_of_lifted_odd_hole PROTO((spp_cg_problem *spp, int oh_len,
int *oh, int hub, int hub_len, int *hubs,
int *hub_coef, char *label, int pos));
int find_violated_odd_antiholes PROTO((spp_cg_problem *spp, double etol));
double lift_nonviolated_odd_antihole PROTO((spp_cg_problem *spp, int oah_len,
int *oah, double lhs_oah,
int *phub_len, int *hubs,
int *hub_coef, double etol));
void translate_cut_to_indices PROTO((spp_cg_problem *spp, cut_data *cut));
void rotate_odd_hole PROTO((int length, int *indices, int *itmp));
#endif