COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/src/glpcpx.c @ 10:5545663ca997

subpack-glpk
Last change on this file since 10:5545663ca997 was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 42.5 KB
Line 
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
43void glp_init_cpxcp(glp_cpxcp *parm)
44{     xassert(parm != NULL);
45      return;
46}
47
48static 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
85struct 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
141static 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
152static 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
162static 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
190static 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
200static 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
209static 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;
216loop: 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)
238name: {  /* 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')
282err:                    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
381static 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
433static int parse_linear_form(struct csa *csa)
434{     int j, k, len = 0, newlen;
435      double s, coef;
436loop: /* 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
488static 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
534static 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);
540loop: /* 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
592static 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
602static 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
630static 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);
636loop: /* 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;
786done: 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
800static 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
827int 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;
947done: 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
986struct 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
994static 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
1005static 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
1021static 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;
1033fake: if (i == 0)
1034         strcpy(rname, "obj");
1035      else
1036         sprintf(rname, "r_%d", i);
1037      return rname;
1038}
1039
1040static 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;
1049fake: sprintf(cname, "x_%d", j);
1050      return cname;
1051}
1052
1053int 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++;
1224skip: /* 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;
1235done: if (fp != NULL) xfclose(fp);
1236      return ret;
1237}
1238
1239/* eof */
Note: See TracBrowser for help on using the repository browser.