GLPK
GLPK.js wrapped for Meteor. Problems may be provided in CPLEX LP format or GMPL format.
For more information, see the GLPK Documentation or the GMPL Documentation. To learn a little about the theory, have a look at this.
Table of Contents
Install
This is available as convexset:glpk on Atmosphere. (Install with meteor add convexset:glpk.)
Usage
The general process is to create a web worker, start a solution pass and wait for the result. See the included example Meteor app for a more detailed example or play with a deployed version.
GLPK.createWorker(loggingCB, postsolveLoggingCB, completionCB, errorCB, intOptCB)
-
loggingCB: logs messages such asReading model section from null ... 57 lines were read Reading data section from null ... 21 lines were read Generating phi... Generating psi... Generating obj... Model has been successfully generated Scaling... A: min|aij| = 1 max|aij| = 54 ratio = 54 GM: min|aij| = 0.5024965815329516 max|aij| = 1.9900632894841375 ratio = 3.9603518961524267 EQ: min|aij| = 0.2660380370764144 max|aij| = 1.0000000000000002 ratio = 3.7588609921699625 GLPK Simplex Optimizer, v4.49 17 rows, 64 columns, 192 non-zeros Preprocessing... 16 rows, 64 columns, 128 non-zeros Scaling... A: min|aij| = 1 max|aij| = 1 ratio = 1 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 16 0: obj = 224 infeas = 7 (0) *13: obj = 175 infeas = 0 (0) *26: obj = 76 infeas = 0 (0) OPTIMAL SOLUTION FOUND GLPK Integer Optimizer, v4.49 17 rows, 64 columns, 192 non-zeros 0 integer variables, none of which are binary Preprocessing... 16 rows, 64 columns, 128 non-zeros 0 integer variables, none of which are binary Scaling... A: min|aij| = 1 max|aij| = 1 ratio = 1 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 16 Solving LP relaxation... GLPK Simplex Optimizer, v4.49 16 rows, 64 columns, 128 non-zeros 26: obj = 224 infeas = 7 (0) *45: obj = 175 infeas = 0 (0) *72: obj = 76 infeas = 0 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... +72: mip = not found yet >= -inf (1; 0) +72: >>>>> 76 >= 76 0.0% (1; 0) +72: mip = 76 >= tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Agent Task Cost 1 1 13 2 8 8 3 7 13 4 5 12 5 2 6 6 6 16 7 4 3 8 3 5 ---------------------- Total: 76 Model has been successfully processed -
postsolveLoggingCB: reports messages arising from the postsolve step (if applicable), for example...Agent Task Cost 1 1 13 2 8 8 3 7 13 4 5 12 5 2 6 6 6 16 7 4 3 8 3 5 ---------------------- Total: 76 Model has been successfully processed -
completionCB: called when the solve is complete. See Info for an example of the payload, which is identical to what is returned by thejobBundle.solution()call -
errorCB: called on error, called with the error message as argument -
intOptCB: called on each integer optimization action, here is an example payload...1{ 2 "reason": 2, 3 "reasonDescription": "better integer solution found", 4 "gap": 0.007662835249042145, 5 "mipObjective": 261, 6 "numCallbacks": 877, 7 "iterationCount": 542, 8 "treeInfo": { 9 "numActiveNodes": 131, 10 "numNodes": 272, 11 "totalNodesIncludingRemoved": 283 12 } 13}where the reason codes can be read via
GLPK.getCodeDescription("reason codes", val).description, though that is not necessary at this stage. For a listing, here is an excerpt from the description of constants:1"GLP_IROWGEN": {value: 0x01, description: "request for row generation"}, 2"GLP_IBINGO": {value: 0x02, description: "better integer solution found"}, 3"GLP_IHEUR": {value: 0x03, description: "request for heuristic solution"}, 4"GLP_ICUTGEN": {value: 0x04, description: "request for cut generation"}, 5"GLP_IBRANCH": {value: 0x05, description: "request for branching"}, 6"GLP_ISELECT": {value: 0x06, description: "request for subproblem selection"}, 7"GLP_IPREPRO": {value: 0x07, description: "request for preprocessing"},
CPLEX LP Format
1var isMIP = true; 2var jobBundleLP = GLPK.createWorker( 3 // process regular logging messages 4 msg => console.log('[glpk.js|log]', msg), 5 // process post processing output 6 null, // not necessary here 7 // completion callback 8 function(info) { 9 console.info('All done.', info); 10 }, 11 // completion callback 12 function(info) { 13 console.info('Error.', info); 14 }, 15 // integer optimization callback 16 function(info) { 17 if (info.reason === GLPK.CONSTANTS.GLP_IBINGO) { 18 // filter for messages of interest 19 console.info('Int Opt Callback.', info); 20 } 21 }, 22); 23jobBundleLP.solveLP(lpProblemSourceCode, isMIP);
GMPL Format
1var isMIP = true; 2var jobBundleMPL = GLPK.createWorker( 3 // process regular logging messages 4 msg => console.log('[glpk.js|log]', msg), 5 // process post processing output 6 msg => console.log('[glpk.js|postsolve]', msg), 7 // completion callback 8 function(info) { 9 console.info('All done.', info); 10 }, 11 // completion callback 12 function(info) { 13 console.info('Error.', info); 14 }, 15 // integer optimization callback 16 function(info) { 17 if (info.reason === GLPK.CONSTANTS.GLP_IBINGO) { 18 // filter for messages of interest 19 console.info('Int Opt Callback.', info); 20 } 21 }, 22); 23jobBundleMPL.solveMPL(mplModelSourceCode, mplDataSourceCode, isMIP);
More Information
Descriptions of constants can be obtained from their codes via GLPK.getCodeDescription(category, code). Available categories:
"optimization direction flag""MPS file format""additional row attribute""kind of structural variable""integer optimizer control parameter""solution indicator""assignment problem formulation""status of auxiliary/structural variable""type of auxiliary/structural variable""solution status""simplex method control parameter""branch selection indicator""interior-point solver control parameter""enable/disable flag""row class descriptor""reason codes""condition indicator""scaling options""return codes""basis factorization control parameter"
After creating a worker with GLPK.createWorker, the object returned implements the following:
jobBundleLP.solveLP(lpProblemSourceCode, isMIP, mipParams): starts a solve using model and data files in CPLEX LP formatisMIP: whether to also solve as MIP once LP relaxation solved (default:true)mipParams: provides updates to default values of integer optimization control parameters (defaults:{})
jobBundleMPL.solveMPL(mplModelSourceCode, mplDataSourceCode, isMIP, mipParams): starts a solve using model and data files in MPL formatisMIP: whether to also solve as MIP once LP relaxation solved (default:true)mipParams: provides updates to default values of integer optimization control parameters (defaults:{})
jobBundle.isStarted(): reports whether the solution process has startedjobBundle.primalSolutionValueLP(): returns the primal solution value of the LP solutionjobBundle.dualSolutionValueLP(): returns the dual solution value of the LP solutionjobBundle.primalSolutionValueMIP(): returns the primal solution value of the MIP solutionjobBundle.solution(): returns the solution in the following format...
1{ 2 "lp": { 3 "cols": { 4 "x": { 5 "idx": 1, 6 "lb": -1, 7 "ub": 1, 8 "objCoeff": 1, 9 "type": 4, // Get description via: GLPK.getCodeDescription("type of auxiliary/structural variable", val).description 10 "stat": 1, // Get description via: GLPK.getCodeDescription("status of auxiliary/structural variable", val).description 11 "primal": 0.5, 12 "dual": 0, 13 "kind": 1 // Get description via: GLPK.getCodeDescription("kind of structural variable", val).description 14 }, 15 "y": { 16 "idx": 2, 17 "lb": -1, 18 "ub": 1, 19 "objCoeff": 1, 20 "type": 4, 21 "stat": 1, 22 "primal": 0.5, 23 "dual": 0, 24 "kind": 1 25 }, 26 "a": { 27 "idx": 3, 28 "lb": -1.7976931348623157e+308, 29 "ub": 1.7976931348623157e+308, 30 "objCoeff": 2, 31 "type": 1, 32 "stat": 1, 33 "primal": 1.5, 34 "dual": 0, 35 "kind": 1 36 } 37 }, 38 "rows": { 39 "blah_x": { 40 "type": 3, // Get description via: GLPK.getCodeDescription("type of auxiliary/structural variable", val).description 41 "lb": -1.7976931348623157e+308, 42 "ub": 3, 43 "stat": 3, // Get description via: GLPK.getCodeDescription("status of auxiliary/structural variable", val).description 44 "primal": 3, 45 "dual": 0.3333333333333333, 46 "coeffs": [ // column index (they start from 1) 47 [1, 1], // and coefficient 48 [2, 2], 49 [3, 1] 50 ] 51 }, 52 "blah_y": { 53 "type": 3, 54 "lb": -1.7976931348623157e+308, 55 "ub": 3, 56 "stat": 3, 57 "primal": 3, 58 "dual": 0.33333333333333337, 59 "coeffs": [ 60 [1, 2], 61 [2, 1], 62 [3, 1] 63 ] 64 }, 65 "bounds_a_lb": { 66 "type": 2, 67 "lb": -1.5, 68 "ub": 1.7976931348623157e+308, 69 "stat": 1, 70 "primal": 1.5, 71 "dual": 0, 72 "coeffs": [ 73 [3, 1] 74 ] 75 }, 76 "bounds_a_ub": { 77 "type": 3, 78 "lb": -1.7976931348623157e+308, 79 "ub": 1.5, 80 "stat": 3, 81 "primal": 1.5, 82 "dual": 1.3333333333333335, 83 "coeffs": [ 84 [3, 1] 85 ] 86 } 87 }, 88 "optimization_direction": 2, // Get description via: GLPK.getCodeDescription("optimization direction flag", val).description 89 "objective": 4, 90 "status": 5, // Get description via: GLPK.getCodeDescription("solution status", val).description 91 "dual_stat": 2, // Get description via: GLPK.getCodeDescription("solution status", val).description 92 "primal_stat": 2, // Get description via: GLPK.getCodeDescription("solution status", val).description 93 "return_code": 0 // Get description via: GLPK.getCodeDescription("return codes", val).description 94 }, 95 "mip": { 96 "cols": { 97 "x": { 98 "idx": 1, 99 "lb": -1, 100 "ub": 1, 101 "objCoeff": 1, 102 "type": 4, 103 "stat": 1, 104 "primal": 0.6666666666666666, 105 "dual": 0, 106 "kind": 1 107 }, 108 "y": { 109 "idx": 2, 110 "lb": -1, 111 "ub": 1, 112 "objCoeff": 1, 113 "type": 4, 114 "stat": 1, 115 "primal": 0.6666666666666667, 116 "dual": 0, 117 "kind": 1 118 }, 119 "a": { 120 "idx": 3, 121 "lb": -1.7976931348623157e+308, 122 "ub": 1.7976931348623157e+308, 123 "objCoeff": 2, 124 "type": 1, 125 "stat": 1, 126 "primal": 1, 127 "dual": 0, 128 "kind": 2 129 } 130 }, 131 "rows": { 132 "blah_x": { 133 "type": 3, 134 "lb": -1.7976931348623157e+308, 135 "ub": 3, 136 "stat": 3, 137 "primal": 3, 138 "dual": 0.3333333333333333, 139 "coeffs": [ 140 [1, 1], 141 [2, 2], 142 [3, 1] 143 ] 144 }, 145 "blah_y": { 146 "type": 3, 147 "lb": -1.7976931348623157e+308, 148 "ub": 3, 149 "stat": 3, 150 "primal": 3, 151 "dual": 0.33333333333333337, 152 "coeffs": [ 153 [1, 2], 154 [2, 1], 155 [3, 1] 156 ] 157 }, 158 "bounds_a_lb": { 159 "type": 2, 160 "lb": -1.5, 161 "ub": 1.7976931348623157e+308, 162 "stat": 1, 163 "primal": 1, 164 "dual": 0, 165 "coeffs": [ 166 [3, 1] 167 ] 168 }, 169 "bounds_a_ub": { 170 "type": 3, 171 "lb": -1.7976931348623157e+308, 172 "ub": 1.5, 173 "stat": 3, 174 "primal": 1, 175 "dual": 1.3333333333333335, 176 "coeffs": [ 177 [3, 1] 178 ] 179 } 180 }, 181 "optimization_direction": 2, 182 "objective": 3.3333333333333335, 183 "status": 5, 184 "dual_stat": 2, 185 "primal_stat": 2, 186 "return_code": 0 187 } 188}
for the following model in CPLEX LP format
\* Objective function *\ Maximize obj: x + y + 2 a Subject To blah_x: x + 2 y + a <= 3 blah_y: 2 x + y + a <= 3 bounds_a_lb: a >= -1.5 bounds_a_ub: a <= 1.5 Bounds -1 <= x <= 1 -1 <= y <= 1 a free Integer a