best Python interface for GLPK

[Joshua Friedman]

I have tried pymprog and while 0-1 integer programs and linear programs
seems to work great, there might be a bug in integer programs. Is there a
good interface for python I can use to teach my students. I also need to
use sensitivity reports.
Thanks

-- 
Joshua Friedman PhD
crownea...@gmail.com
http://www.math.sunysb.edu/~joshua

Re: [Help-glpk] MODELING A OBJECTIVE FUNCTION WITH SOFT CONSTRAINTS.

[Joshua Friedman]

Your question is not mathematically clear enough for me to understand it.
Try asking it in math notation.

On Wed, Aug 15, 2018, 10:05 AM Joao Pedro  wrote:

> Hello,
>
> I'm currently trying to model a large scale school timetabling problem. My
> current objective function tries to maximize the set of teacher preferences
> allocated in the final solution. But, there is a problem, every course has
> a specific shift that it happens but sometimes that are classes that needs
> to be taken in another shift.
>
> For example, the engineers can mainly take classes in the morning but
> sometimes that are classes that needs to be taken in the afternoon. This
> situation happens with a specif set of courses in which the total sum of
> daily classes on a week exceeds the total possible number of classes on a
> week.
>
> I'm trying to model this situation:
>
> An objective function that maximizes the teachers preferences -
> (minus)*(weight)*a soft constraint that allows these specific courses to
> take classes outside their main shift.
>
> I mean: If a a course that only takes classes in the morning happens to
> have some clases in the afternoon, this can be done but it will cause a
> penalty to be added in the objective function.
>
> The problem is that it doesn't seems to be working, the model just
> allocates a lot of classes in this extra shifts independent of the weight
> that i put in the soft constraint, it seems like it's somehow better to
> have this penalties instead of avoiding them as much as possible.
>
> What could be possible to change?
> ___
> Help-glpk mailing list
> Help-glpk@gnu.org
> https://lists.gnu.org/mailman/listinfo/help-glpk
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] TRYING TO GET A NON-OPTMIAL SOLUTION OF A MIP MODEL.

[Joshua Friedman]

Michael
The technique you described of relaxing all but 1-2 days and fixing the
integer part sounds interesting. Are there any published works implenting
the technique. I am also working on a timetabling/student enrollment
problem at my college.

On Wed, Jun 13, 2018, 9:50 AM Michael Hennebry <
henne...@web.cs.ndsu.nodak.edu> wrote:

> On Tue, 12 Jun 2018, João Pedro de Sá Moreira wrote:
>
> > I?m currently working on a timetable model that is supposed to deal if a
> pretty big number of variables.
> >
> > On initial tests i can see it takes a fair time to get to a LP solution
> (about 30m) and then it starts to work on finding the optimal integer
> solution.
> >
> > The problem is that in this part, it takes about 5h working on analyzing
> the whole tree, but the strange thing is that it keeps showing the same
> value every iteration it does until it gets to the end of the tree. The
> value it shows is the same value that can be seen when it finds the lp
> solution, does it means that the LP solution was the optimal since the
> beginning? Am i able to interrupt the execution and take a look at this
> solution? Or is there a way to speed it up a little bit?
>
> I suspect the problem is a lot of near-equivalent solutions.
> Best-first can be truly horrible on some such things.
> Try depth-first.
>
> If you have what amounts to 40 loosely connected subproblems,
> each with five nearly optimal solutions.
> Best-first could grind away for a very long time.
>
> Another possibility is to do the problem in stages.
> For the first stage,
> require only the first two days' variables to be integer.
> For the second stage,
> fix the first day's integers from the first stage
> and require only the second and third days' variables to be integer.
>
> If you know the problem has a solution,
> how do you know?
> That might provide a mechanism for getting a solution.
> ___
> Help-glpk mailing list
> Help-glpk@gnu.org
> https://lists.gnu.org/mailman/listinfo/help-glpk
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] TRYING TO GET A NON-OPTMIAL SOLUTION OF A MIP MODEL.

[Joshua Friedman]

I believe glpk is too slow for timetable problems like yours. Try Gurobi.

On Tue, Jun 12, 2018, 8:05 PM João Pedro de Sá Moreira <
jopmoreir...@gmail.com> wrote:

