[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Easiest interface
From: |
Marcin Mucha |
Subject: |
Re: [Help-glpk] Easiest interface |
Date: |
Thu, 18 Feb 2010 17:08:02 +0100 |
Thanks for the answer.
I am thinking about asking them to implement something like an
LP-rounding algorithm for
weighted vertex cover, or some other simple algorithm like that. That
includes: implementing
the creation of the LP program corresponding to a given graph, running
the LP solver, and then
rounding the solution obtained from the solver. Doing this using
external files as opposed to
manipulating the data directly in the memory seems a bit awkward...
Marcin
On Thu, Feb 18, 2010 at 2:23 PM, Andrew Makhorin <address@hidden> wrote:
>> Hi all, not sure if this is the right forum to ask that question, but
>> will try anyway.
>
>> I am planning on doing a short workshop on approximation algorithms,
>> including LP based methods for talented high school students and I
>> would like to give them some simple programming tasks to get the
>> flavour of how LP based methods work. The problem is I will not have
>> much time and I am wondering if there exists some sort of easy to
>> grasp interface to glpk, so that you can easily get going in, say,
>> 10-20 minutes, assuming you have a decent grasp of C/C++. I myself use
>> glpk directly, but I remember that it was a bit hard at the beginning.
>> Also, maybe a different tool would be a better choice? However we will
>> postprocess the results of the LP solver, so it is important that the
>> tool works non-interactively.
>
> Below here is an easy example of application program using glpk api.
> It reads lp instance from a text file in cplex lp format, solves it
> with the primal simplex, and writes optimal solution to a text file in
> printable format. Probably it might be a starting point for beginners.
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <glpk.h>
>
> int main(int argc, char *argv[])
> { glp_prob *P;
> int ret;
> if (argc != 2)
> { printf("Usage: %s lp-file\n", argv[0]);
> return 0;
> }
> P = glp_create_prob();
> ret = glp_read_lp(P, NULL, argv[1]);
> if (ret != 0) return 1;
> glp_simplex(P, NULL);
> glp_print_sol(P, "sol");
> glp_delete_prob(P);
> return 0;
> }
>
> Reading problem data from `plan.lp'...
> 8 rows, 7 columns, 48 non-zeros
> 39 lines were read
> GLPK Simplex Optimizer, v4.43
> 8 rows, 7 columns, 48 non-zeros
> 0: obj = 8.000000000e+01 infeas = 2.811e+03 (1)
> * 4: obj = 4.376770833e+02 infeas = 0.000e+00 (0)
> * 10: obj = 2.962166065e+02 infeas = 0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> Writing basic solution to `sol'...
>
> (Example lp data file 'plan.lp' is included in the distribution and
> can be found in subdirectory glpk/examples.)
>
>
>
>
--
Dwell not on close decisions, and thus, when you play against
dwellers, you will make reciprocal gains in energy conservation and
sanity preservation.
Tommy Angelo