glpapi17.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

/* glpapi17.c (stand-alone LP/MIP solver) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#define _GLPSTD_STDIO
#include "glpapi.h"
#include "glpgmp.h"

struct csa
{     /* common storage area */
      glp_prob *prob;
      /* LP/MIP problem object */
      glp_bfcp bfcp;
      /* basis factorization control parameters */
      glp_smcp smcp;
      /* simplex method control parameters */
      glp_iocp iocp;
      /* integer optimizer control parameters */
      glp_tran *tran;
      /* model translator workspace */
      glp_graph *graph;
      /* network problem object */
      int format;
      /* problem file format: */
#define FMT_MPS_DECK    1  /* fixed MPS */
#define FMT_MPS_FILE    2  /* free MPS */
#define FMT_CPLEX_LP    3  /* CPLEX LP */
#define FMT_MATHPROG    4  /* MathProg */
#define FMT_MIN_COST    5  /* DIMACS min-cost flow */
#define FMT_MAX_FLOW    6  /* DIMACS maximum flow */
      const char *in_file;
      /* name of input problem file */
#define DATA_MAX 10
      /* maximal number of input data files */
      int ndf;
      /* number of input data files specified */
      const char *in_data[1+DATA_MAX];
      /* name(s) of input data file(s) */
      const char *out_dpy;
      /* name of output file to send display output; NULL means the
         display output is sent to the terminal */
      int solution;
      /* solution type flag: */
#define SOL_BASIC       1  /* basic */
#define SOL_INTERIOR    2  /* interior-point */
#define SOL_INTEGER     3  /* mixed integer */
      const char *in_res;
      /* name of input solution file in raw format */
      int dir;
      /* optimization direction flag:
         0       - not specified
         GLP_MIN - minimization
         GLP_MAX - maximization */
      int scale;
      /* automatic problem scaling flag */
      const char *out_sol;
      /* name of output solution file in printable format */
      const char *out_res;
      /* name of output solution file in raw format */
      const char *out_bnds;
      /* name of output sensitivity bounds file in printable format */
      int check;
      /* input data checking flag; no solution is performed */
      const char *new_name;
      /* new name to be assigned to the problem */
      const char *out_mps;
      /* name of output problem file in fixed MPS format */
      const char *out_freemps;
      /* name of output problem file in free MPS format */
      const char *out_cpxlp;
      /* name of output problem file in CPLEX LP format */
      const char *out_pb;
      /* name of output problem file in OPB format */
      const char *out_npb;
      /* name of output problem file in normalized OPB format */
      const char *log_file;
      /* name of output file to hardcopy terminal output */
      int crash;
      /* initial basis option: */
#define USE_STD_BASIS   1  /* use standard basis */
#define USE_ADV_BASIS   2  /* use advanced basis */
#define USE_CPX_BASIS   3  /* use Bixby's basis */
      int exact;
      /* flag to use glp_exact rather than glp_simplex */
      int xcheck;
      /* flag to check final basis with glp_exact */
      int nomip;
      /* flag to consider MIP as pure LP */
};