> I’m currently working on a timetable model that is supposed to deal if a
> pretty big number of variables.
>
>
>
> On initial tests i can see it takes a fair time to get to a LP solution
> (about 30m) and then it starts to work on finding the optimal integer
> solution.
>
>
>
> The problem is that in this part, it takes about 5h working on analyzing
> the whole tree, but the strange thing is that it keeps showing the same
> value every iteration it does until it gets to the end of the tree. The
> value it shows is the same value that can be seen when it finds the lp
> solution, does it means that the LP solution was the optimal since the
> beginning? Am i able to interrupt the execution and take a look at this
> solution? Or is there a way to speed it up a little bit?
>
>
>
> I’ve alreay tried –tmlim and it worked but the solution couldn’t be
> returned. Then i tried –nopresol and –output but the problem is that the
> output returned a “INTEGER UNDEFINED” status.
>
>
>
> That’s the part of the model where it finds the optmial LP solution:
>
>
>
> Solving LP relaxation...
>
> GLPK Simplex Optimizer, v4.65
>
> 15202 rows, 138924 columns, 555696 non-zeros
>
>   0: obj =  -0.0e+00 inf =   3.194e+03 (620)
>
> Perturbing LP to avoid stalling [401]...
>
>2722: obj =   8.75000e+02 inf =   1.930e+02 (52) 2
>
>4678: obj =   8.951560756e+02 inf =   1.026e+01 (9) 11
>
>4915: obj =   9.000461789e+02 inf =   8.944e-06 (0) 1
>
> *  6780: obj =   9.391853182e+02 inf =   7.886e-06 (49431) 11
>
> Removing LP perturbation [8499]...
>
> *  8499: obj =   9.68000e+02 inf =   1.588e-14 (0) 10
>
> OPTIMAL LP SOLUTION FOUND
>
>
>
> Then it begins the integer optmization and keeps on working and 5 hours
> later:
>
>
>
> .
>
> .
>
> .
>
> + 86591: mip = not found yet <=   9.68000e+02(1184; 0)
>
> + 86616: mip = not found yet <=   9.68000e+02(1187; 0)
>
> + 86651: mip = not found yet <=   9.68000e+02(1191; 0)
>
> + 86727: mip = not found yet <=   9.68000e+02(1195; 0)
>
> + 86818: mip = not found yet <=   9.68000e+02(1205; 0)
>
> Time used: 18130.5 secs.  Memory used: 313.8 Mb.
>
> + 86874: >   9.68000e+02 <=   9.68000e+02   0.0% (1213; 0)
>
> + 86874: mip =   9.68000e+02 <= tree is empty   0.0% (0; 2425)
>
> INTEGER OPTIMAL SOLUTION FOUND
>
> Time used:   18154.2 secs
>
> Memory used: 413.6 Mb (433691909 bytes)
>
>
>
> Then the timetable is shown.
>
>
>
> Any tips? Thanks in advance.
>
>
>
>
>
>
>
>
>
>
>
>
>
> Enviado do Email  para
> Windows 10
>
>
>
>
> 
>  Livre
> de vírus. www.avast.com
> .
> <#m_-3075016419714778253_DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
> ___
> Help-glpk mailing list
> Help-glpk@gnu.org
> https://lists.gnu.org/mailman/listinfo/help-glpk
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] minisat mathprog and python/glpk

[Joshua Friedman]

I found that using python/glpk instead of mathprog is usually more
convenient. I was wondering if there is a way to use modelling from
python/glpk to interface with minsat?

I like the way mathprog can model SAT problems, but the benefits of python
are so huge that I need to stick with python over mathprog for a real
application.

-- 
Joshua Friedman PhD
crownea...@gmail.com
http://www.math.sunysb.edu/~joshua
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Parallel runs of glpk

[Joshua Friedman]

It is not a GLPK solution, but I am trying to solve a binary IP with
10+ vars and constraints, and I have experimented with every solver out
there, GLPK, CBC, SCIP, CPLEX, and GUROBI.
CBC is free and can be compiled to run on multiple threads (you have to
choose that when configuring).

I think GLPK is great as a learning tool, I am using it in my Operations
Research courses that I teach, but if you need to solve something that
needs parallel runs, you probably need something with faster algorithms.


On Wed, Dec 14, 2016 at 9:06 AM, Mathieu Dutour 
wrote:

> I am interested in running glpk from a multithreaded program.
> The goal is not to have GLPK itself parallel but instead to
> have glpk used many times by different threads for solving
> many different linear programs.
>
> As is well known glpk is not thread safe and my question
> is about alternative solution to that problem. Here are some
> possibilities:
>
> A) One is to have to run glpsol standalone by running it
> as external program with the input file generated by the thread
> and then read by the thread. But this solution has its costs
> in terms of runtime. It is easy to program.
>
> B) Have one thread that does only call glpk. It is adequate
> in single threaded performance but potentially expensive
> since some thread may wait. Relatively easy to program.
>
> C) Use shared memory to exchange data. That is multiple
> number of individual programs running glpk and getting their
> data from shared memory.
>
> Any other solution? Is there any implementation that you
> would recommend?
>
>   Mathieu
>
> ___
> Help-glpk mailing list
> Help-glpk@gnu.org
> https://lists.gnu.org/mailman/listinfo/help-glpk
>
>


-- 
Joshua Friedman PhD
crownea...@gmail.com
http://www.math.sunysb.edu/~joshua
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] GNU MathProg language reference?

[Joshua Friedman]

I went from knowing nothing about mathprog to quite a lot looking at the
examples at
 https://www3.nd.edu/~jeff/mathprog/

On Wed, Sep 14, 2016 at 6:33 AM, Balaco Baco  wrote:

