|
| From: | Michael Bramley |
| Subject: | Re: [Help-glpk] Sizing the problem... |
| Date: | Sun, 3 Feb 2013 14:11:27 -0500 |
Thanks for the response, but I don’t think this applies as other solvers find a solution. You are right that supply / demand are [0,1]. Maybe the problem is just tooooooo large? Any ideas? From: Meketon, Marc [mailto:address@hidden I’ve never tried the “satisfiability” feature of GLPK, but this might work here. If Supply/Demand where “1”s, then I’m pretty sure this could be solved in GLPK (see the cnfsat.pdf documentation that comes with GLPK). If Supply/demand were greater than 1, I’m not so sure – perhaps someone who understands satisfiability problems better than me (that would be almost anyone) could comment. From: address@hidden [mailto:address@hidden] On Behalf Of Michael Bramley Hello: We have one example that runs without end. The model is listed below, and the data file contains 2,500 rows (or 4,779,594 bytes) of data. This defines the 834 source and destination params, followed by the 834x834 matrix of values for param dp. The data are so large that I did not attach them. When glpk is executed against these files, we get the following preamble (I included it so you have it). We always seem to have the warnings so ignored them (perhaps at our peril). I trust this is sufficient to help. GLPSOL: GLPK LP/MIP Solver, v4.48 Parameter(s) specified in the command line: -m MP_layout.mod -d MP_layout.dat -o MP_layout_results.txt Reading model section from MP_layout.mod... MP_layout.mod:19: warning: final NL missing before end of file MP_layout.mod:19: warning: unexpected end of file; missing end statement inserted 19 lines were read Reading data section from MP_layout.dat... MP_layout.dat:2508: warning: final NL missing before end of file MP_layout.dat:2508: warning: unexpected end of file; missing end statement inserted 2508 lines were read Generating total_dp... Generating Supply... Generating Demand... Generating morepair... Model has been successfully generated GLPK Integer Optimizer, v4.48 697225 rows, 695556 columns, 3455308 non-zeros 695556 integer variables, all of which are binary Preprocessing... 696390 rows, 694722 columns, 2778888 non-zeros 694722 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 696389 Solving LP relaxation... GLPK Simplex Optimizer, v4.48 696390 rows, 694722 columns, 2778888 non-zeros 0: obj = -1.951460560e+04 infeas = 5.817e+03 (1) Are we asking too much of glpk (sounds horrible to say)? MB set ORIG; # origins set DEST; # destinations param supply {ORIG}; # amounts available at origins param demand {DEST}; # amounts required at destinations param dp {ORIG,DEST}; # shipment costs per unit var Trans {ORIG,DEST} binary; # units to be shipped maximize total_dp: sum {i in ORIG, j in DEST} dp[i,j] * Trans[i,j]; subject to Supply {i in ORIG}: sum {j in DEST} Trans[i,j] =supply[i]; subject to Demand {j in DEST}: sum {i in ORIG} Trans[i,j] = demand[j]; subject to morepair {i in ORIG, j in DEST}: (Trans[i,j]+Trans[j,i]) <= 1; Michael Bramley tel: +1 513 632 0549 From: Jeffrey Kantor [mailto:address@hidden] Hi Michael, No invective here! Could you say a bit more about the problems that are not finding a solution? For example, the type of problem you're trying to solve, and some metrics regarding problem size, the number of integer and binary variables? Jeff On Sun, Feb 3, 2013 at 10:48 AM, Michael Bramley <address@hidden> wrote: Hello: We are using Linux glpk v4.48. This may be a school boy question, but I’ll ask and beg indulgence from those on the list. We have a number of LP/MIP problems that range in size. Most are quite manageable in glpk (yeah!!), while a small subset of others test the limits of glpk to either find a solution or run for days without a solution. Indeed, the annoying bit is that some problems just seem to run for days and days, while CPLEX seems to find an answer in minutes. Is there a way to determine this limit in advance, i.e. can we look at the problem and say that generates X conditions (or something else) and thus is not suited for glpk in its current state? Is there a way that we could build this into glpk as a pre-processing option? Looking for any ideas/help, and may even respond to invective. :) MB The contents of this message and any attachments to it are confidential and may be legally privileged.
The contents of this message and any attachments to it are confidential and may be legally privileged. This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation. The contents of this message and any attachments to it are confidential and may be legally privileged. |
| [Prev in Thread] | Current Thread | [Next in Thread] |