4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 #include "sp_matrix.h"
19 typedef struct _name_t name_t;
22 const char *name; /**< the name of the var/constraint supplied by user */
23 int nr; /**< the col/row number in the matrix */
31 /* The problem data */
32 char *name; /**< A textual name for this problem */
33 opt_t opt_type; /**< Optimization direction */
34 sp_matrix_t *m; /**< The matrix holding objective and constraints */
35 int rhs_size; /**< Size of the rhs-array below */
36 int *rhs; /**< The right hand side vector */
38 /* Cst/Var to Nr mapping */
39 set *cst2nr; /**< Holds name_t's for constraints */
40 set *var2nr; /**< Holds name_t's for variables */
42 /* Nr to Cst/Var mapping */
43 int cst_size, var_size; /**< Size of the csts/vars-arrays below */
44 int cst_next, var_next; /**< Next free position in arrays below */
45 name_t **csts; /**< Pointers to the elements in the cst2nr set */
46 name_t **vars; /**< Pointers to the elements in the var2nr set */
49 #define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
51 static int cmp_name_t(const void *x, const void *y, size_t size) {
54 return strcmp(n->name, m->name);
57 #define INITIAL_SIZE 64
59 lpp_t *new_lp(char *name, opt_t opt_type) {
60 lpp_t *lpp = xcalloc(1, sizeof(*lpp));
62 lpp->opt_type = opt_type;
63 lpp->cst2nr = new_set(cmp_name_t, INITIAL_SIZE);
64 lpp->var2nr = new_set(cmp_name_t, INITIAL_SIZE);
65 lpp->cst_size = INITIAL_SIZE;
66 lpp->csts = xcalloc(INITIAL_SIZE, sizeof(*lpp->csts));
67 lpp->var_size = INITIAL_SIZE;
68 lpp->vars = xcalloc(INITIAL_SIZE, sizeof(*lpp->vars));
69 lpp->m = new_matrix(INITIAL_SIZE, INITIAL_SIZE);
70 lpp->rhs_size = INITIAL_SIZE;
71 lpp->rhs = xcalloc(INITIAL_SIZE, sizeof(*lpp->rhs));
75 void free_lp(lpp_t *lpp) {
85 void lpp_add_constr(lpp_t *lpp, const char *cst_name, cst_t cst_type) {
87 n.name = xstrdup(cst_name);
88 n.nr = lpp->cst_next++;
89 n.type.cst_type = cst_type;
90 inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
92 if (lpp->cst_next == lpp->cst_size)
93 lpp->csts = xrealloc(lpp->csts, 2 * lpp->cst_size * sizeof(*lpp->csts));
94 lpp->csts[lpp->cst_next++] = inner;
97 void lpp_add_var(lpp_t *lpp, const char *var_name, var_t var_type) {
99 assert(var_type != invalid && "invalid is for internal use only");
100 n.name = xstrdup(var_name);
101 n.nr = lpp->var_next++;
102 n.type.var_type = var_type;
103 inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
105 if (lpp->var_next == lpp->var_size)
106 lpp->vars = xrealloc(lpp->vars, 2 * lpp->var_size * sizeof(*lpp->vars));
107 lpp->vars[lpp->var_next++] = inner;
110 static INLINE int name2nr(set *where, const char *name) {
113 found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find));
120 #define cst_nr(lp, name) name2nr(lpp->cst2nr, name)
121 #define var_nr(lp, name) name2nr(lpp->var2nr, name)
123 void lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, int value) {
125 cst = cst_nr(lp, cst_name);
126 var = var_nr(lp, var_name);
129 matrix_set(lpp->m, cst, var, value);
132 static INLINE void adjust_rhs_size(lpp_t *lpp) {
133 if (lpp->cst_size > lpp->rhs_size) {
134 lpp->rhs_size = lpp->cst_size;
135 lpp->rhs = xrealloc(lpp->rhs, lpp->rhs_size);
139 void lpp_set_rhs(lpp_t *lpp, char *cst_name, int value) {
140 int cst = cst_nr(lp, cst_name);
142 adjust_rhs_size(lpp);
143 lpp->rhs[cst] = value;
146 void lpp_set_all_constr(lpp_t *lpp, char *cst_name, char **var_names, int *values) {
150 /******************************************************************************
152 ******************************************************************************/
154 static char *mps_cst_encoding[4] = {"N", "E", "L", "G"};
155 typedef enum _mps_line_t {l_raw,
156 l_ind_name, l_ind_objs, l_ind_rows, l_ind_cols, l_ind_rhs, l_ind_end,
157 l_data_row, l_data_col1, l_data_col2, l_marker} mps_line_t;
159 static INLINE void mps_write_line(FILE *out, style_t style, mps_line_t line_type, ...) {
163 assert(style == s_mps_fixed || style == s_mps_free);
164 va_start(args, line_type);
166 if (style == s_mps_fixed) {
167 /* white spaces are important! */
169 case l_raw: fmt = "%s\n"; break;
170 case l_ind_name: fmt = "NAME %s\n"; break;
171 case l_ind_objs: fmt = "OBJSENSE\n"; break;
172 case l_ind_rows: fmt = "ROWS\n"; break;
173 case l_ind_cols: fmt = "COLUMNS\n"; break;
174 case l_ind_rhs: fmt = "RHS\n"; break;
175 case l_ind_end: fmt = "ENDATA\n"; break;
176 case l_data_row: fmt = " %-2s %-8s\n"; break; /* Field 1-2 */
177 case l_data_col1: fmt = " %-8s %-8s %12d\n"; break; /* Field 2-4 */
178 case l_data_col2: fmt = " %-8s %-8s %12d %-8s %12d\n"; break; /* Field 2-6 */
179 case l_marker: fmt = " M%-7d 'MARKER' '%s'\n"; break; /* Field 2,3,5 */
184 case l_raw: fmt = "%s\n"; break;
185 case l_ind_name: fmt = "NAME %s\n"; break;
186 case l_ind_objs: fmt = "OBJSENSE\n"; break;
187 case l_ind_rows: fmt = "ROWS\n"; break;
188 case l_ind_cols: fmt = "COLUMNS\n"; break;
189 case l_ind_rhs: fmt = "RHS\n"; break;
190 case l_ind_end: fmt = "ENDATA\n"; break;
191 case l_data_row: fmt = " %s\t%s\n"; break;
192 case l_data_col1: fmt = " %s\t%s\t%d\n"; break;
193 case l_data_col2: fmt = " %s\t%s\t%d\t%s\t%d\n"; break;
194 case l_marker: fmt = " M%d\t'MARKER'\t'%s'\n"; break;
199 vfprintf(out, fmt, args);
203 static INLINE int mps_insert_markers(FILE *out, style_t style, var_t curr, var_t last, int marker_nr) {
204 assert(style == s_mps_fixed || style == s_mps_free);
206 /* print end-marker for last */
208 mps_write_line(out, style, l_marker, marker_nr++, "INTEND");
210 /* print begin-marker for curr */
212 mps_write_line(out, style, l_marker, marker_nr++, "INTORG");
217 static void lpp_dump_mps(lpp_t *lpp, FILE *out, style_t style) {
218 int i, count, marker_nr = 0;
221 assert(style == s_mps_fixed || style == s_mps_free);
224 mps_write_line(out, style, l_ind_name, lpp->name);
227 mps_write_line(out, style, l_ind_objs);
228 if (lpp->opt_type == maximize)
229 mps_write_line(out, style, l_raw, " MAX");
232 mps_write_line(out, style, l_ind_rows);
233 for(i=0; i<lpp->cst_next; ++i) {
235 mps_write_line(out, style, l_data_row, mps_cst_encoding[curr->type.cst_type], curr->name);
239 mps_write_line(out, style, l_ind_cols);
241 for(i=0; i<lpp->var_next; ++i) {
242 const matrix_elem_t *elem, *before = NULL;
246 marker_nr = mps_insert_markers(out, style, last_type, curr->type.var_type, marker_nr);
247 last_type = curr->type.var_type;
249 /* participation in constraints */
251 matrix_foreach_in_col(lpp->m, curr->nr, elem) {
256 mps_write_line(out, style, l_data_col2, curr->name, lpp->csts[before->row]->name, before->val, lpp->csts[elem->row]->name, elem->val);
261 mps_write_line(out, style, l_data_col1, curr->name, lpp->csts[before->row]->name, before->val);
263 mps_insert_markers(out, style, last_type, invalid, marker_nr); /* potential end-marker */
266 mps_write_line(out, style, l_ind_rhs);
267 for(i=0; i<lpp->rhs_size/2; ++i)
268 mps_write_line(out, style, l_data_col2, "rhs", lpp->csts[2*i]->name, lpp->rhs[2*i], lpp->csts[2*i+1]->name, lpp->rhs[2*i+1]);
269 if ((lpp->rhs_size & 1) == 1)
270 mps_write_line(out, style, l_data_col1, "rhs", lpp->csts[lpp->rhs_size-1]->name, lpp->rhs[lpp->rhs_size-1]);
273 mps_write_line(out, style, l_ind_end);
276 /******************************************************************************
278 ******************************************************************************/
280 static void lpp_dump_lp(lpp_t *lpp, FILE *out) {
284 void lpp_dump(lpp_t *lpp, FILE *out, style_t style) {
285 adjust_rhs_size(lpp);
288 case s_mps_free: lpp_dump_mps(lpp, out, style); break;
289 case s_lp: lpp_dump_lp(lpp, out); break;