lemon-project-template-glpk
view deps/glpk/src/glpcpx.c @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 /* glpcpx.c (CPLEX LP format routines) */
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 ***********************************************************************/
25 #include "glpapi.h"
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. */
43 void glp_init_cpxcp(glp_cpxcp *parm)
44 { xassert(parm != NULL);
45 return;
46 }
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 }
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. */
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 };
138 #define CHAR_SET "!\"#$%&()/,.;?@_`'{}|~"
139 /* characters, which may appear in symbolic names */
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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. */
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 }
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> */
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 }
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> */
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 }
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 }
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 }
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> */
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 }
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> */
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 }
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 }
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. */
984 #define csa csa1
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 };
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 }
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 }
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 }
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 }
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 }
1239 /* eof */