Debian Codegraph @

SYMPHONY/Applications/MATCH/src/CutGen/user_cg.c

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 Matching Problem. */
6 /* */
7 /* (c) Copyright 2005-2007 Michael Trick and Ted Ralphs. All Rights Reserved.*/
8 /* */
9 /* This application was originally written by Michael Trick and was modified */
10 /* by 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 /* system include files */
18 #include <memory.h>
19 #include <stdio.h>
20
21 /* SYMPHONY include files */
22 #include "sym_constants.h"
23 #include "sym_macros.h"
24 #include "sym_cg_u.h"
25
26 /* MATCH include files */
27 #include "user.h"
28
29 /*===========================================================================*/
30
31 /*===========================================================================*\
32 * This file contains user-written functions used by the cut generator
33 * process.
34 \*===========================================================================*/
35
36 /*===========================================================================*\
37 * Here is where the user must receive all of the data sent from
38 * user_send_cg_data() and set up data structures. Note that this function is
39 * only called if one of COMPILE_IN_CG, COMPILE_IN_LP, or COMPILE_IN_TM is
40 * FALSE. For sequential computation, nothing is needed here.
41 \*===========================================================================*/
42
43 int user_receive_cg_data(void **user, int dg_id)
44 {
45 return(USER_DEFAULT);
46 }
47
48 /*===========================================================================*/
49
50 /*===========================================================================*\
51 * If the user wants to fill in a customized routine for sending and receiving
52 * the LP solution, it can be done here. For most cases, the default routines
53 * are fine.
54 \*===========================================================================*/
55
56 int user_receive_lp_solution_cg(void *user)
57 {
58 return(USER_DEFAULT);
59 }
60
61 /*===========================================================================*/
62
63 /*===========================================================================*\
64 * Find cuts violated by a particular LP solution. This can be a fairly
65 * involved function but the bottom line is that an LP solution comes in
66 * and cuts go out. Remember, use the function cg_send_cut() to send cuts out
67 * when they are found.
68 \*===========================================================================*/
69
70 int user_find_cuts(void *user, int varnum, int iter_num, int level,
71 int index, double objval, int *indices, double *values,
72 double ub, double etol, int *num_cuts, int *alloc_cuts,
73 cut_data ***cuts)
74 {
75
76 #if 1
77
78 /* Here, we demonstrate how to add an explicit cut that doesn't have a
79 special packed form. This is the easiest way to add cuts, but may be
80 inefficient in parallel. */
81
82 user_problem *prob = (user_problem *) user;
83 double edge_val[200][200]; /* Matrix of edge values */
84 int i, j, k, cutind[3];
85 double cutval[3];
86
87 int cutnum = 0;
88
89 /* Allocate the edge_val matrix to zero (we could also just calloc it) */
90 memset((char *)edge_val, 0, 200*200*ISIZE);
91
92 for (i = 0; i < varnum; i++) {
93 edge_val[prob->match1[indices[i]]][prob->match2[indices[i]]] = values[i];
94 }
95
96 for (i = 0; i < prob->numnodes; i++){
97 for (j = i+1; j < prob->numnodes; j++){
98 for (k = j+1; k < prob->numnodes; k++) {
99 if (edge_val[i][j]+edge_val[j][k]+edge_val[i][k] > 1.0 + etol) {
100 /* Found violated triangle cut */
101 /* Form the cut as a sparse vector */
102 cutind[0] = prob->index[i][j];
103 cutind[1] = prob->index[j][k];
104 cutind[2] = prob->index[i][k];
105 cutval[0] = cutval[1] = cutval[2] = 1.0;
106 cg_add_explicit_cut(3, cutind, cutval, 1.0, 0, 'L',
107 TRUE, num_cuts, alloc_cuts, cuts);
108 cutnum++;
109
110 }
111 }
112 }
113 }
114
115 #else
116 /* Here, we show how to use a user-defined cut class with a packed form. In
117 this case, the packed form is just to store the three nodes that form
118 the triangle. See the function user_unpack_cuts() for the code to unpack
119 the cut. */
120 user_problem *prob = (user_problem *) user;
121 double edge_val[200][200]; /* Matrix of edge values */
122 int i, j, k;
123 int *new_cuts;
124 cut_data cut;
125 int coef[3];
126
127 int cutnum = 0;
128
129 /* Allocate the edge_val matrix to zero (we could also just calloc it) */
130 memset((char *)edge_val, 0, 200*200*ISIZE);
131
132 for (i = 0; i < varnum; i++) {
133 edge_val[prob->match1[indices[i]]][prob->match2[indices[i]]]
134 = values[i];
135 }
136 for (i = 0; i < prob->numnodes; i++){
137 for (j = i+1; j < prob->numnodes; j++){
138 for (k = j+1; k < prob->numnodes; k++) {
139 if (edge_val[i][j]+edge_val[j][k]+edge_val[i][k] > 1.0 + etol) {
140 memset(new_cuts, 0, prob->numnodes * ISIZE);
141 coef[1] = i;
142 coef[2] = j;
143 coef[3] = k;
144 cut.size = 3*ISIZE;
145 cut.coef = (char *) coef;
146 cut.rhs = 1.0;
147 cut.range = 0.0;
148 cut.type = TRIANGLE;
149 cut.sense = 'L';
150 cut.deletable = TRUE;
151 cut.branch = ALLOWED_TO_BRANCH_ON;
152 cg_add_user_cut(&cut, num_cuts, alloc_cuts, cuts);
153 cutnum++;
154
155 }
156 }
157 }
158 }
159
160 FREE(new_cuts);
161 #endif
162
163 return(USER_SUCCESS);
164 }
165
166 /*===========================================================================*/
167
168 /*===========================================================================*\
169 * Free the user data structure. If the default setup is used with sequential
170 * computation, nothing needs to be filled in here.
171 \*===========================================================================*/
172
173 int user_free_cg(void **user)
174 {
175 return(USER_DEFAULT);
176 }
177
178 /*===========================================================================*/
179
180 /*===========================================================================*\
181 * This is an undocumented (for now) debugging feature which can allow the user
182 * to identify the cut which cuts off a particular known feasible solution.
183 \*===========================================================================*/
184
185 #ifdef CHECK_CUT_VALIDITY
186 int user_check_validity_of_cut(void *user, cut_data *new_cut)
187 {
188 return(USER_DEFAULT);
189 }
190 #endif