static void print_help(const char *my_name)
{     /* print help information */
      xprintf("Usage: %s [options...] filename\n", my_name);
      xprintf("\n");
      xprintf("General options:\n");
      xprintf("   --mps             read LP/MIP problem in fixed MPS fo"
         "rmat\n");
      xprintf("   --freemps         read LP/MIP problem in free MPS for"
         "mat (default)\n");
      xprintf("   --cpxlp           read LP/MIP problem in CPLEX LP for"
         "mat\n");
      xprintf("   --math            read LP/MIP model written in GNU Ma"
         "thProg modeling\n");
      xprintf("                     language\n");
      xprintf("   -m filename, --model filename\n");
      xprintf("                     read model section and optional dat"
         "a section from\n");
      xprintf("                     filename (the same as --math)\n");
      xprintf("   -d filename, --data filename\n");
      xprintf("                     read data section from filename (fo"
         "r --math only);\n");
      xprintf("                     if model file also has data section"
         ", it is ignored\n");
      xprintf("   -y filename, --display filename\n");
      xprintf("                     send display output to filename (fo"
         "r --math only);\n");
      xprintf("                     by default the output is sent to te"
         "rminal\n");
      xprintf("   --mincost         read min-cost flow problem in DIMAC"
         "S format\n");
      xprintf("   --maxflow         read maximum flow problem in DIMACS"
         " format\n");
      xprintf("   --simplex         use simplex method (default)\n");
      xprintf("   --interior        use interior point method (LP only)"
         "\n");
      xprintf("   -r filename, --read filename\n");
      xprintf("                     read solution from filename rather "
         "to find it with\n");
      xprintf("                     the solver\n");
      xprintf("   --min             minimization\n");
      xprintf("   --max             maximization\n");
      xprintf("   --scale           scale problem (default)\n");
      xprintf("   --noscale         do not scale problem\n");
      xprintf("   -o filename, --output filename\n");
      xprintf("                     write solution to filename in print"
         "able format\n");
      xprintf("   -w filename, --write filename\n");
      xprintf("                     write solution to filename in plain"
         " text format\n");
      xprintf("   --bounds filename\n");
      xprintf("                     write sensitivity bounds to filenam"
         "e in printable\n");
      xprintf("                     format (LP only)\n");
      xprintf("   --tmlim nnn       limit solution time to nnn seconds "
         "\n");
      xprintf("   --memlim nnn      limit available memory to nnn megab"
         "ytes\n");
      xprintf("   --check           do not solve problem, check input d"
         "ata only\n");
      xprintf("   --name probname   change problem name to probname\n");
      xprintf("   --wmps filename   write problem to filename in fixed "
         "MPS format\n");
      xprintf("   --wfreemps filename\n");
      xprintf("                     write problem to filename in free M"
         "PS format\n");
      xprintf("   --wcpxlp filename write problem to filename in CPLEX "
         "LP format\n");
      xprintf("   --wpb filename    write problem to filename in OPB fo"
         "rmat\n");
      xprintf("   --wnpb filename   write problem to filename in normal"
         "ized OPB format\n");
      xprintf("   --log filename    write copy of terminal output to fi"
         "lename\n");
      xprintf("   -h, --help        display this help information and e"
         "xit\n");
      xprintf("   -v, --version     display program version and exit\n")
         ;
      xprintf("\n");
      xprintf("LP basis factorization options:\n");
      xprintf("   --luf             LU + Forrest-Tomlin update\n");
      xprintf("                     (faster, less stable; default)\n");
      xprintf("   --cbg             LU + Schur complement + Bartels-Gol"
         "ub update\n");
      xprintf("                     (slower, more stable)\n");
      xprintf("   --cgr             LU + Schur complement + Givens rota"
         "tion update\n");
      xprintf("                     (slower, more stable)\n");
      xprintf("\n");
      xprintf("Options specific to simplex method:\n");
      xprintf("   --primal          use primal simplex (default)\n");
      xprintf("   --dual            use dual simplex\n");
      xprintf("   --std             use standard initial basis of all s"
         "lacks\n");
      xprintf("   --adv             use advanced initial basis (default"
         ")\n");
      xprintf("   --bib             use Bixby's initial basis\n");
      xprintf("   --steep           use steepest edge technique (defaul"
         "t)\n");
      xprintf("   --nosteep         use standard \"textbook\" pricing\n"
         );
      xprintf("   --relax           use Harris' two-pass ratio test (de"
         "fault)\n");
      xprintf("   --norelax         use standard \"textbook\" ratio tes"
         "t\n");
      xprintf("   --presol          use presolver (default; assumes --s"
         "cale and --adv)\n");
      xprintf("   --nopresol        do not use presolver\n");
      xprintf("   --exact           use simplex method based on exact a"
         "rithmetic\n");
      xprintf("   --xcheck          check final basis using exact arith"
         "metic\n");
      xprintf("\n");
      xprintf("Options specific to MIP:\n");
      xprintf("   --nomip           consider all integer variables as c"
         "ontinuous\n");
      xprintf("                     (allows solving MIP as pure LP)\n");
      xprintf("   --first           branch on first integer variable\n")
         ;
      xprintf("   --last            branch on last integer variable\n");
      xprintf("   --drtom           branch using heuristic by Driebeck "
         "and Tomlin\n");
      xprintf("                     (default)\n");
      xprintf("   --mostf           branch on most fractional variable "
         "\n");
      xprintf("   --dfs             backtrack using depth first search "
         "\n");
      xprintf("   --bfs             backtrack using breadth first searc"
         "h\n");
      xprintf("   --bestp           backtrack using the best projection"
         " heuristic\n");
      xprintf("   --bestb           backtrack using node with best loca"
         "l bound\n");
      xprintf("                     (default)\n");
      xprintf("   --intopt          use MIP presolver (default)\n");
      xprintf("   --nointopt        do not use MIP presolver\n");
      xprintf("   --binarize        replace general integer variables b"
         "y binary ones\n");
      xprintf("                     (assumes --intopt)\n");
      xprintf("   --gomory          generate Gomory's mixed integer cut"
         "s\n");
      xprintf("   --mir             generate MIR (mixed integer roundin"
         "g) cuts\n");
      xprintf("   --cover           generate mixed cover cuts\n");
      xprintf("   --clique          generate clique cuts\n");
      xprintf("   --cuts            generate all cuts above\n");
      xprintf("   --mipgap tol      set relative mip gap tolerance to t"
         "ol\n");
      xprintf("\n");
      xprintf("For description of the MPS and CPLEX LP formats see Refe"
         "rence Manual.\n");
      xprintf("For description of the modeling language see \"GLPK: Mod"
         "eling Language\n");
      xprintf("GNU MathProg\". Both documents are included in the GLPK "
         "distribution.\n");
      xprintf("\n");
      xprintf("See GLPK web page at <http://www.gnu.org/software/glpk/g"
         "lpk.html>.\n");
      xprintf("\n");
      xprintf("Please report bugs to <[e-mail]>.\n");
      return;
}

