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 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 
glp_init_cpxcp(glp_cpxcp * parm)43 void glp_init_cpxcp(glp_cpxcp *parm)
44 {     xassert(parm != NULL);
45       return;
46 }
47 
check_parm(const char * func,const glp_cpxcp * parm)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 
error(struct csa * csa,const char * fmt,...)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 
warning(struct csa * csa,const char * fmt,...)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 
read_char(struct csa * csa)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 
add_char(struct csa * csa)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 
the_same(char * s1,char * s2)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 
scan_token(struct csa * csa)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 
find_col(struct csa * csa,char * name)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 
parse_linear_form(struct csa * csa)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 
parse_objective(struct csa * csa)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 
parse_constraints(struct csa * csa)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 
set_lower_bound(struct csa * csa,int j,double lb)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 
set_upper_bound(struct csa * csa,int j,double ub)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 
parse_bounds(struct csa * csa)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 
parse_integer(struct csa * csa)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 
glp_read_lp(glp_prob * P,const glp_cpxcp * parm,const char * fname)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 
check_name(char * name)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 
adjust_name(char * name)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 
row_name(struct csa * csa,int i,char rname[255+1])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 
col_name(struct csa * csa,int j,char cname[255+1])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 
glp_write_lp(glp_prob * P,const glp_cpxcp * parm,const char * fname)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 */
1240