[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] MIP API Documentation and (New) Examples

From: Marcos
Subject: [Help-glpk] MIP API Documentation and (New) Examples
Date: Tue, 21 Sep 2004 00:47:06 -0300
User-agent: Mozilla/5.0 (X11; U; Linux i686; pt-BR; rv:1.6) Gecko/20040413 Debian/1.6-5

Dear Friends,
I found the message below in the Help-glpk archive. There are some advances in this topic?
I am trying to use the api routines of glpk to the gap (like in the gap.mod in the examples sub-directory)
Anyone have more examples?

Thank you.

Best regards,

Marcos Roberto Silva

Re: [Help-glpk] GLPK API

From: Andrew Makhorin
Subject: Re: [Help-glpk] GLPK API
Date: Thu, 21 Jun 2001 19:26:19 +0400

Thank you for your interest in GLPK.

>First of all congratulations!  I solved a small MIP model of mine using
>GLPK in 0.1 seconds where the commercial solver LINDO took 3.5 seconds
>to solve it.

Please note that GLPK MIP solver is based on a branch-and-bound, which
is much less efficient in case of large-scale and hard MIP problems than
a branch-and-cut used in LINDO.

Could you please send out the MPS file to me? (If, of course, your model
is not a top secret :+) In the future I'd like to make a free collection
of LP/MIP instances.

>To be truly usefull to me I would need an API for GLPK similar to the
>API's found in many commercial products, i.e. something like
>void loadProblem
> (
>  int m,
>  int n,
>  int *Cst,
>  int *Clg,
>  int *Rnr,
>  double *Elm,
>  double *l, 
>  double *u,
>  double *blower, 
>  double *bupper,   
>  double *c,
>  int objective_direction,
>  int *var_type
>void getPrimalSolution(double *x)
>I could implement this interface myself using the existing API, however
>it seems wastefull to me to give names to every row and column in this
>case. I could also try to set up the datastructure of GLPK directly, but
>this I suppose will be much faster to do for somebody which is already
>familiar with the code. So my question is: "Are there any plans to add
>API routines like this to GLPK?"

You can try the low level access to GLPK. Here is a template example:

#include <glplp.h>   --->  LP/MIP low level data structures
#include <glprsm.h>  --->  revised simplex
#include <glpbbm.h>  --->  branch-and-bound

LP *build_problem(...)
{     LP *lp;
      int m, n, mip, i, j;
      m = <number of rows>;
      n = <number of columns>;
      mip = <0 for pure LP, 1 for MIP>;
      lp = create_lp(m, n, mip);
      if (mip) for (j = 1; j <= n; j++)
         lp->kind[j] = <0 for continuous column, 1 for integer one>;
      for (i = 1; i <= m; i++)
      {  lp->type[i] = <type of i-th row>;
         lp->lb[i] = <lower bound of i-th row or 0.0>;
         lp->ub[i] = <upper bound of i-th row or 0.0>;
         for (j = ...)
            new_elem(lp->A, i, j, <non-zero coefficient a[i,j]>);
      for (j = 1; j <= n; j++)
      {  lp->type[m+j] = <type of j-th column>;
         lp->lb[m+j] = <lower bound of j-th column or 0.0>;
         lp->ub[m+j] = <upper bound of j-th column or 0.0>;
      lp->dir = <'-' for minimization or '+' for maximization>;
      lp->c[0] = <constant term of the objective function or 0.0>;
      for (j = 1; j <= n; j++)
         lp->c[j] = <objective coefficient at j-th column>;
      check_lp(lp); /* to check LP struct for correctness */
      show_mat(lp->A, 1, "a.bmp"); /* to look at the matrix pattern */
      check_mat(lp->A); /* to check matrix for correctness */
      return lp;

void solve_problem(LP *lp, LPSOL *sol)
{     /* obtain LP relaxation */
      {  struct rsm1_cp cp;
         cp.what = 2;
         cp.form = 1;
         cp.scale = 1;
         cp.dual = 0;
         cp.steep = 1;
         cp.relax = 1;
         cp.tol_bnd = 1e-8;
         cp.tol_dj = 1e-7;
         cp.tol_piv = 1e-10;
         cp.iter_max = 0;
         cp.round = 0;
         if (rsm1_driver(mip, sol, &cp) != 0) ... <error> ...
         if (sol->status != 'O') ... <error> ...
      /* obtain MIP solution */
      {  struct bbm1_cp cp;
         cp.what = 2;
         cp.branch = BB_DRTOM;
         cp.btrack = BB_BESTP;
         cp.tol_int = 1e-6;
         cp.tol_obj = 1e-7;
         cp.form = 1;
         cp.steep = 1;
         cp.relax = 1;
         cp.tol_bnd = 1e-8;
         cp.tol_dj = 1e-7;
         cp.tol_piv = 1e-10;
         cp.iter_max = 0;
         cp.round = 1;
         if (bbm1_driver(mip, sol, &cp) != 0) ... <error> ...
         if (sol->status != 'O') ... <error> ...

int main(...)
{     LP *lp;
      LPSOL *sol;
      /* build LP/MIP problem block */
      lp = build_problem(...);
      /* create LP/MIP solution block */
      sol = create_lpsol(lp->m, lp->n);
      /* solve problem */
      solve_problem(lp, sol);
      /* process solution */

Although the low level LP/MIP routines are not documented yet, they are
provided with detailed comments (see the partitions GLPLP, GLPRSM,
and GLPBBM). If you will have any questions about these routines, please
contact me.


Andrew Makhorin

reply via email to

[Prev in Thread] Current Thread [Next in Thread]