static void print_version(void)
{     /* print version information */
      xprintf("GLPSOL: GLPK LP/MIP Solver %s\n", glp_version());
      xprintf("\n");
      xprintf("Copyright (C) 2008 Andrew Makhorin, Department for Appli"
         "ed Informatics,\n");
      xprintf("Moscow Aviation Institute, Moscow, Russia. All rights re"
         "served.\n");
      xprintf("\n");
      xprintf("This program has ABSOLUTELY NO WARRANTY.\n");
      xprintf("\n");
      xprintf("This program is free software; you may re-distribute it "
         "under the terms\n");
      xprintf("of the GNU General Public License version 3 or later.\n")
         ;
      return;
}

static int parse_cmdline(struct csa *csa, int argc, const char *argv[])
{     /* parse command-line parameters */
      int k;
#define p(str) (strcmp(argv[k], str) == 0)
      for (k = 1; k < argc; k++)
      {  if (p("--mps"))
            csa->format = FMT_MPS_DECK;
         else if (p("--freemps"))
            csa->format = FMT_MPS_FILE;
         else if (p("--cpxlp"))
            csa->format = FMT_CPLEX_LP;
         else if (p("--math") || p("-m") || p("--model"))
            csa->format = FMT_MATHPROG;
         else if (p("-d") || p("--data"))
         {  k++;
            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
            {  xprintf("No input data file specifed\n");
               return 1;
            }
            if (csa->ndf == DATA_MAX)
            {  xprintf("Too many input data files\n");
               return 1;
            }
            csa->in_data[++(csa->ndf)] = argv[k];
         }
         else if (p("-y") || p("--display"))
         {  k++;
            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
            {  xprintf("No display output file specifed\n");
               return 1;
            }
            if (csa->out_dpy != NULL)
            {  xprintf("Only one display output file allowed\n");
               return 1;
            }
            csa->out_dpy = argv[k];
         }
         else if (p("--mincost"))
            csa->format = FMT_MIN_COST;
         else if (p("--maxflow"))
            csa->format = FMT_MAX_FLOW;
         else if (p("--simplex"))
            csa->solution = SOL_BASIC;
         else if (p("--interior"))
            csa->solution = SOL_INTERIOR;
         else if (p("-r") || p("--read"))
         {  k++;
            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
            {  xprintf("No input solution file specifed\n");
               return 1;
            }
            if (csa->in_res != NULL)
            {  xprintf("Only one input solution file allowed\n");