1 /*===========================================================================*/
2 /* */
3 /* This file is part of the SYMPHONY MILP Solver Framework. */
4 /* */
5 /* SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and */
6 /* Laci Ladanyi (ladanyi@us.ibm.com). */
7 /* */
8 /* (c) Copyright 2000-2019 Ted Ralphs. All Rights Reserved. */
9 /* */
10 /* This software is licensed under the Eclipse Public License. Please see */
11 /* accompanying file for terms. */
12 /* */
13 /*===========================================================================*/
14
15 #include <stdlib.h>
16 #include <string.h>
17 #include <stdio.h>
18
19 #include "sym_pack_cut.h"
20 #include "sym_messages.h"
21 #include "sym_proccomm.h"
22 #include "sym_timemeas.h"
23 #include "sym_constants.h"
24 #include "sym_macros.h"
25 #include "sym_cg.h"
26
27 /*===========================================================================*/
28
29 /*===========================================================================*\
30 * This file contains general functions used by the cut generator process.
31 \*===========================================================================*/
32
33 /*===========================================================================*/
34
35 /*===========================================================================*\
36 * This function receives the problem data (if we are running in parallel)
37 * and intitializes the data structures.
38 \*===========================================================================*/
39
40
cg_initialize(cg_prob * p,int master_tid)41 void cg_initialize(cg_prob *p, int master_tid)
42 {
43 #ifndef COMPILE_IN_CG
44 int bytes, msgtag;
45 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP)
46 int s_bufid, r_bufid, info;
47 #endif
48 #endif
49 #if !defined(COMPILE_IN_TM) || !defined(COMPILE_IN_LP)
50 int r_bufid, s_bufid = 0;
51 #endif
52
53 /*------------------------------------------------------------------------
54 * Receive the problem data
55 *------------------------------------------------------------------------*/
56
57 #ifdef COMPILE_IN_CG
58
59 p->master = master_tid;
60
61 #else
62
63 /* We only need to do this part if the CG is running as a separate process*/
64 /* Otherwise, all of this setup is done in the master in the function */
65 /* pack_cg_data_u()*/
66
67 /* set stdout to be line buffered */
68 setvbuf(stdout, (char *)NULL, _IOLBF, 0);
69
70 register_process();
71
72 r_bufid = receive_msg(ANYONE, MASTER_TID_INFO);
73 bufinfo(r_bufid, &bytes, &msgtag, &p->tree_manager);
74 receive_int_array(&p->master, 1);
75 receive_int_array(&p->proc_index, 1);
76 freebuf(r_bufid);
77
78 #endif
79
80 #if !defined(COMPILE_IN_TM) || !defined(COMPILE_IN_LP) || \
81 !defined(COMPILE_IN_CG)
82
83 /* This part, we only need to do if we are not running in full serial mode*/
84
85 s_bufid = init_send(DataInPlace);
86 send_msg(p->master, REQUEST_FOR_CG_DATA);
87 freebuf(s_bufid);
88
89 receive_cg_data_u(p);
90
91 #endif
92
93 (void) used_time(&p->tt);
94 }
95
96 /*===========================================================================*/
97
98 /*===========================================================================*\
99 * This function is provided for the user to send cuts. This function is
100 * retained for backwards compatibility, but is deprecated. See
101 * cg_add_user_cut() below.
102 \*===========================================================================*/
103
cg_send_cut(cut_data * new_cut,int * num_cuts,int * alloc_cuts,cut_data *** cuts)104 int cg_send_cut(cut_data *new_cut, int *num_cuts, int *alloc_cuts,
105 cut_data ***cuts)
106 {
107 #ifdef COMPILE_IN_CG
108
109 int i;
110 cut_data *tmp_cut;
111
112 for (i = 0; i < *num_cuts; i++){
113 if (new_cut->type != (*cuts)[i]->type ||
114 new_cut->size != (*cuts)[i]->size ||
115 new_cut->rhs != (*cuts)[i]->rhs){
116 continue;
117 }
118 if (!new_cut->coef){
119 return(0);
120 }
121 if (memcmp(new_cut->coef, (*cuts)[i]->coef,
122 new_cut->size) == 0){
123 return(0);
124 }
125 }
126 if (new_cut->name != CUT__DO_NOT_SEND_TO_CP)
127 new_cut->name = CUT__SEND_TO_CP;
128 tmp_cut = (cut_data *) malloc (sizeof(cut_data));
129 memcpy((char *)tmp_cut, (char *)new_cut, sizeof(cut_data));
130 if (new_cut->size >0){
131 tmp_cut->coef = (char *) malloc (new_cut->size * sizeof(char));
132 memcpy((char *)tmp_cut->coef, (char *)new_cut->coef,
133 new_cut->size * sizeof(char));
134 }
135 REALLOC((*cuts), cut_data *, (*alloc_cuts), (*num_cuts + 1), BB_BUNCH);
136 (*cuts)[(*num_cuts)++] = tmp_cut;
137
138 #else
139
140 int s_bufid;
141
142 if (new_cut->name != CUT__DO_NOT_SEND_TO_CP)
143 new_cut->name = CUT__SEND_TO_CP;
144 s_bufid = init_send(DataInPlace);
145 pack_cut(new_cut);
146 send_msg(p->cur_sol.lp, PACKED_CUT);
147 freebuf(s_bufid);
148
149 #endif
150
151 return(1);
152 }
153
154 /*===========================================================================*/
155
create_explicit_cut(int nzcnt,int * indices,double * values,double rhs,double range,char sense,char send_to_cp)156 cut_data *create_explicit_cut(int nzcnt, int *indices, double *values,
157 double rhs, double range, char sense,
158 char send_to_cp)
159 {
160 cut_data *cut = (cut_data *) calloc(1, sizeof(cut_data));
161
162 cut->type = EXPLICIT_ROW;
163 cut->sense = sense;
164 cut->rhs = rhs;
165 cut->range = range;
166 cut->size = (int)(DSIZE + nzcnt * (ISIZE + DSIZE));
167 cut->coef = (char *) malloc (cut->size);
168 ((double *) cut->coef)[0] = 0; // otherwise valgrind complains
169 ((int *) cut->coef)[0] = nzcnt;
170 //Here, we have to pad the initial int to avoid misalignment, so we
171 //add DSIZE bytes to get to a double boundary
172 memcpy(cut->coef + DSIZE, (char *)values, nzcnt * DSIZE);
173 memcpy(cut->coef + (nzcnt + 1) * DSIZE, (char *)indices, nzcnt*ISIZE);
174 cut->branch = DO_NOT_BRANCH_ON_THIS_ROW;
175 cut->deletable = TRUE;
176 cut->name = send_to_cp ? CUT__SEND_TO_CP : CUT__DO_NOT_SEND_TO_CP;
177
178 return(cut);
179 }
180
181 /*===========================================================================*/
182
cg_add_explicit_cut(int nzcnt,int * indices,double * values,double rhs,double range,char sense,char send_to_cp,int * num_cuts,int * alloc_cuts,cut_data *** cuts)183 int cg_add_explicit_cut(int nzcnt, int *indices, double *values,
184 double rhs, double range, char sense,
185 char send_to_cp, int *num_cuts, int *alloc_cuts,
186 cut_data ***cuts)
187 {
188 cut_data *cut = (cut_data *) calloc(1, sizeof(cut_data));
189
190 cut->type = EXPLICIT_ROW;
191 cut->sense = sense;
192 cut->rhs = rhs;
193 cut->range = range;
194 cut->size = (int)(DSIZE + nzcnt * (ISIZE + DSIZE));
195 cut->coef = (char *) malloc (cut->size);
196 ((double *) cut->coef)[0] = 0; // otherwise valgrind complains.
197 ((int *) cut->coef)[0] = nzcnt;
198 //Here, we have to pad the initial int to avoid misalignment, so we
199 //add DSIZE bytes to get to a double boundary
200 memcpy(cut->coef + DSIZE, (char *)values, nzcnt * DSIZE);
201 memcpy(cut->coef + (nzcnt + 1) * DSIZE, (char *)indices, nzcnt*ISIZE);
202 cut->branch = DO_NOT_BRANCH_ON_THIS_ROW;
203 cut->deletable = TRUE;
204 cut->name = send_to_cp ? CUT__SEND_TO_CP : CUT__DO_NOT_SEND_TO_CP;
205
206 return(cg_add_user_cut(cut, num_cuts, alloc_cuts, cuts));
207 }
208
209 /*===========================================================================*/
210
cg_add_user_cut(cut_data * new_cut,int * num_cuts,int * alloc_cuts,cut_data *** cuts)211 int cg_add_user_cut(cut_data *new_cut, int *num_cuts, int *alloc_cuts,
212 cut_data ***cuts)
213 {
214 #ifdef COMPILE_IN_CG
215
216 int i;
217 cut_data *tmp_cut;
218
219 for (i = 0; i < *num_cuts; i++){
220 if (new_cut->size != (*cuts)[i]->size){
221 continue;
222 }
223 if (memcmp(new_cut->coef, (*cuts)[i]->coef, new_cut->size) == 0){
224 return(0);
225 }
226 }
227 if (new_cut->name != CUT__DO_NOT_SEND_TO_CP)
228 new_cut->name = CUT__SEND_TO_CP;
229 tmp_cut = (cut_data *) malloc (sizeof(cut_data));
230 memcpy((char *)tmp_cut, (char *)new_cut, sizeof(cut_data));
231 if (new_cut->size >0){
232 tmp_cut->coef = (char *) malloc (new_cut->size * sizeof(char));
233 memcpy((char *)tmp_cut->coef, (char *)new_cut->coef,
234 new_cut->size * sizeof(char));
235 }
236 REALLOC((*cuts), cut_data *, (*alloc_cuts), (*num_cuts + 1), BB_BUNCH);
237 (*cuts)[(*num_cuts)++] = tmp_cut;
238
239 #else
240
241 int s_bufid;
242
243 if (new_cut->name != CUT__DO_NOT_SEND_TO_CP)
244 new_cut->name = CUT__SEND_TO_CP;
245 s_bufid = init_send(DataInPlace);
246 pack_cut(new_cut);
247 send_msg(p->cur_sol.lp, PACKED_CUT);
248 freebuf(s_bufid);
249
250 #endif
251
252 return(1);
253 }
254
255 /*===========================================================================*/
256
257 /*===========================================================================*\
258 * This function frees data structures
259 \*===========================================================================*/
260
cg_close(cg_prob * p)261 void cg_close(cg_prob *p)
262 {
263 free_cg_u(p);
264 }
265