[9] | 1 | /* glpcpx.c (CPLEX LP format routines) */ |
---|
| 2 | |
---|
| 3 | /*********************************************************************** |
---|
| 4 | * This code is part of GLPK (GNU Linear Programming Kit). |
---|
| 5 | * |
---|
| 6 | * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
---|
| 7 | * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, |
---|
| 8 | * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
---|
| 9 | * E-mail: <mao@gnu.org>. |
---|
| 10 | * |
---|
| 11 | * GLPK is free software: you can redistribute it and/or modify it |
---|
| 12 | * under the terms of the GNU General Public License as published by |
---|
| 13 | * the Free Software Foundation, either version 3 of the License, or |
---|
| 14 | * (at your option) any later version. |
---|
| 15 | * |
---|
| 16 | * GLPK is distributed in the hope that it will be useful, but WITHOUT |
---|
| 17 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
---|
| 18 | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
---|
| 19 | * License for more details. |
---|
| 20 | * |
---|
| 21 | * You should have received a copy of the GNU General Public License |
---|
| 22 | * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
---|
| 23 | ***********************************************************************/ |
---|
| 24 | |
---|
| 25 | #include "glpapi.h" |
---|
| 26 | |
---|
| 27 | /*********************************************************************** |
---|
| 28 | * NAME |
---|
| 29 | * |
---|
| 30 | * glp_init_cpxcp - initialize CPLEX LP format control parameters |
---|
| 31 | * |
---|
| 32 | * SYNOPSIS |
---|
| 33 | * |
---|
| 34 | * void glp_init_cpxcp(glp_cpxcp *parm): |
---|
| 35 | * |
---|
| 36 | * The routine glp_init_cpxcp initializes control parameters used by |
---|
| 37 | * the CPLEX LP input/output routines glp_read_lp and glp_write_lp with |
---|
| 38 | * default values. |
---|
| 39 | * |
---|
| 40 | * Default values of the control parameters are stored in the glp_cpxcp |
---|
| 41 | * structure, which the parameter parm points to. */ |
---|
| 42 | |
---|
| 43 | void glp_init_cpxcp(glp_cpxcp *parm) |
---|
| 44 | { xassert(parm != NULL); |
---|
| 45 | return; |
---|
| 46 | } |
---|
| 47 | |
---|
| 48 | static void check_parm(const char *func, const glp_cpxcp *parm) |
---|
| 49 | { /* check control parameters */ |
---|
| 50 | xassert(func != NULL); |
---|
| 51 | xassert(parm != NULL); |
---|
| 52 | return; |
---|
| 53 | } |
---|
| 54 | |
---|
| 55 | /*********************************************************************** |
---|
| 56 | * NAME |
---|
| 57 | * |
---|
| 58 | * glp_read_lp - read problem data in CPLEX LP format |
---|
| 59 | * |
---|
| 60 | * SYNOPSIS |
---|
| 61 | * |
---|
| 62 | * int glp_read_lp(glp_prob *P, const glp_cpxcp *parm, const char |
---|
| 63 | * *fname); |
---|
| 64 | * |
---|
| 65 | * DESCRIPTION |
---|
| 66 | * |
---|
| 67 | * The routine glp_read_lp reads problem data in CPLEX LP format from |
---|
| 68 | * a text file. |
---|
| 69 | * |
---|
| 70 | * The parameter parm is a pointer to the structure glp_cpxcp, which |
---|
| 71 | * specifies control parameters used by the routine. If parm is NULL, |
---|
| 72 | * the routine uses default settings. |
---|
| 73 | * |
---|
| 74 | * The character string fname specifies a name of the text file to be |
---|
| 75 | * read. |
---|
| 76 | * |
---|
| 77 | * Note that before reading data the current content of the problem |
---|
| 78 | * object is completely erased with the routine glp_erase_prob. |
---|
| 79 | * |
---|
| 80 | * RETURNS |
---|
| 81 | * |
---|
| 82 | * If the operation was successful, the routine glp_read_lp returns |
---|
| 83 | * zero. Otherwise, it prints an error message and returns non-zero. */ |
---|
| 84 | |
---|
| 85 | struct csa |
---|
| 86 | { /* common storage area */ |
---|
| 87 | glp_prob *P; |
---|
| 88 | /* LP/MIP problem object */ |
---|
| 89 | const glp_cpxcp *parm; |
---|
| 90 | /* pointer to control parameters */ |
---|
| 91 | const char *fname; |
---|
| 92 | /* name of input CPLEX LP file */ |
---|
| 93 | XFILE *fp; |
---|
| 94 | /* stream assigned to input CPLEX LP file */ |
---|
| 95 | jmp_buf jump; |
---|
| 96 | /* label for go to in case of error */ |
---|
| 97 | int count; |
---|
| 98 | /* line count */ |
---|
| 99 | int c; |
---|
| 100 | /* current character or XEOF */ |
---|
| 101 | int token; |
---|
| 102 | /* current token: */ |
---|
| 103 | #define T_EOF 0x00 /* end of file */ |
---|
| 104 | #define T_MINIMIZE 0x01 /* keyword 'minimize' */ |
---|
| 105 | #define T_MAXIMIZE 0x02 /* keyword 'maximize' */ |
---|
| 106 | #define T_SUBJECT_TO 0x03 /* keyword 'subject to' */ |
---|
| 107 | #define T_BOUNDS 0x04 /* keyword 'bounds' */ |
---|
| 108 | #define T_GENERAL 0x05 /* keyword 'general' */ |
---|
| 109 | #define T_INTEGER 0x06 /* keyword 'integer' */ |
---|
| 110 | #define T_BINARY 0x07 /* keyword 'binary' */ |
---|
| 111 | #define T_END 0x08 /* keyword 'end' */ |
---|
| 112 | #define T_NAME 0x09 /* symbolic name */ |
---|
| 113 | #define T_NUMBER 0x0A /* numeric constant */ |
---|
| 114 | #define T_PLUS 0x0B /* delimiter '+' */ |
---|
| 115 | #define T_MINUS 0x0C /* delimiter '-' */ |
---|
| 116 | #define T_COLON 0x0D /* delimiter ':' */ |
---|
| 117 | #define T_LE 0x0E /* delimiter '<=' */ |
---|
| 118 | #define T_GE 0x0F /* delimiter '>=' */ |
---|
| 119 | #define T_EQ 0x10 /* delimiter '=' */ |
---|
| 120 | char image[255+1]; |
---|
| 121 | /* image of current token */ |
---|
| 122 | int imlen; |
---|
| 123 | /* length of token image */ |
---|
| 124 | double value; |
---|
| 125 | /* value of numeric constant */ |
---|
| 126 | int n_max; |
---|
| 127 | /* length of the following five arrays (enlarged automatically, |
---|
| 128 | if necessary) */ |
---|
| 129 | int *ind; /* int ind[1+n_max]; */ |
---|
| 130 | double *val; /* double val[1+n_max]; */ |
---|
| 131 | char *flag; /* char flag[1+n_max]; */ |
---|
| 132 | /* working arrays used to construct linear forms */ |
---|
| 133 | double *lb; /* double lb[1+n_max]; */ |
---|
| 134 | double *ub; /* double ub[1+n_max]; */ |
---|
| 135 | /* lower and upper bounds of variables (columns) */ |
---|
| 136 | }; |
---|
| 137 | |
---|
| 138 | #define CHAR_SET "!\"#$%&()/,.;?@_`'{}|~" |
---|
| 139 | /* characters, which may appear in symbolic names */ |
---|
| 140 | |
---|
| 141 | static void error(struct csa *csa, const char *fmt, ...) |
---|
| 142 | { /* print error message and terminate processing */ |
---|
| 143 | va_list arg; |
---|
| 144 | xprintf("%s:%d: ", csa->fname, csa->count); |
---|
| 145 | va_start(arg, fmt); |
---|
| 146 | xvprintf(fmt, arg); |
---|
| 147 | va_end(arg); |
---|
| 148 | longjmp(csa->jump, 1); |
---|
| 149 | /* no return */ |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | static void warning(struct csa *csa, const char *fmt, ...) |
---|
| 153 | { /* print warning message and continue processing */ |
---|
| 154 | va_list arg; |
---|
| 155 | xprintf("%s:%d: warning: ", csa->fname, csa->count); |
---|
| 156 | va_start(arg, fmt); |
---|
| 157 | xvprintf(fmt, arg); |
---|
| 158 | va_end(arg); |
---|
| 159 | return; |
---|
| 160 | } |
---|
| 161 | |
---|
| 162 | static void read_char(struct csa *csa) |
---|
| 163 | { /* read next character from input file */ |
---|
| 164 | int c; |
---|
| 165 | xassert(csa->c != XEOF); |
---|
| 166 | if (csa->c == '\n') csa->count++; |
---|
| 167 | c = xfgetc(csa->fp); |
---|
| 168 | if (c < 0) |
---|
| 169 | { if (xferror(csa->fp)) |
---|
| 170 | error(csa, "read error - %s\n", xerrmsg()); |
---|
| 171 | else if (csa->c == '\n') |
---|
| 172 | { csa->count--; |
---|
| 173 | c = XEOF; |
---|
| 174 | } |
---|
| 175 | else |
---|
| 176 | { warning(csa, "missing final end of line\n"); |
---|
| 177 | c = '\n'; |
---|
| 178 | } |
---|
| 179 | } |
---|
| 180 | else if (c == '\n') |
---|
| 181 | ; |
---|
| 182 | else if (isspace(c)) |
---|
| 183 | c = ' '; |
---|
| 184 | else if (iscntrl(c)) |
---|
| 185 | error(csa, "invalid control character 0x%02X\n", c); |
---|
| 186 | csa->c = c; |
---|
| 187 | return; |
---|
| 188 | } |
---|
| 189 | |
---|
| 190 | static void add_char(struct csa *csa) |
---|
| 191 | { /* append current character to current token */ |
---|
| 192 | if (csa->imlen == sizeof(csa->image)-1) |
---|
| 193 | error(csa, "token `%.15s...' too long\n", csa->image); |
---|
| 194 | csa->image[csa->imlen++] = (char)csa->c; |
---|
| 195 | csa->image[csa->imlen] = '\0'; |
---|
| 196 | read_char(csa); |
---|
| 197 | return; |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | static int the_same(char *s1, char *s2) |
---|
| 201 | { /* compare two character strings ignoring case sensitivity */ |
---|
| 202 | for (; *s1 != '\0'; s1++, s2++) |
---|
| 203 | { if (tolower((unsigned char)*s1) != tolower((unsigned char)*s2)) |
---|
| 204 | return 0; |
---|
| 205 | } |
---|
| 206 | return 1; |
---|
| 207 | } |
---|
| 208 | |
---|
| 209 | static void scan_token(struct csa *csa) |
---|
| 210 | { /* scan next token */ |
---|
| 211 | int flag; |
---|
| 212 | csa->token = -1; |
---|
| 213 | csa->image[0] = '\0'; |
---|
| 214 | csa->imlen = 0; |
---|
| 215 | csa->value = 0.0; |
---|
| 216 | loop: flag = 0; |
---|
| 217 | /* skip non-significant characters */ |
---|
| 218 | while (csa->c == ' ') read_char(csa); |
---|
| 219 | /* recognize and scan current token */ |
---|
| 220 | if (csa->c == XEOF) |
---|
| 221 | csa->token = T_EOF; |
---|
| 222 | else if (csa->c == '\n') |
---|
| 223 | { read_char(csa); |
---|
| 224 | /* if the next character is letter, it may begin a keyword */ |
---|
| 225 | if (isalpha(csa->c)) |
---|
| 226 | { flag = 1; |
---|
| 227 | goto name; |
---|
| 228 | } |
---|
| 229 | goto loop; |
---|
| 230 | } |
---|
| 231 | else if (csa->c == '\\') |
---|
| 232 | { /* comment; ignore everything until end-of-line */ |
---|
| 233 | while (csa->c != '\n') read_char(csa); |
---|
| 234 | goto loop; |
---|
| 235 | } |
---|
| 236 | else if (isalpha(csa->c) || csa->c != '.' && strchr(CHAR_SET, |
---|
| 237 | csa->c) != NULL) |
---|
| 238 | name: { /* symbolic name */ |
---|
| 239 | csa->token = T_NAME; |
---|
| 240 | while (isalnum(csa->c) || strchr(CHAR_SET, csa->c) != NULL) |
---|
| 241 | add_char(csa); |
---|
| 242 | if (flag) |
---|
| 243 | { /* check for keyword */ |
---|
| 244 | if (the_same(csa->image, "minimize")) |
---|
| 245 | csa->token = T_MINIMIZE; |
---|
| 246 | else if (the_same(csa->image, "minimum")) |
---|
| 247 | csa->token = T_MINIMIZE; |
---|
| 248 | else if (the_same(csa->image, "min")) |
---|
| 249 | csa->token = T_MINIMIZE; |
---|
| 250 | else if (the_same(csa->image, "maximize")) |
---|
| 251 | csa->token = T_MAXIMIZE; |
---|
| 252 | else if (the_same(csa->image, "maximum")) |
---|
| 253 | csa->token = T_MAXIMIZE; |
---|
| 254 | else if (the_same(csa->image, "max")) |
---|
| 255 | csa->token = T_MAXIMIZE; |
---|
| 256 | else if (the_same(csa->image, "subject")) |
---|
| 257 | { if (csa->c == ' ') |
---|
| 258 | { read_char(csa); |
---|
| 259 | if (tolower(csa->c) == 't') |
---|
| 260 | { csa->token = T_SUBJECT_TO; |
---|
| 261 | csa->image[csa->imlen++] = ' '; |
---|
| 262 | csa->image[csa->imlen] = '\0'; |
---|
| 263 | add_char(csa); |
---|
| 264 | if (tolower(csa->c) != 'o') |
---|
| 265 | error(csa, "keyword `subject to' incomplete\n"); |
---|
| 266 | add_char(csa); |
---|
| 267 | if (isalpha(csa->c)) |
---|
| 268 | error(csa, "keyword `%s%c...' not recognized\n", |
---|
| 269 | csa->image, csa->c); |
---|
| 270 | } |
---|
| 271 | } |
---|
| 272 | } |
---|
| 273 | else if (the_same(csa->image, "such")) |
---|
| 274 | { if (csa->c == ' ') |
---|
| 275 | { read_char(csa); |
---|
| 276 | if (tolower(csa->c) == 't') |
---|
| 277 | { csa->token = T_SUBJECT_TO; |
---|
| 278 | csa->image[csa->imlen++] = ' '; |
---|
| 279 | csa->image[csa->imlen] = '\0'; |
---|
| 280 | add_char(csa); |
---|
| 281 | if (tolower(csa->c) != 'h') |
---|
| 282 | err: error(csa, "keyword `such that' incomplete\n"); |
---|
| 283 | add_char(csa); |
---|
| 284 | if (tolower(csa->c) != 'a') goto err; |
---|
| 285 | add_char(csa); |
---|
| 286 | if (tolower(csa->c) != 't') goto err; |
---|
| 287 | add_char(csa); |
---|
| 288 | if (isalpha(csa->c)) |
---|
| 289 | error(csa, "keyword `%s%c...' not recognized\n", |
---|
| 290 | csa->image, csa->c); |
---|
| 291 | } |
---|
| 292 | } |
---|
| 293 | } |
---|
| 294 | else if (the_same(csa->image, "st")) |
---|
| 295 | csa->token = T_SUBJECT_TO; |
---|
| 296 | else if (the_same(csa->image, "s.t.")) |
---|
| 297 | csa->token = T_SUBJECT_TO; |
---|
| 298 | else if (the_same(csa->image, "st.")) |
---|
| 299 | csa->token = T_SUBJECT_TO; |
---|
| 300 | else if (the_same(csa->image, "bounds")) |
---|
| 301 | csa->token = T_BOUNDS; |
---|
| 302 | else if (the_same(csa->image, "bound")) |
---|
| 303 | csa->token = T_BOUNDS; |
---|
| 304 | else if (the_same(csa->image, "general")) |
---|
| 305 | csa->token = T_GENERAL; |
---|
| 306 | else if (the_same(csa->image, "generals")) |
---|
| 307 | csa->token = T_GENERAL; |
---|
| 308 | else if (the_same(csa->image, "gen")) |
---|
| 309 | csa->token = T_GENERAL; |
---|
| 310 | else if (the_same(csa->image, "integer")) |
---|
| 311 | csa->token = T_INTEGER; |
---|
| 312 | else if (the_same(csa->image, "integers")) |
---|
| 313 | csa->token = T_INTEGER; |
---|
| 314 | else if (the_same(csa->image, "int")) |
---|
| 315 | csa->token = T_INTEGER; |
---|
| 316 | else if (the_same(csa->image, "binary")) |
---|
| 317 | csa->token = T_BINARY; |
---|
| 318 | else if (the_same(csa->image, "binaries")) |
---|
| 319 | csa->token = T_BINARY; |
---|
| 320 | else if (the_same(csa->image, "bin")) |
---|
| 321 | csa->token = T_BINARY; |
---|
| 322 | else if (the_same(csa->image, "end")) |
---|
| 323 | csa->token = T_END; |
---|
| 324 | } |
---|
| 325 | } |
---|
| 326 | else if (isdigit(csa->c) || csa->c == '.') |
---|
| 327 | { /* numeric constant */ |
---|
| 328 | csa->token = T_NUMBER; |
---|
| 329 | /* scan integer part */ |
---|
| 330 | while (isdigit(csa->c)) add_char(csa); |
---|
| 331 | /* scan optional fractional part (it is mandatory, if there is |
---|
| 332 | no integer part) */ |
---|
| 333 | if (csa->c == '.') |
---|
| 334 | { add_char(csa); |
---|
| 335 | if (csa->imlen == 1 && !isdigit(csa->c)) |
---|
| 336 | error(csa, "invalid use of decimal point\n"); |
---|
| 337 | while (isdigit(csa->c)) add_char(csa); |
---|
| 338 | } |
---|
| 339 | /* scan optional decimal exponent */ |
---|
| 340 | if (csa->c == 'e' || csa->c == 'E') |
---|
| 341 | { add_char(csa); |
---|
| 342 | if (csa->c == '+' || csa->c == '-') add_char(csa); |
---|
| 343 | if (!isdigit(csa->c)) |
---|
| 344 | error(csa, "numeric constant `%s' incomplete\n", |
---|
| 345 | csa->image); |
---|
| 346 | while (isdigit(csa->c)) add_char(csa); |
---|
| 347 | } |
---|
| 348 | /* convert the numeric constant to floating-point */ |
---|
| 349 | if (str2num(csa->image, &csa->value)) |
---|
| 350 | error(csa, "numeric constant `%s' out of range\n", |
---|
| 351 | csa->image); |
---|
| 352 | } |
---|
| 353 | else if (csa->c == '+') |
---|
| 354 | csa->token = T_PLUS, add_char(csa); |
---|
| 355 | else if (csa->c == '-') |
---|
| 356 | csa->token = T_MINUS, add_char(csa); |
---|
| 357 | else if (csa->c == ':') |
---|
| 358 | csa->token = T_COLON, add_char(csa); |
---|
| 359 | else if (csa->c == '<') |
---|
| 360 | { csa->token = T_LE, add_char(csa); |
---|
| 361 | if (csa->c == '=') add_char(csa); |
---|
| 362 | } |
---|
| 363 | else if (csa->c == '>') |
---|
| 364 | { csa->token = T_GE, add_char(csa); |
---|
| 365 | if (csa->c == '=') add_char(csa); |
---|
| 366 | } |
---|
| 367 | else if (csa->c == '=') |
---|
| 368 | { csa->token = T_EQ, add_char(csa); |
---|
| 369 | if (csa->c == '<') |
---|
| 370 | csa->token = T_LE, add_char(csa); |
---|
| 371 | else if (csa->c == '>') |
---|
| 372 | csa->token = T_GE, add_char(csa); |
---|
| 373 | } |
---|
| 374 | else |
---|
| 375 | error(csa, "character `%c' not recognized\n", csa->c); |
---|
| 376 | /* skip non-significant characters */ |
---|
| 377 | while (csa->c == ' ') read_char(csa); |
---|
| 378 | return; |
---|
| 379 | } |
---|
| 380 | |
---|
| 381 | static int find_col(struct csa *csa, char *name) |
---|
| 382 | { /* find column by its symbolic name */ |
---|
| 383 | int j; |
---|
| 384 | j = glp_find_col(csa->P, name); |
---|
| 385 | if (j == 0) |
---|
| 386 | { /* not found; create new column */ |
---|
| 387 | j = glp_add_cols(csa->P, 1); |
---|
| 388 | glp_set_col_name(csa->P, j, name); |
---|
| 389 | /* enlarge working arrays, if necessary */ |
---|
| 390 | if (csa->n_max < j) |
---|
| 391 | { int n_max = csa->n_max; |
---|
| 392 | int *ind = csa->ind; |
---|
| 393 | double *val = csa->val; |
---|
| 394 | char *flag = csa->flag; |
---|
| 395 | double *lb = csa->lb; |
---|
| 396 | double *ub = csa->ub; |
---|
| 397 | csa->n_max += csa->n_max; |
---|
| 398 | csa->ind = xcalloc(1+csa->n_max, sizeof(int)); |
---|
| 399 | memcpy(&csa->ind[1], &ind[1], n_max * sizeof(int)); |
---|
| 400 | xfree(ind); |
---|
| 401 | csa->val = xcalloc(1+csa->n_max, sizeof(double)); |
---|
| 402 | memcpy(&csa->val[1], &val[1], n_max * sizeof(double)); |
---|
| 403 | xfree(val); |
---|
| 404 | csa->flag = xcalloc(1+csa->n_max, sizeof(char)); |
---|
| 405 | memset(&csa->flag[1], 0, csa->n_max * sizeof(char)); |
---|
| 406 | memcpy(&csa->flag[1], &flag[1], n_max * sizeof(char)); |
---|
| 407 | xfree(flag); |
---|
| 408 | csa->lb = xcalloc(1+csa->n_max, sizeof(double)); |
---|
| 409 | memcpy(&csa->lb[1], &lb[1], n_max * sizeof(double)); |
---|
| 410 | xfree(lb); |
---|
| 411 | csa->ub = xcalloc(1+csa->n_max, sizeof(double)); |
---|
| 412 | memcpy(&csa->ub[1], &ub[1], n_max * sizeof(double)); |
---|
| 413 | xfree(ub); |
---|
| 414 | } |
---|
| 415 | csa->lb[j] = +DBL_MAX, csa->ub[j] = -DBL_MAX; |
---|
| 416 | } |
---|
| 417 | return j; |
---|
| 418 | } |
---|
| 419 | |
---|
| 420 | /*********************************************************************** |
---|
| 421 | * parse_linear_form - parse linear form |
---|
| 422 | * |
---|
| 423 | * This routine parses the linear form using the following syntax: |
---|
| 424 | * |
---|
| 425 | * <variable> ::= <symbolic name> |
---|
| 426 | * <coefficient> ::= <numeric constant> |
---|
| 427 | * <term> ::= <variable> | <numeric constant> <variable> |
---|
| 428 | * <linear form> ::= <term> | + <term> | - <term> | |
---|
| 429 | * <linear form> + <term> | <linear form> - <term> |
---|
| 430 | * |
---|
| 431 | * The routine returns the number of terms in the linear form. */ |
---|
| 432 | |
---|
| 433 | static int parse_linear_form(struct csa *csa) |
---|
| 434 | { int j, k, len = 0, newlen; |
---|
| 435 | double s, coef; |
---|
| 436 | loop: /* parse an optional sign */ |
---|
| 437 | if (csa->token == T_PLUS) |
---|
| 438 | s = +1.0, scan_token(csa); |
---|
| 439 | else if (csa->token == T_MINUS) |
---|
| 440 | s = -1.0, scan_token(csa); |
---|
| 441 | else |
---|
| 442 | s = +1.0; |
---|
| 443 | /* parse an optional coefficient */ |
---|
| 444 | if (csa->token == T_NUMBER) |
---|
| 445 | coef = csa->value, scan_token(csa); |
---|
| 446 | else |
---|
| 447 | coef = 1.0; |
---|
| 448 | /* parse a variable name */ |
---|
| 449 | if (csa->token != T_NAME) |
---|
| 450 | error(csa, "missing variable name\n"); |
---|
| 451 | /* find the corresponding column */ |
---|
| 452 | j = find_col(csa, csa->image); |
---|
| 453 | /* check if the variable is already used in the linear form */ |
---|
| 454 | if (csa->flag[j]) |
---|
| 455 | error(csa, "multiple use of variable `%s' not allowed\n", |
---|
| 456 | csa->image); |
---|
| 457 | /* add new term to the linear form */ |
---|
| 458 | len++, csa->ind[len] = j, csa->val[len] = s * coef; |
---|
| 459 | /* and mark that the variable is used in the linear form */ |
---|
| 460 | csa->flag[j] = 1; |
---|
| 461 | scan_token(csa); |
---|
| 462 | /* if the next token is a sign, there is another term */ |
---|
| 463 | if (csa->token == T_PLUS || csa->token == T_MINUS) goto loop; |
---|
| 464 | /* clear marks of the variables used in the linear form */ |
---|
| 465 | for (k = 1; k <= len; k++) csa->flag[csa->ind[k]] = 0; |
---|
| 466 | /* remove zero coefficients */ |
---|
| 467 | newlen = 0; |
---|
| 468 | for (k = 1; k <= len; k++) |
---|
| 469 | { if (csa->val[k] != 0.0) |
---|
| 470 | { newlen++; |
---|
| 471 | csa->ind[newlen] = csa->ind[k]; |
---|
| 472 | csa->val[newlen] = csa->val[k]; |
---|
| 473 | } |
---|
| 474 | } |
---|
| 475 | return newlen; |
---|
| 476 | } |
---|
| 477 | |
---|
| 478 | /*********************************************************************** |
---|
| 479 | * parse_objective - parse objective function |
---|
| 480 | * |
---|
| 481 | * This routine parses definition of the objective function using the |
---|
| 482 | * following syntax: |
---|
| 483 | * |
---|
| 484 | * <obj sense> ::= minimize | minimum | min | maximize | maximum | max |
---|
| 485 | * <obj name> ::= <empty> | <symbolic name> : |
---|
| 486 | * <obj function> ::= <obj sense> <obj name> <linear form> */ |
---|
| 487 | |
---|
| 488 | static void parse_objective(struct csa *csa) |
---|
| 489 | { /* parse objective sense */ |
---|
| 490 | int k, len; |
---|
| 491 | /* parse the keyword 'minimize' or 'maximize' */ |
---|
| 492 | if (csa->token == T_MINIMIZE) |
---|
| 493 | glp_set_obj_dir(csa->P, GLP_MIN); |
---|
| 494 | else if (csa->token == T_MAXIMIZE) |
---|
| 495 | glp_set_obj_dir(csa->P, GLP_MAX); |
---|
| 496 | else |
---|
| 497 | xassert(csa != csa); |
---|
| 498 | scan_token(csa); |
---|
| 499 | /* parse objective name */ |
---|
| 500 | if (csa->token == T_NAME && csa->c == ':') |
---|
| 501 | { /* objective name is followed by a colon */ |
---|
| 502 | glp_set_obj_name(csa->P, csa->image); |
---|
| 503 | scan_token(csa); |
---|
| 504 | xassert(csa->token == T_COLON); |
---|
| 505 | scan_token(csa); |
---|
| 506 | } |
---|
| 507 | else |
---|
| 508 | { /* objective name is not specified; use default */ |
---|
| 509 | glp_set_obj_name(csa->P, "obj"); |
---|
| 510 | } |
---|
| 511 | /* parse linear form */ |
---|
| 512 | len = parse_linear_form(csa); |
---|
| 513 | for (k = 1; k <= len; k++) |
---|
| 514 | glp_set_obj_coef(csa->P, csa->ind[k], csa->val[k]); |
---|
| 515 | return; |
---|
| 516 | } |
---|
| 517 | |
---|
| 518 | /*********************************************************************** |
---|
| 519 | * parse_constraints - parse constraints section |
---|
| 520 | * |
---|
| 521 | * This routine parses the constraints section using the following |
---|
| 522 | * syntax: |
---|
| 523 | * |
---|
| 524 | * <row name> ::= <empty> | <symbolic name> : |
---|
| 525 | * <row sense> ::= < | <= | =< | > | >= | => | = |
---|
| 526 | * <right-hand side> ::= <numeric constant> | + <numeric constant> | |
---|
| 527 | * - <numeric constant> |
---|
| 528 | * <constraint> ::= <row name> <linear form> <row sense> |
---|
| 529 | * <right-hand side> |
---|
| 530 | * <subject to> ::= subject to | such that | st | s.t. | st. |
---|
| 531 | * <constraints section> ::= <subject to> <constraint> | |
---|
| 532 | * <constraints section> <constraint> */ |
---|
| 533 | |
---|
| 534 | static void parse_constraints(struct csa *csa) |
---|
| 535 | { int i, len, type; |
---|
| 536 | double s; |
---|
| 537 | /* parse the keyword 'subject to' */ |
---|
| 538 | xassert(csa->token == T_SUBJECT_TO); |
---|
| 539 | scan_token(csa); |
---|
| 540 | loop: /* create new row (constraint) */ |
---|
| 541 | i = glp_add_rows(csa->P, 1); |
---|
| 542 | /* parse row name */ |
---|
| 543 | if (csa->token == T_NAME && csa->c == ':') |
---|
| 544 | { /* row name is followed by a colon */ |
---|
| 545 | if (glp_find_row(csa->P, csa->image) != 0) |
---|
| 546 | error(csa, "constraint `%s' multiply defined\n", |
---|
| 547 | csa->image); |
---|
| 548 | glp_set_row_name(csa->P, i, csa->image); |
---|
| 549 | scan_token(csa); |
---|
| 550 | xassert(csa->token == T_COLON); |
---|
| 551 | scan_token(csa); |
---|
| 552 | } |
---|
| 553 | else |
---|
| 554 | { /* row name is not specified; use default */ |
---|
| 555 | char name[50]; |
---|
| 556 | sprintf(name, "r.%d", csa->count); |
---|
| 557 | glp_set_row_name(csa->P, i, name); |
---|
| 558 | } |
---|
| 559 | /* parse linear form */ |
---|
| 560 | len = parse_linear_form(csa); |
---|
| 561 | glp_set_mat_row(csa->P, i, len, csa->ind, csa->val); |
---|
| 562 | /* parse constraint sense */ |
---|
| 563 | if (csa->token == T_LE) |
---|
| 564 | type = GLP_UP, scan_token(csa); |
---|
| 565 | else if (csa->token == T_GE) |
---|
| 566 | type = GLP_LO, scan_token(csa); |
---|
| 567 | else if (csa->token == T_EQ) |
---|
| 568 | type = GLP_FX, scan_token(csa); |
---|
| 569 | else |
---|
| 570 | error(csa, "missing constraint sense\n"); |
---|
| 571 | /* parse right-hand side */ |
---|
| 572 | if (csa->token == T_PLUS) |
---|
| 573 | s = +1.0, scan_token(csa); |
---|
| 574 | else if (csa->token == T_MINUS) |
---|
| 575 | s = -1.0, scan_token(csa); |
---|
| 576 | else |
---|
| 577 | s = +1.0; |
---|
| 578 | if (csa->token != T_NUMBER) |
---|
| 579 | error(csa, "missing right-hand side\n"); |
---|
| 580 | glp_set_row_bnds(csa->P, i, type, s * csa->value, s * csa->value); |
---|
| 581 | /* the rest of the current line must be empty */ |
---|
| 582 | if (!(csa->c == '\n' || csa->c == XEOF)) |
---|
| 583 | error(csa, "invalid symbol(s) beyond right-hand side\n"); |
---|
| 584 | scan_token(csa); |
---|
| 585 | /* if the next token is a sign, numeric constant, or a symbolic |
---|
| 586 | name, here is another constraint */ |
---|
| 587 | if (csa->token == T_PLUS || csa->token == T_MINUS || |
---|
| 588 | csa->token == T_NUMBER || csa->token == T_NAME) goto loop; |
---|
| 589 | return; |
---|
| 590 | } |
---|
| 591 | |
---|
| 592 | static void set_lower_bound(struct csa *csa, int j, double lb) |
---|
| 593 | { /* set lower bound of j-th variable */ |
---|
| 594 | if (csa->lb[j] != +DBL_MAX) |
---|
| 595 | { warning(csa, "lower bound of variable `%s' redefined\n", |
---|
| 596 | glp_get_col_name(csa->P, j)); |
---|
| 597 | } |
---|
| 598 | csa->lb[j] = lb; |
---|
| 599 | return; |
---|
| 600 | } |
---|
| 601 | |
---|
| 602 | static void set_upper_bound(struct csa *csa, int j, double ub) |
---|
| 603 | { /* set upper bound of j-th variable */ |
---|
| 604 | if (csa->ub[j] != -DBL_MAX) |
---|
| 605 | { warning(csa, "upper bound of variable `%s' redefined\n", |
---|
| 606 | glp_get_col_name(csa->P, j)); |
---|
| 607 | } |
---|
| 608 | csa->ub[j] = ub; |
---|
| 609 | return; |
---|
| 610 | } |
---|
| 611 | |
---|
| 612 | /*********************************************************************** |
---|
| 613 | * parse_bounds - parse bounds section |
---|
| 614 | * |
---|
| 615 | * This routine parses the bounds section using the following syntax: |
---|
| 616 | * |
---|
| 617 | * <variable> ::= <symbolic name> |
---|
| 618 | * <infinity> ::= infinity | inf |
---|
| 619 | * <bound> ::= <numeric constant> | + <numeric constant> | |
---|
| 620 | * - <numeric constant> | + <infinity> | - <infinity> |
---|
| 621 | * <lt> ::= < | <= | =< |
---|
| 622 | * <gt> ::= > | >= | => |
---|
| 623 | * <bound definition> ::= <bound> <lt> <variable> <lt> <bound> | |
---|
| 624 | * <bound> <lt> <variable> | <variable> <lt> <bound> | |
---|
| 625 | * <variable> <gt> <bound> | <variable> = <bound> | <variable> free |
---|
| 626 | * <bounds> ::= bounds | bound |
---|
| 627 | * <bounds section> ::= <bounds> | |
---|
| 628 | * <bounds section> <bound definition> */ |
---|
| 629 | |
---|
| 630 | static void parse_bounds(struct csa *csa) |
---|
| 631 | { int j, lb_flag; |
---|
| 632 | double lb, s; |
---|
| 633 | /* parse the keyword 'bounds' */ |
---|
| 634 | xassert(csa->token == T_BOUNDS); |
---|
| 635 | scan_token(csa); |
---|
| 636 | loop: /* bound definition can start with a sign, numeric constant, or |
---|
| 637 | a symbolic name */ |
---|
| 638 | if (!(csa->token == T_PLUS || csa->token == T_MINUS || |
---|
| 639 | csa->token == T_NUMBER || csa->token == T_NAME)) goto done; |
---|
| 640 | /* parse bound definition */ |
---|
| 641 | if (csa->token == T_PLUS || csa->token == T_MINUS) |
---|
| 642 | { /* parse signed lower bound */ |
---|
| 643 | lb_flag = 1; |
---|
| 644 | s = (csa->token == T_PLUS ? +1.0 : -1.0); |
---|
| 645 | scan_token(csa); |
---|
| 646 | if (csa->token == T_NUMBER) |
---|
| 647 | lb = s * csa->value, scan_token(csa); |
---|
| 648 | else if (the_same(csa->image, "infinity") || |
---|
| 649 | the_same(csa->image, "inf")) |
---|
| 650 | { if (s > 0.0) |
---|
| 651 | error(csa, "invalid use of `+inf' as lower bound\n"); |
---|
| 652 | lb = -DBL_MAX, scan_token(csa); |
---|
| 653 | } |
---|
| 654 | else |
---|
| 655 | error(csa, "missing lower bound\n"); |
---|
| 656 | } |
---|
| 657 | else if (csa->token == T_NUMBER) |
---|
| 658 | { /* parse unsigned lower bound */ |
---|
| 659 | lb_flag = 1; |
---|
| 660 | lb = csa->value, scan_token(csa); |
---|
| 661 | } |
---|
| 662 | else |
---|
| 663 | { /* lower bound is not specified */ |
---|
| 664 | lb_flag = 0; |
---|
| 665 | } |
---|
| 666 | /* parse the token that should follow the lower bound */ |
---|
| 667 | if (lb_flag) |
---|
| 668 | { if (csa->token != T_LE) |
---|
| 669 | error(csa, "missing `<', `<=', or `=<' after lower bound\n") |
---|
| 670 | ; |
---|
| 671 | scan_token(csa); |
---|
| 672 | } |
---|
| 673 | /* parse variable name */ |
---|
| 674 | if (csa->token != T_NAME) |
---|
| 675 | error(csa, "missing variable name\n"); |
---|
| 676 | j = find_col(csa, csa->image); |
---|
| 677 | /* set lower bound */ |
---|
| 678 | if (lb_flag) set_lower_bound(csa, j, lb); |
---|
| 679 | scan_token(csa); |
---|
| 680 | /* parse the context that follows the variable name */ |
---|
| 681 | if (csa->token == T_LE) |
---|
| 682 | { /* parse upper bound */ |
---|
| 683 | scan_token(csa); |
---|
| 684 | if (csa->token == T_PLUS || csa->token == T_MINUS) |
---|
| 685 | { /* parse signed upper bound */ |
---|
| 686 | s = (csa->token == T_PLUS ? +1.0 : -1.0); |
---|
| 687 | scan_token(csa); |
---|
| 688 | if (csa->token == T_NUMBER) |
---|
| 689 | { set_upper_bound(csa, j, s * csa->value); |
---|
| 690 | scan_token(csa); |
---|
| 691 | } |
---|
| 692 | else if (the_same(csa->image, "infinity") || |
---|
| 693 | the_same(csa->image, "inf")) |
---|
| 694 | { if (s < 0.0) |
---|
| 695 | error(csa, "invalid use of `-inf' as upper bound\n"); |
---|
| 696 | set_upper_bound(csa, j, +DBL_MAX); |
---|
| 697 | scan_token(csa); |
---|
| 698 | } |
---|
| 699 | else |
---|
| 700 | error(csa, "missing upper bound\n"); |
---|
| 701 | } |
---|
| 702 | else if (csa->token == T_NUMBER) |
---|
| 703 | { /* parse unsigned upper bound */ |
---|
| 704 | set_upper_bound(csa, j, csa->value); |
---|
| 705 | scan_token(csa); |
---|
| 706 | } |
---|
| 707 | else |
---|
| 708 | error(csa, "missing upper bound\n"); |
---|
| 709 | } |
---|
| 710 | else if (csa->token == T_GE) |
---|
| 711 | { /* parse lower bound */ |
---|
| 712 | if (lb_flag) |
---|
| 713 | { /* the context '... <= x >= ...' is invalid */ |
---|
| 714 | error(csa, "invalid bound definition\n"); |
---|
| 715 | } |
---|
| 716 | scan_token(csa); |
---|
| 717 | if (csa->token == T_PLUS || csa->token == T_MINUS) |
---|
| 718 | { /* parse signed lower bound */ |
---|
| 719 | s = (csa->token == T_PLUS ? +1.0 : -1.0); |
---|
| 720 | scan_token(csa); |
---|
| 721 | if (csa->token == T_NUMBER) |
---|
| 722 | { set_lower_bound(csa, j, s * csa->value); |
---|
| 723 | scan_token(csa); |
---|
| 724 | } |
---|
| 725 | else if (the_same(csa->image, "infinity") || |
---|
| 726 | the_same(csa->image, "inf") == 0) |
---|
| 727 | { if (s > 0.0) |
---|
| 728 | error(csa, "invalid use of `+inf' as lower bound\n"); |
---|
| 729 | set_lower_bound(csa, j, -DBL_MAX); |
---|
| 730 | scan_token(csa); |
---|
| 731 | } |
---|
| 732 | else |
---|
| 733 | error(csa, "missing lower bound\n"); |
---|
| 734 | } |
---|
| 735 | else if (csa->token == T_NUMBER) |
---|
| 736 | { /* parse unsigned lower bound */ |
---|
| 737 | set_lower_bound(csa, j, csa->value); |
---|
| 738 | scan_token(csa); |
---|
| 739 | } |
---|
| 740 | else |
---|
| 741 | error(csa, "missing lower bound\n"); |
---|
| 742 | } |
---|
| 743 | else if (csa->token == T_EQ) |
---|
| 744 | { /* parse fixed value */ |
---|
| 745 | if (lb_flag) |
---|
| 746 | { /* the context '... <= x = ...' is invalid */ |
---|
| 747 | error(csa, "invalid bound definition\n"); |
---|
| 748 | } |
---|
| 749 | scan_token(csa); |
---|
| 750 | if (csa->token == T_PLUS || csa->token == T_MINUS) |
---|
| 751 | { /* parse signed fixed value */ |
---|
| 752 | s = (csa->token == T_PLUS ? +1.0 : -1.0); |
---|
| 753 | scan_token(csa); |
---|
| 754 | if (csa->token == T_NUMBER) |
---|
| 755 | { set_lower_bound(csa, j, s * csa->value); |
---|
| 756 | set_upper_bound(csa, j, s * csa->value); |
---|
| 757 | scan_token(csa); |
---|
| 758 | } |
---|
| 759 | else |
---|
| 760 | error(csa, "missing fixed value\n"); |
---|
| 761 | } |
---|
| 762 | else if (csa->token == T_NUMBER) |
---|
| 763 | { /* parse unsigned fixed value */ |
---|
| 764 | set_lower_bound(csa, j, csa->value); |
---|
| 765 | set_upper_bound(csa, j, csa->value); |
---|
| 766 | scan_token(csa); |
---|
| 767 | } |
---|
| 768 | else |
---|
| 769 | error(csa, "missing fixed value\n"); |
---|
| 770 | } |
---|
| 771 | else if (the_same(csa->image, "free")) |
---|
| 772 | { /* parse the keyword 'free' */ |
---|
| 773 | if (lb_flag) |
---|
| 774 | { /* the context '... <= x free ...' is invalid */ |
---|
| 775 | error(csa, "invalid bound definition\n"); |
---|
| 776 | } |
---|
| 777 | set_lower_bound(csa, j, -DBL_MAX); |
---|
| 778 | set_upper_bound(csa, j, +DBL_MAX); |
---|
| 779 | scan_token(csa); |
---|
| 780 | } |
---|
| 781 | else if (!lb_flag) |
---|
| 782 | { /* neither lower nor upper bounds are specified */ |
---|
| 783 | error(csa, "invalid bound definition\n"); |
---|
| 784 | } |
---|
| 785 | goto loop; |
---|
| 786 | done: return; |
---|
| 787 | } |
---|
| 788 | |
---|
| 789 | /*********************************************************************** |
---|
| 790 | * parse_integer - parse general, integer, or binary section |
---|
| 791 | * |
---|
| 792 | * <variable> ::= <symbolic name> |
---|
| 793 | * <general> ::= general | generals | gen |
---|
| 794 | * <integer> ::= integer | integers | int |
---|
| 795 | * <binary> ::= binary | binaries | bin |
---|
| 796 | * <section head> ::= <general> <integer> <binary> |
---|
| 797 | * <additional section> ::= <section head> | |
---|
| 798 | * <additional section> <variable> */ |
---|
| 799 | |
---|
| 800 | static void parse_integer(struct csa *csa) |
---|
| 801 | { int j, binary; |
---|
| 802 | /* parse the keyword 'general', 'integer', or 'binary' */ |
---|
| 803 | if (csa->token == T_GENERAL) |
---|
| 804 | binary = 0, scan_token(csa); |
---|
| 805 | else if (csa->token == T_INTEGER) |
---|
| 806 | binary = 0, scan_token(csa); |
---|
| 807 | else if (csa->token == T_BINARY) |
---|
| 808 | binary = 1, scan_token(csa); |
---|
| 809 | else |
---|
| 810 | xassert(csa != csa); |
---|
| 811 | /* parse list of variables (may be empty) */ |
---|
| 812 | while (csa->token == T_NAME) |
---|
| 813 | { /* find the corresponding column */ |
---|
| 814 | j = find_col(csa, csa->image); |
---|
| 815 | /* change kind of the variable */ |
---|
| 816 | glp_set_col_kind(csa->P, j, GLP_IV); |
---|
| 817 | /* set 0-1 bounds for the binary variable */ |
---|
| 818 | if (binary) |
---|
| 819 | { set_lower_bound(csa, j, 0.0); |
---|
| 820 | set_upper_bound(csa, j, 1.0); |
---|
| 821 | } |
---|
| 822 | scan_token(csa); |
---|
| 823 | } |
---|
| 824 | return; |
---|
| 825 | } |
---|
| 826 | |
---|
| 827 | int glp_read_lp(glp_prob *P, const glp_cpxcp *parm, const char *fname) |
---|
| 828 | { /* read problem data in CPLEX LP format */ |
---|
| 829 | glp_cpxcp _parm; |
---|
| 830 | struct csa _csa, *csa = &_csa; |
---|
| 831 | int ret; |
---|
| 832 | xprintf("Reading problem data from `%s'...\n", fname); |
---|
| 833 | if (parm == NULL) |
---|
| 834 | glp_init_cpxcp(&_parm), parm = &_parm; |
---|
| 835 | /* check control parameters */ |
---|
| 836 | check_parm("glp_read_lp", parm); |
---|
| 837 | /* initialize common storage area */ |
---|
| 838 | csa->P = P; |
---|
| 839 | csa->parm = parm; |
---|
| 840 | csa->fname = fname; |
---|
| 841 | csa->fp = NULL; |
---|
| 842 | if (setjmp(csa->jump)) |
---|
| 843 | { ret = 1; |
---|
| 844 | goto done; |
---|
| 845 | } |
---|
| 846 | csa->count = 0; |
---|
| 847 | csa->c = '\n'; |
---|
| 848 | csa->token = T_EOF; |
---|
| 849 | csa->image[0] = '\0'; |
---|
| 850 | csa->imlen = 0; |
---|
| 851 | csa->value = 0.0; |
---|
| 852 | csa->n_max = 100; |
---|
| 853 | csa->ind = xcalloc(1+csa->n_max, sizeof(int)); |
---|
| 854 | csa->val = xcalloc(1+csa->n_max, sizeof(double)); |
---|
| 855 | csa->flag = xcalloc(1+csa->n_max, sizeof(char)); |
---|
| 856 | memset(&csa->flag[1], 0, csa->n_max * sizeof(char)); |
---|
| 857 | csa->lb = xcalloc(1+csa->n_max, sizeof(double)); |
---|
| 858 | csa->ub = xcalloc(1+csa->n_max, sizeof(double)); |
---|
| 859 | /* erase problem object */ |
---|
| 860 | glp_erase_prob(P); |
---|
| 861 | glp_create_index(P); |
---|
| 862 | /* open input CPLEX LP file */ |
---|
| 863 | csa->fp = xfopen(fname, "r"); |
---|
| 864 | if (csa->fp == NULL) |
---|
| 865 | { xprintf("Unable to open `%s' - %s\n", fname, xerrmsg()); |
---|
| 866 | ret = 1; |
---|
| 867 | goto done; |
---|
| 868 | } |
---|
| 869 | /* scan very first token */ |
---|
| 870 | scan_token(csa); |
---|
| 871 | /* parse definition of the objective function */ |
---|
| 872 | if (!(csa->token == T_MINIMIZE || csa->token == T_MAXIMIZE)) |
---|
| 873 | error(csa, "`minimize' or `maximize' keyword missing\n"); |
---|
| 874 | parse_objective(csa); |
---|
| 875 | /* parse constraints section */ |
---|
| 876 | if (csa->token != T_SUBJECT_TO) |
---|
| 877 | error(csa, "constraints section missing\n"); |
---|
| 878 | parse_constraints(csa); |
---|
| 879 | /* parse optional bounds section */ |
---|
| 880 | if (csa->token == T_BOUNDS) parse_bounds(csa); |
---|
| 881 | /* parse optional general, integer, and binary sections */ |
---|
| 882 | while (csa->token == T_GENERAL || |
---|
| 883 | csa->token == T_INTEGER || |
---|
| 884 | csa->token == T_BINARY) parse_integer(csa); |
---|
| 885 | /* check for the keyword 'end' */ |
---|
| 886 | if (csa->token == T_END) |
---|
| 887 | scan_token(csa); |
---|
| 888 | else if (csa->token == T_EOF) |
---|
| 889 | warning(csa, "keyword `end' missing\n"); |
---|
| 890 | else |
---|
| 891 | error(csa, "symbol `%s' in wrong position\n", csa->image); |
---|
| 892 | /* nothing must follow the keyword 'end' (except comments) */ |
---|
| 893 | if (csa->token != T_EOF) |
---|
| 894 | error(csa, "extra symbol(s) detected beyond `end'\n"); |
---|
| 895 | /* set bounds of variables */ |
---|
| 896 | { int j, type; |
---|
| 897 | double lb, ub; |
---|
| 898 | for (j = 1; j <= P->n; j++) |
---|
| 899 | { lb = csa->lb[j]; |
---|
| 900 | ub = csa->ub[j]; |
---|
| 901 | if (lb == +DBL_MAX) lb = 0.0; /* default lb */ |
---|
| 902 | if (ub == -DBL_MAX) ub = +DBL_MAX; /* default ub */ |
---|
| 903 | if (lb == -DBL_MAX && ub == +DBL_MAX) |
---|
| 904 | type = GLP_FR; |
---|
| 905 | else if (ub == +DBL_MAX) |
---|
| 906 | type = GLP_LO; |
---|
| 907 | else if (lb == -DBL_MAX) |
---|
| 908 | type = GLP_UP; |
---|
| 909 | else if (lb != ub) |
---|
| 910 | type = GLP_DB; |
---|
| 911 | else |
---|
| 912 | type = GLP_FX; |
---|
| 913 | glp_set_col_bnds(csa->P, j, type, lb, ub); |
---|
| 914 | } |
---|
| 915 | } |
---|
| 916 | /* print some statistics */ |
---|
| 917 | xprintf("%d row%s, %d column%s, %d non-zero%s\n", |
---|
| 918 | P->m, P->m == 1 ? "" : "s", P->n, P->n == 1 ? "" : "s", |
---|
| 919 | P->nnz, P->nnz == 1 ? "" : "s"); |
---|
| 920 | if (glp_get_num_int(P) > 0) |
---|
| 921 | { int ni = glp_get_num_int(P); |
---|
| 922 | int nb = glp_get_num_bin(P); |
---|
| 923 | if (ni == 1) |
---|
| 924 | { if (nb == 0) |
---|
| 925 | xprintf("One variable is integer\n"); |
---|
| 926 | else |
---|
| 927 | xprintf("One variable is binary\n"); |
---|
| 928 | } |
---|
| 929 | else |
---|
| 930 | { xprintf("%d integer variables, ", ni); |
---|
| 931 | if (nb == 0) |
---|
| 932 | xprintf("none"); |
---|
| 933 | else if (nb == 1) |
---|
| 934 | xprintf("one"); |
---|
| 935 | else if (nb == ni) |
---|
| 936 | xprintf("all"); |
---|
| 937 | else |
---|
| 938 | xprintf("%d", nb); |
---|
| 939 | xprintf(" of which %s binary\n", nb == 1 ? "is" : "are"); |
---|
| 940 | } |
---|
| 941 | } |
---|
| 942 | xprintf("%d lines were read\n", csa->count); |
---|
| 943 | /* problem data has been successfully read */ |
---|
| 944 | glp_delete_index(P); |
---|
| 945 | glp_sort_matrix(P); |
---|
| 946 | ret = 0; |
---|
| 947 | done: if (csa->fp != NULL) xfclose(csa->fp); |
---|
| 948 | xfree(csa->ind); |
---|
| 949 | xfree(csa->val); |
---|
| 950 | xfree(csa->flag); |
---|
| 951 | xfree(csa->lb); |
---|
| 952 | xfree(csa->ub); |
---|
| 953 | if (ret != 0) glp_erase_prob(P); |
---|
| 954 | return ret; |
---|
| 955 | } |
---|
| 956 | |
---|
| 957 | /*********************************************************************** |
---|
| 958 | * NAME |
---|
| 959 | * |
---|
| 960 | * glp_write_lp - write problem data in CPLEX LP format |
---|
| 961 | * |
---|
| 962 | * SYNOPSIS |
---|
| 963 | * |
---|
| 964 | * int glp_write_lp(glp_prob *P, const glp_cpxcp *parm, const char |
---|
| 965 | * *fname); |
---|
| 966 | * |
---|
| 967 | * DESCRIPTION |
---|
| 968 | * |
---|
| 969 | * The routine glp_write_lp writes problem data in CPLEX LP format to |
---|
| 970 | * a text file. |
---|
| 971 | * |
---|
| 972 | * The parameter parm is a pointer to the structure glp_cpxcp, which |
---|
| 973 | * specifies control parameters used by the routine. If parm is NULL, |
---|
| 974 | * the routine uses default settings. |
---|
| 975 | * |
---|
| 976 | * The character string fname specifies a name of the text file to be |
---|
| 977 | * written. |
---|
| 978 | * |
---|
| 979 | * RETURNS |
---|
| 980 | * |
---|
| 981 | * If the operation was successful, the routine glp_write_lp returns |
---|
| 982 | * zero. Otherwise, it prints an error message and returns non-zero. */ |
---|
| 983 | |
---|
| 984 | #define csa csa1 |
---|
| 985 | |
---|
| 986 | struct csa |
---|
| 987 | { /* common storage area */ |
---|
| 988 | glp_prob *P; |
---|
| 989 | /* pointer to problem object */ |
---|
| 990 | const glp_cpxcp *parm; |
---|
| 991 | /* pointer to control parameters */ |
---|
| 992 | }; |
---|
| 993 | |
---|
| 994 | static int check_name(char *name) |
---|
| 995 | { /* check if specified name is valid for CPLEX LP format */ |
---|
| 996 | if (*name == '.') return 1; |
---|
| 997 | if (isdigit((unsigned char)*name)) return 1; |
---|
| 998 | for (; *name; name++) |
---|
| 999 | { if (!isalnum((unsigned char)*name) && |
---|
| 1000 | strchr(CHAR_SET, (unsigned char)*name) == NULL) return 1; |
---|
| 1001 | } |
---|
| 1002 | return 0; /* name is ok */ |
---|
| 1003 | } |
---|
| 1004 | |
---|
| 1005 | static void adjust_name(char *name) |
---|
| 1006 | { /* attempt to adjust specified name to make it valid for CPLEX LP |
---|
| 1007 | format */ |
---|
| 1008 | for (; *name; name++) |
---|
| 1009 | { if (*name == ' ') |
---|
| 1010 | *name = '_'; |
---|
| 1011 | else if (*name == '-') |
---|
| 1012 | *name = '~'; |
---|
| 1013 | else if (*name == '[') |
---|
| 1014 | *name = '('; |
---|
| 1015 | else if (*name == ']') |
---|
| 1016 | *name = ')'; |
---|
| 1017 | } |
---|
| 1018 | return; |
---|
| 1019 | } |
---|
| 1020 | |
---|
| 1021 | static char *row_name(struct csa *csa, int i, char rname[255+1]) |
---|
| 1022 | { /* construct symbolic name of i-th row (constraint) */ |
---|
| 1023 | const char *name; |
---|
| 1024 | if (i == 0) |
---|
| 1025 | name = glp_get_obj_name(csa->P); |
---|
| 1026 | else |
---|
| 1027 | name = glp_get_row_name(csa->P, i); |
---|
| 1028 | if (name == NULL) goto fake; |
---|
| 1029 | strcpy(rname, name); |
---|
| 1030 | adjust_name(rname); |
---|
| 1031 | if (check_name(rname)) goto fake; |
---|
| 1032 | return rname; |
---|
| 1033 | fake: if (i == 0) |
---|
| 1034 | strcpy(rname, "obj"); |
---|
| 1035 | else |
---|
| 1036 | sprintf(rname, "r_%d", i); |
---|
| 1037 | return rname; |
---|
| 1038 | } |
---|
| 1039 | |
---|
| 1040 | static char *col_name(struct csa *csa, int j, char cname[255+1]) |
---|
| 1041 | { /* construct symbolic name of j-th column (variable) */ |
---|
| 1042 | const char *name; |
---|
| 1043 | name = glp_get_col_name(csa->P, j); |
---|
| 1044 | if (name == NULL) goto fake; |
---|
| 1045 | strcpy(cname, name); |
---|
| 1046 | adjust_name(cname); |
---|
| 1047 | if (check_name(cname)) goto fake; |
---|
| 1048 | return cname; |
---|
| 1049 | fake: sprintf(cname, "x_%d", j); |
---|
| 1050 | return cname; |
---|
| 1051 | } |
---|
| 1052 | |
---|
| 1053 | int glp_write_lp(glp_prob *P, const glp_cpxcp *parm, const char *fname) |
---|
| 1054 | { /* write problem data in CPLEX LP format */ |
---|
| 1055 | glp_cpxcp _parm; |
---|
| 1056 | struct csa _csa, *csa = &_csa; |
---|
| 1057 | XFILE *fp; |
---|
| 1058 | GLPROW *row; |
---|
| 1059 | GLPCOL *col; |
---|
| 1060 | GLPAIJ *aij; |
---|
| 1061 | int i, j, len, flag, count, ret; |
---|
| 1062 | char line[1000+1], term[500+1], name[255+1]; |
---|
| 1063 | xprintf("Writing problem data to `%s'...\n", fname); |
---|
| 1064 | if (parm == NULL) |
---|
| 1065 | glp_init_cpxcp(&_parm), parm = &_parm; |
---|
| 1066 | /* check control parameters */ |
---|
| 1067 | check_parm("glp_write_lp", parm); |
---|
| 1068 | /* initialize common storage area */ |
---|
| 1069 | csa->P = P; |
---|
| 1070 | csa->parm = parm; |
---|
| 1071 | /* create output CPLEX LP file */ |
---|
| 1072 | fp = xfopen(fname, "w"), count = 0; |
---|
| 1073 | if (fp == NULL) |
---|
| 1074 | { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg()); |
---|
| 1075 | ret = 1; |
---|
| 1076 | goto done; |
---|
| 1077 | } |
---|
| 1078 | /* write problem name */ |
---|
| 1079 | xfprintf(fp, "\\* Problem: %s *\\\n", |
---|
| 1080 | P->name == NULL ? "Unknown" : P->name), count++; |
---|
| 1081 | xfprintf(fp, "\n"), count++; |
---|
| 1082 | /* the problem should contain at least one row and one column */ |
---|
| 1083 | if (!(P->m > 0 && P->n > 0)) |
---|
| 1084 | { xprintf("Warning: problem has no rows/columns\n"); |
---|
| 1085 | xfprintf(fp, "\\* WARNING: PROBLEM HAS NO ROWS/COLUMNS *\\\n"), |
---|
| 1086 | count++; |
---|
| 1087 | xfprintf(fp, "\n"), count++; |
---|
| 1088 | goto skip; |
---|
| 1089 | } |
---|
| 1090 | /* write the objective function definition */ |
---|
| 1091 | if (P->dir == GLP_MIN) |
---|
| 1092 | xfprintf(fp, "Minimize\n"), count++; |
---|
| 1093 | else if (P->dir == GLP_MAX) |
---|
| 1094 | xfprintf(fp, "Maximize\n"), count++; |
---|
| 1095 | else |
---|
| 1096 | xassert(P != P); |
---|
| 1097 | row_name(csa, 0, name); |
---|
| 1098 | sprintf(line, " %s:", name); |
---|
| 1099 | len = 0; |
---|
| 1100 | for (j = 1; j <= P->n; j++) |
---|
| 1101 | { col = P->col[j]; |
---|
| 1102 | if (col->coef != 0.0 || col->ptr == NULL) |
---|
| 1103 | { len++; |
---|
| 1104 | col_name(csa, j, name); |
---|
| 1105 | if (col->coef == 0.0) |
---|
| 1106 | sprintf(term, " + 0 %s", name); /* empty column */ |
---|
| 1107 | else if (col->coef == +1.0) |
---|
| 1108 | sprintf(term, " + %s", name); |
---|
| 1109 | else if (col->coef == -1.0) |
---|
| 1110 | sprintf(term, " - %s", name); |
---|
| 1111 | else if (col->coef > 0.0) |
---|
| 1112 | sprintf(term, " + %.*g %s", DBL_DIG, +col->coef, name); |
---|
| 1113 | else |
---|
| 1114 | sprintf(term, " - %.*g %s", DBL_DIG, -col->coef, name); |
---|
| 1115 | if (strlen(line) + strlen(term) > 72) |
---|
| 1116 | xfprintf(fp, "%s\n", line), line[0] = '\0', count++; |
---|
| 1117 | strcat(line, term); |
---|
| 1118 | } |
---|
| 1119 | } |
---|
| 1120 | if (len == 0) |
---|
| 1121 | { /* empty objective */ |
---|
| 1122 | sprintf(term, " 0 %s", col_name(csa, 1, name)); |
---|
| 1123 | strcat(line, term); |
---|
| 1124 | } |
---|
| 1125 | xfprintf(fp, "%s\n", line), count++; |
---|
| 1126 | if (P->c0 != 0.0) |
---|
| 1127 | xfprintf(fp, "\\* constant term = %.*g *\\\n", DBL_DIG, P->c0), |
---|
| 1128 | count++; |
---|
| 1129 | xfprintf(fp, "\n"), count++; |
---|
| 1130 | /* write the constraints section */ |
---|
| 1131 | xfprintf(fp, "Subject To\n"), count++; |
---|
| 1132 | for (i = 1; i <= P->m; i++) |
---|
| 1133 | { row = P->row[i]; |
---|
| 1134 | if (row->type == GLP_FR) continue; /* skip free row */ |
---|
| 1135 | row_name(csa, i, name); |
---|
| 1136 | sprintf(line, " %s:", name); |
---|
| 1137 | /* linear form */ |
---|
| 1138 | for (aij = row->ptr; aij != NULL; aij = aij->r_next) |
---|
| 1139 | { col_name(csa, aij->col->j, name); |
---|
| 1140 | if (aij->val == +1.0) |
---|
| 1141 | sprintf(term, " + %s", name); |
---|
| 1142 | else if (aij->val == -1.0) |
---|
| 1143 | sprintf(term, " - %s", name); |
---|
| 1144 | else if (aij->val > 0.0) |
---|
| 1145 | sprintf(term, " + %.*g %s", DBL_DIG, +aij->val, name); |
---|
| 1146 | else |
---|
| 1147 | sprintf(term, " - %.*g %s", DBL_DIG, -aij->val, name); |
---|
| 1148 | if (strlen(line) + strlen(term) > 72) |
---|
| 1149 | xfprintf(fp, "%s\n", line), line[0] = '\0', count++; |
---|
| 1150 | strcat(line, term); |
---|
| 1151 | } |
---|
| 1152 | if (row->type == GLP_DB) |
---|
| 1153 | { /* double-bounded (ranged) constraint */ |
---|
| 1154 | sprintf(term, " - ~r_%d", i); |
---|
| 1155 | if (strlen(line) + strlen(term) > 72) |
---|
| 1156 | xfprintf(fp, "%s\n", line), line[0] = '\0', count++; |
---|
| 1157 | strcat(line, term); |
---|
| 1158 | } |
---|
| 1159 | else if (row->ptr == NULL) |
---|
| 1160 | { /* empty constraint */ |
---|
| 1161 | sprintf(term, " 0 %s", col_name(csa, 1, name)); |
---|
| 1162 | strcat(line, term); |
---|
| 1163 | } |
---|
| 1164 | /* right hand-side */ |
---|
| 1165 | if (row->type == GLP_LO) |
---|
| 1166 | sprintf(term, " >= %.*g", DBL_DIG, row->lb); |
---|
| 1167 | else if (row->type == GLP_UP) |
---|
| 1168 | sprintf(term, " <= %.*g", DBL_DIG, row->ub); |
---|
| 1169 | else if (row->type == GLP_DB || row->type == GLP_FX) |
---|
| 1170 | sprintf(term, " = %.*g", DBL_DIG, row->lb); |
---|
| 1171 | else |
---|
| 1172 | xassert(row != row); |
---|
| 1173 | if (strlen(line) + strlen(term) > 72) |
---|
| 1174 | xfprintf(fp, "%s\n", line), line[0] = '\0', count++; |
---|
| 1175 | strcat(line, term); |
---|
| 1176 | xfprintf(fp, "%s\n", line), count++; |
---|
| 1177 | } |
---|
| 1178 | xfprintf(fp, "\n"), count++; |
---|
| 1179 | /* write the bounds section */ |
---|
| 1180 | flag = 0; |
---|
| 1181 | for (i = 1; i <= P->m; i++) |
---|
| 1182 | { row = P->row[i]; |
---|
| 1183 | if (row->type != GLP_DB) continue; |
---|
| 1184 | if (!flag) |
---|
| 1185 | xfprintf(fp, "Bounds\n"), flag = 1, count++; |
---|
| 1186 | xfprintf(fp, " 0 <= ~r_%d <= %.*g\n", |
---|
| 1187 | i, DBL_DIG, row->ub - row->lb), count++; |
---|
| 1188 | } |
---|
| 1189 | for (j = 1; j <= P->n; j++) |
---|
| 1190 | { col = P->col[j]; |
---|
| 1191 | if (col->type == GLP_LO && col->lb == 0.0) continue; |
---|
| 1192 | if (!flag) |
---|
| 1193 | xfprintf(fp, "Bounds\n"), flag = 1, count++; |
---|
| 1194 | col_name(csa, j, name); |
---|
| 1195 | if (col->type == GLP_FR) |
---|
| 1196 | xfprintf(fp, " %s free\n", name), count++; |
---|
| 1197 | else if (col->type == GLP_LO) |
---|
| 1198 | xfprintf(fp, " %s >= %.*g\n", |
---|
| 1199 | name, DBL_DIG, col->lb), count++; |
---|
| 1200 | else if (col->type == GLP_UP) |
---|
| 1201 | xfprintf(fp, " -Inf <= %s <= %.*g\n", |
---|
| 1202 | name, DBL_DIG, col->ub), count++; |
---|
| 1203 | else if (col->type == GLP_DB) |
---|
| 1204 | xfprintf(fp, " %.*g <= %s <= %.*g\n", |
---|
| 1205 | DBL_DIG, col->lb, name, DBL_DIG, col->ub), count++; |
---|
| 1206 | else if (col->type == GLP_FX) |
---|
| 1207 | xfprintf(fp, " %s = %.*g\n", |
---|
| 1208 | name, DBL_DIG, col->lb), count++; |
---|
| 1209 | else |
---|
| 1210 | xassert(col != col); |
---|
| 1211 | } |
---|
| 1212 | if (flag) xfprintf(fp, "\n"), count++; |
---|
| 1213 | /* write the integer section */ |
---|
| 1214 | flag = 0; |
---|
| 1215 | for (j = 1; j <= P->n; j++) |
---|
| 1216 | { col = P->col[j]; |
---|
| 1217 | if (col->kind == GLP_CV) continue; |
---|
| 1218 | xassert(col->kind == GLP_IV); |
---|
| 1219 | if (!flag) |
---|
| 1220 | xfprintf(fp, "Generals\n"), flag = 1, count++; |
---|
| 1221 | xfprintf(fp, " %s\n", col_name(csa, j, name)), count++; |
---|
| 1222 | } |
---|
| 1223 | if (flag) xfprintf(fp, "\n"), count++; |
---|
| 1224 | skip: /* write the end keyword */ |
---|
| 1225 | xfprintf(fp, "End\n"), count++; |
---|
| 1226 | xfflush(fp); |
---|
| 1227 | if (xferror(fp)) |
---|
| 1228 | { xprintf("Write error on `%s' - %s\n", fname, xerrmsg()); |
---|
| 1229 | ret = 1; |
---|
| 1230 | goto done; |
---|
| 1231 | } |
---|
| 1232 | /* problem data has been successfully written */ |
---|
| 1233 | xprintf("%d lines were written\n", count); |
---|
| 1234 | ret = 0; |
---|
| 1235 | done: if (fp != NULL) xfclose(fp); |
---|
| 1236 | return ret; |
---|
| 1237 | } |
---|
| 1238 | |
---|
| 1239 | /* eof */ |
---|