Debian Codegraph @

SYMPHONY/Applications/SPP+CUTS/include/spp_cg.h

raw
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