> > I found them googling  glpk and gmpl.
>
> Google locks its users in a bubble of results that is possibly different
> for other users. Further, I would not use "gmpl" as a search term. I tried
> to search a bit for this documentation, nothing seemed to be what I wanted
> (and I could have seen it, since it is contained in GLPK). Google does not
> respect at all the privacy of users, far from that.
>
> As a side suggestion, use Duckduckgo.com as your main search engine. It
> has perfect results for most things I do. It respects your privacy. And it
> has "tricks" to search in several other main search engines, if we are
> searching for something hard to find.
>
>
>
>
> ___
> Help-glpk mailing list
> Help-glpk@gnu.org
> https://lists.gnu.org/mailman/listinfo/help-glpk
>



-- 
Joshua Friedman PhD
crownea...@gmail.com
http://www.math.sunysb.edu/~joshua
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] performance issue

[Joshua Friedman]

I tried the --fpump option, and it still ran slow.  By the way, I am
writing in mathprog, converting to LP format, and then solving in Gurobi.
Is there an easier way? I guess I can write some python scripts to get the
variables into a post solver program, but I would think there is a simpler
solution?

On Wed, Sep 7, 2016 at 10:55 AM, Giorgio Sartor  wrote:

> Have you tried option --fpump?
> The heuristic part of GLPK (the one able to find feasible solutions
> quickly) is not as strong as the MIP engine. We are working on that. ;-)
>
> - G. S. -
>
> On 7 Sep 2016, at 9:44 PM, Joshua Friedman  wrote:
>
> I am working on a bit integer program and my data has 45000 variables (see
> below). I am basically  just looking for a feasible solution, my objective
> is constant.
>
> My question: it took 10 minutes to run using the glpk solver. I converted
> to a CBC form and it solved it in 1 minute, and using Gurobi it took about
> 1 second (but it used all 8 threads).  Am I doing something wrong with glpk
> for bit integer programs?  Is there an option that is more efficient?
>
> Model has been successfully generated
> GLPK Integer Optimizer, v4.60
> 68514 rows, 45040 columns, 372605 non-zeros
> 45040 integer variables, all of which are binary
> Preprocessing...
> 9020 hidden covering inequaliti(es) were detected
> 1397 constraint coefficient(s) were reduced
> 15253 rows, 29410 columns, 161743 non-zeros
> 29410 integer variables, all of which are binary
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  1.000e+01  ratio =  1.000e+01
> Problem data seem to be well scaled
> Constructing initial basis...
> Size of triangular part is 15253
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.60
> 15253 rows, 29410 columns, 161743 non-zeros
>   0: obj =   0.0e+00 inf =   6.040e+02 (247)
> 500: obj =   0.0e+00 inf =   3.980e+02 (115) 1
> 837: obj =   0.0e+00 inf =   0.000e+00 (0) 1
> OPTIMAL LP SOLUTION FOUND
> Integer optimization begins...
> +   837: mip = not found yet >=  -inf(1; 0)
> +  1389: mip = not found yet >=   0.0e+00(30; 0)
> +  2309: mip = not found yet >=   0.0e+00(50; 7)
> +  2835: mip =     not found yet >=   0.0e+00(77; 14)
> +  3106: mip = not found yet >=   0.0e+00(113; 14)
>
>
> --
> Joshua Friedman PhD
>
> crownea...@gmail.com
> http://www.math.sunysb.edu/~joshua
>
> ___
> Help-glpk mailing list
> Help-glpk@gnu.org
> https://lists.gnu.org/mailman/listinfo/help-glpk
>
>


-- 
Joshua Friedman PhD
crownea...@gmail.com
http://www.math.sunysb.edu/~joshua
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] performance issue

[Joshua Friedman]

I am working on a bit integer program and my data has 45000 variables (see
below). I am basically  just looking for a feasible solution, my objective
is constant.

My question: it took 10 minutes to run using the glpk solver. I converted
to a CBC form and it solved it in 1 minute, and using Gurobi it took about
1 second (but it used all 8 threads).  Am I doing something wrong with glpk
for bit integer programs?  Is there an option that is more efficient?

Model has been successfully generated
GLPK Integer Optimizer, v4.60
68514 rows, 45040 columns, 372605 non-zeros
45040 integer variables, all of which are binary
Preprocessing...
9020 hidden covering inequaliti(es) were detected
1397 constraint coefficient(s) were reduced
15253 rows, 29410 columns, 161743 non-zeros
29410 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+01  ratio =  1.000e+01
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 15253
Solving LP relaxation...
GLPK Simplex Optimizer, v4.60
15253 rows, 29410 columns, 161743 non-zeros
  0: obj =   0.0e+00 inf =   6.040e+02 (247)
500: obj =   0.0e+00 inf =   3.980e+02 (115) 1
837: obj =   0.0e+00 inf =   0.000e+00 (0) 1
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+   837: mip = not found yet >=  -inf(1; 0)
+  1389: mip = not found yet >=   0.0e+00(30; 0)
+  2309: mip = not found yet >=   0.0e+00(50; 7)
+  2835: mip = not found yet >=   0.0e+00(77; 14)
+  3106: mip = not found yet >=   0.0e+00(113; 14)


-- 
Joshua Friedman PhD

crownea...@gmail.com
http://www.math.sunysb.edu/~joshua
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk