jvail / glpk.js Goto Github PK

Add more documentation

Installation

• npm install
• ...

API

• bounds
• upper & lower bounds explanation
• samples LP, MILP
• Add gh-pages?

Hi,

I've noticed that sometimes, glpk.js takes up to 5x more time to process a linear program than normal on Firefox. I've created a small example to show this: https://glpk-js-loop-test.surge.sh/. If you open up the console, I've set it to print whenever processing takes more than 55ms. If you right-click "View page source" and scroll down to line 1235 (everything before that is the linear program), you'll see that the web worker acts as a FIFO queue. The queue's throughput should be regular, but every few seconds there is an outlier of an order of around 5x. I'm wondering if this is a Firefox issue or if there is a setting in emscripten that would help fix this?

Thanks!
~Mike

Can this library be modified to support the GLPK Dual Simplex Solver?

I have no clue how to do this. I tried the following, but it results in the battery being charged higher then the capacity.
This is the problem:
I want an optimum charge/discharge scheme for my battery. In this example I have 8 hours, and in each hour the cost of energy varies. I start with an empty battery. I want to end with maximum profit (=minimum cost)

the State of Charge (SoC) of the battery can never exceed 5kWh, and has a minimum of 0. The battery can be loaded with a maximum of 2kW, and discharged with a maximum of 1.7kW.

const GLPK = require('glpk.js');
const glpk = GLPK();
const options = {
    msglev: glpk.GLP_MSG_ALL,
    presol: true,
    cb: {
        call: progress => console.log(progress),
        each: 1
    }
};

const maxSoC = 5; // kWh
const minSoC = 0; // kWh
const maxCharge = 2; // kW
const minCharge = -1.7; // kW (negative is discharging)

const startSoC = 0; // kWh (when 0, the battery is empty at start)
const prices = [ 0.1, 0.1, 0.2, 0.2, 0.3, 0.3, 0.5, 0.5, 0.5]; // prices per kWh for each hour

// optimized load per hour l1..l8 is what is being looked for
// objective function (minimize cost) totalCost = l1*p1 + l2*p2 + ... + l8*p8
// the State of Charge (SoC) of the battery can never exceed 5, and has a minimum of 0.


const toSolve = {
    name: 'LP',
    objective: {
        direction: glpk.GLP_MIN,
        name: 'totalCost',
        vars: [
            { name: 'l1', coef: prices[0] },
            { name: 'l2', coef: prices[1] },
            { name: 'l3', coef: prices[2] },
            { name: 'l4', coef: prices[3] },
            { name: 'l5', coef: prices[4] },
            { name: 'l6', coef: prices[5] },
            { name: 'l7', coef: prices[6] },
            { name: 'l8', coef: prices[7] },
        ]
    },
    subjectTo: [
        {
            name: 'SOC',
            vars: [
                { name: 'l1', coef: 1 },
                { name: 'l2', coef: 1 },
                { name: 'l3', coef: 1 },
                { name: 'l4', coef: 1 },
                { name: 'l5', coef: 1 },
                { name: 'l6', coef: 1 },
                { name: 'l7', coef: 1 },
                { name: 'l8', coef: 1 },
            ],
            bnds: { type: glpk.GLP_DB, ub: maxSoC, lb: minSoC }
        },
    ],
    bounds: [
        {
            name: 'l1',
            type: glpk.GLP_DB,
            ub: maxCharge,
            lb: minCharge
        },
        {
            name: 'l2',
            type: glpk.GLP_DB,
            ub: maxCharge,
            lb: minCharge
        },
        {
            name: 'l3',
            type: glpk.GLP_DB,
            ub: maxCharge,
            lb: minCharge
        },
        {
            name: 'l4',
            type: glpk.GLP_DB,
            ub: maxCharge,
            lb: minCharge
        },
        {
            name: 'l5',
            type: glpk.GLP_DB,
            ub: maxCharge,
            lb: minCharge
        },
        {
            name: 'l6',
            type: glpk.GLP_DB,
            ub: maxCharge,
            lb: minCharge
        },
        {
            name: 'l7',
            type: glpk.GLP_DB,
            ub: maxCharge,
            lb: minCharge
        },
        {
            name: 'l8',
            type: glpk.GLP_DB,
            ub: maxCharge,
            lb: minCharge
        }
    ]
}

const res = glpk.solve(toSolve, options);

I'm currently getting what appears to be a solution that violates a constraint that I set.

The constraint is this:

 Desc_LiquidOil_C_BIN_constraint: - Recipe_LiquidFuel_C
 - Recipe_Plastic_C - Recipe_Rubber_C - Recipe_PackagedCrudeOil_C
 - Recipe_UnpackageOil_C - Recipe_Alternate_HeavyOilResidue_C
 - Recipe_Alternate_PolymerResin_C + 1000000 Desc_LiquidOil_C_BIN >= 0

And the relevant values in the solution are this:

Recipe_LiquidFuel_C = 0
Recipe_Plastic_C = 0
Recipe_Rubber_C = 0
Recipe_PackagedCrudeOil_C = 0
Recipe_UnpackageOil_C = 0
Recipe_Alternate_HeavyOilResidue_C = 0.9375
Recipe_Alternate_PolymerResin_C = 0
Desc_LiquidOil_C_BIN = 0

Where Desc_LiquidOil_C_BIN is a binary variable and the others are real-valued.

So substituting into the constraint you get

-0 - 0 - 0 - 0 - 0 - 0.9375 - 0 + 1000000 * 0 >= 0
-0.9375 >= 0

Which is clearly false. Is this something weird about binary variables? I'm not sure where to even start debugging this. My ultimate goal is to have Desc_LiquidOil_C_BIN be set to 1 if any of the other variables are greater than zero.

Hello, in my project I need to solve many linear programming models in one run. When I solve too many models, I encounter the error below. It seems it is caused by the internal WASM program running out of memory. I am wondering if there is a way to deconstruct/release the glpk internal WASM after I solve each model?

TypeError: Cannot perform Construct on a detached ArrayBuffer

RuntimeError: abort(TypeError: Cannot perform Construct on a detached ArrayBuffer). Build with -s ASSERTIONS=1 for more info.
    at process.V (/Users/JayWong/[myfile].js:700:13)
    at process.emit (events.js:400:28)
    at processPromiseRejections (internal/process/promises.js:245:33)
    at processTicksAndRejections (internal/process/task_queues.js:96:32)

Hello! how can I include the shift term in the model?

for example: max z = x1 + x2 + 10

I want to include the 10 constant in the model

Thanks!

Making use of this package in a TypeScript project, inside of a WebWorker. At import, the GLPK type does not indicate it's a promise, nor does the result of glpk.solve, so at the moment I am typecasting to unknown and then the Promise<> type. Could you fix this?

This code in TypeScript

import GLPK from "glpk.js";

const glpk = GLPK();

Throws a compliation error:

This expression is not callable.
  Type 'typeof import("/my_app/node_modules/glpk.js/dist/glpk")' has no call signatures.ts(2349)

However, based on the documentation this seems like the correct way to initialise the library. Using // @ts-ignore, the library seems to work correctly. So I think this is an issue with the typings in dist/glpk.d.ts.

Specifically I'm using versions:

typescript: 4.9.4
glpk.js: 4.0.1

But think it applies on any modern version of TypeScript.

I am trying to compile the glpk 5.0 with emmake.
I got the following error messages:
Is there anything wong?

~/.../emcc/glpk-5.0$ emmake make -j4
make: make -j4
make  all-recursive
make[1]: Entering directory '/home/runner/microdes/emcc/glpk-5.0'
Making all in src
make[2]: Entering directory '/home/runner/microdes/emcc/glpk-5.0/src'
make[2]: Nothing to be done for 'all'.
make[2]: Leaving directory '/home/runner/microdes/emcc/glpk-5.0/src'
Making all in examples
make[2]: Entering directory '/home/runner/microdes/emcc/glpk-5.0/examples'
/nix/store/dsd5gz46hdbdk2rfdimqddhq6m8m8fqs-bash-5.1-p16/bin/bash ../libtool --tag=CC   --mode=link /nix/store/fif8p12nknb7cw8ffbxbsbrhr2gml3v4-emscripten-3.1.17/bin/emcc  -g -O2   -o glpsol glpsol.o ../src/libglpk.la -lm 
libtool: link: /nix/store/fif8p12nknb7cw8ffbxbsbrhr2gml3v4-emscripten-3.1.17/bin/emcc -g -O2 -o glpsol glpsol.o  ../src/.libs/libglpk.so -lm -Wl,-rpath -Wl,/home/runner/microdes/emcc/glpk-5.0/src/.libs
emcc: warning: ignoring unsupported linker flag: `-rpath` [-Wlinkflags]
error: undefined symbol: _glp_jdate (referenced by top-level compiled C/C++ code)
warning: Link with `-sLLD_REPORT_UNDEFINED` to get more information on undefined symbols
warning: To disable errors for undefined symbols use `-sERROR_ON_UNDEFINED_SYMBOLS=0`
warning: __glp_jdate may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_jday (referenced by top-level compiled C/C++ code)
warning: __glp_jday may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_mc13d (referenced by top-level compiled C/C++ code)
warning: __glp_mc13d may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_mc21a (referenced by top-level compiled C/C++ code)
warning: __glp_mc21a may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_strspx (referenced by top-level compiled C/C++ code)
warning: __glp_strspx may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_zlib_gzclose (referenced by top-level compiled C/C++ code)
warning: __glp_zlib_gzclose may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_zlib_gzerror (referenced by top-level compiled C/C++ code)
warning: __glp_zlib_gzerror may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_zlib_gzopen (referenced by top-level compiled C/C++ code)
warning: __glp_zlib_gzopen may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_zlib_gzread (referenced by top-level compiled C/C++ code)
warning: __glp_zlib_gzread may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
error: undefined symbol: _glp_zlib_gzwrite (referenced by top-level compiled C/C++ code)
warning: __glp_zlib_gzwrite may need to be added to EXPORTED_FUNCTIONS if it arrives from a system library
Error: Aborting compilation due to previous errors
emcc: error: '/nix/store/dj805sw07vvpbxx39c8g67x8qddg0ikw-nodejs-18.12.1/bin/node /nix/store/fif8p12nknb7cw8ffbxbsbrhr2gml3v4-emscripten-3.1.17/share/emscripten/src/compiler.js /tmp/tmpkcm_99x6.json' failed (returned 1)
make[2]: *** [Makefile:296: glpsol] Error 1
make[2]: Leaving directory '/home/runner/microdes/emcc/glpk-5.0/examples'
make[1]: *** [Makefile:321: all-recursive] Error 1
make[1]: Leaving directory '/home/runner/microdes/emcc/glpk-5.0'
make: *** [Makefile:252: all] Error 2
emmake: error: 'make -j4' failed (returned 2)

Besides the results of the variable column-objects in "vars" in the result JSON, it would be very good to also get the constraint row-objects in a seperate array in the result.
Bascially one need to add
glp_mip_row_val = cwrap('glp_mip_row_val', 'number', ['number', 'number']),
as a constant at the top and adjust the result template and writing in the solve() function.
I think this should be rather easy. Is that possible?

Compile with emcc modularization and es6 options.

There are some important features in the original glpk that is not present in this repo. I understand the plan is to keep it simple but I think a couple of features worth adding.

• glpk.js doesn't return shadow price information in LP problems.
• we can't pass any solver setting such as tmLim or mipGap to control the solution procedure.

I forked this repo (https://github.com/TakeScoop/glpk.js) and tried to address these issues. I added shadow prices to the output of LP solutions. I also added an object of solver settings to the API with values of mipGap, tmLim & msgLev which are the important ones.
I pass these settings as function args in glpk.js.c hardcoded. A better way would be to create an object of these settings in js and pass it to the solve_mip, but I couldn't manage to do it.

If these changes that I made are cool, I can create a PR to merge them back here.

cc. @rregue

This library is fantastic, it is very pleasant to use.

One thing I am a bit worried about is the size of the library, 1.05 MB according to webpack.
If I understand correctly, the entire glpk library is included in the package, even if the interface it exposes might not use all of glpk itself.

If this is correct, how hard would it be to trim down the WebAssembly to only the code that is required for the interface exposed? It sounds quite hard to me.

Are you aware of any JS library exposing a similar interface, but with a lighter memory footprint (possibly to the expense of speed)?

Hello
I love the library. It works great, however I am having some problems with large amounts of data. I get the message:

lp_set_mat_row: i = 1; ind[11] = 405; duplicate column indices not allowed
glpk.js?eval:4 Error detected in file glpapi01.c at line 776

glpk.js?eval:71179 Uncaught abort() at Error
at jsStackTrace (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:952:20)
at stackTrace (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:967:29)
at Object.abort (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:71173:51)
at _abort (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:2849:25)
at Array.xd (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:37338:52)
at $e (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:41804:23)
at Db (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:51335:13)
at ccallFunc (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:532:26)
at Object.Module.solve (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/lib/glpk.js?eval:71232:10)
at f.doMagic (https://webidetesting5757664-a2d39b03e.dispatcher.hana.ondemand.com/webapp/modules/material/material.controller.js?eval:390:49)
If this abort() is unexpected, build with -s ASSERTIONS=1 which can give more information.
abort @ glpk.js?eval:71179
_abort @ glpk.js?eval:2849
xd @ glpk.js?eval:37338
$e @ glpk.js?eval:41804
Db @ glpk.js?eval:51335
ccallFunc @ glpk.js?eval:532
Module.solve @ glpk.js?eval:71232
doMagic @ material.controller.js?eval:390
triggerOprimizerChange @ material.controller.js?eval:244
a.fireEvent @ EventProvider-dbg.js:229
a.fireEvent @ Element-dbg.js:427
(anonymous) @ ManagedObjectMetadata-dbg.js:428
B.ontap @ Button-dbg.js:263
a._handleEvent @ Element-dbg.js:162
U._handleEvent @ UIArea-dbg.js:786
dispatch @ jquery-dbg.js:4737
g @ jquery-mobile-custom-dbg.js:1972
q @ jquery-mobile-custom-dbg.js:2063
dispatch @ jquery-dbg.js:4737
c3.handle @ jquery-dbg.js:4549
trigger @ jquery-dbg.js:7819
(anonymous) @ jquery-dbg.js:7903
each @ jquery-dbg.js:365
each @ jquery-dbg.js:137
trigger @ jquery-dbg.js:7902
P @ jquery-mobile-custom-dbg.js:1543
R @ jquery-mobile-custom-dbg.js:1553
dispatch @ jquery-dbg.js:4737
c3.handle @ jquery-dbg.js:4549

Is there a way to solve GLPK through LP format instead of JSON in this library?

Currently there is no indications on how to set the variable type, even if there are some constants related to it (GLP_CV, GLP_IV, GLP_BV).

Peeking at the code I noticed that we can set lp.binaries to an array of variable names to set them as binary, but I think that this should be added to the README, along with how to set them as integer.

Thanks for the great library!

Add bundled (wasm file & worker script) versions for convenience.

#19

Is there any intention to support v5.0 in this project?

https://guix.gnu.org/packages/glpk-5.0/

Currently setting the "shift" does not seem to be supported from glpk.js. This can be added via the glp_set_obj_coef function with the index j == 0. See also the glpk documentation on the glp_set_obj_coef function. It could be added e.g. by giving the objective object a const element next to the vars array.

Hi,

I'm trying to run the glpk example in vuejs but run into:
Uncaught (in promise) TypeError: glpk.solve is not a function
Any ideas? Would this indicate the .wasm file is not loaded?

Was indeed the case. This can be closed
sorry for the confusion

Many thanks in advance,
-Jan

Can't install under node v10.x.

This project inherites an issue from the node-glpk module: hgourvest/node-glpk#6

glpk.solve({
  name: 'LP',
  objective: {
    direction: glpk.GLP_MIN,
    name: 'obj',
    vars: [{ name: 'x', coef: 1 }]
  },
  subjectTo: [
    {
      name: 'cons1',
      vars: [{ name: 'x', coef: 1.0 }],
      bnds: { type: glpk.GLP_LO, lb: -1.0 }
    }
  ]
})

should set x to -1 but x is set to 0

Module not found: Error: Can't resolve 'fs' in './node_modules/glpk.js'
Module not found: Error: Can't resolve 'path' ./node_modules/glpk.js'

rename glpk-worker.js to glpk.js and glpk.js to glpk-node.js so glpk (web) becomes the default

import glpk from 'glpk.js';

// solve is async and creates a worker internally 
const result = await glpk.solve(lp);

// ..or create a worker yourself
const glpkWorker = glpk.worker();

Hi!

First, thank you so much for this amazing package, it's a life saver!

I'm using glpk to synchronize audio graphs in web audio (check out https://klank-hello-world.surge.sh/ for an example). The rendering is slowed down needlessly because of the following message that is printed to the console:

Long-step dual simplex will be used

I did a bit of digging and it looks like GLPK accidentally shipped with this message printing even when debugging is turned off. It is reported here, for example.

There is a patch that fixes this here. It's a one-liner.

I was wondering if you could please apply this patch to your local glpk distro and rebuild?

Thank you!

For some reason, GLPK.GLP_FR is undefined. MWE is along the lines of the provided lp.html example

import GLPK from '../dist/glpk.js';
(async () => {
    const glpk = await GLPK();
    console.log(GLPK.GLP_FR); // "undefined"
})();

I ran into this when working with negative variables, as discussed in #29 . Through working with glpsol and converting MathProg problems into CPLEX files, I observed, that glpsol --wlp would include a Bounds section that labels the appropriate variables as free, effectively dropping the non-negativity constraint.

Setting the bounds field in the (javascript) lp definition by including appropriate {name: 'my_var', type: 1} (i.e. the value, GLPK.GLP_FR is supposed to be) objects fixed the issue.

PS: Thanks for this great wrapper library!

Hello @jvail, this package is so cool and helpful! I love the idea to use JSON interface to interact with LP solvers! Really appreciate your effort in making and maintaining it! 🤩

If I understand it correctly, this package compiles the GLPK source code from C to wasm, and then calls the wasm using webWorker from JS with user's JSON specifications. If the JS is calling from the browser, it decodes the wasm base64 string first.

I am wondering if it is possible to use CBC instead of GLPK for the backend solver? I am asking because CBC has a more permissive license (Eclipse Public License) comparing to GLPK (GPL). I heard CBC is faster than GLPK too.

Hello!

I've tried to test this library with a very simple situation: square 2x2, from -1.0 to 1.0 by both coordinates. I've corrected your lp.html test by replacing lp model:

const lp = {
                    name: 'LP',
                    objective: {
                        direction: glpk.GLP_MIN,
                        name: 'obj',
                        vars: [
                            { name: 'x1', coef: 1 },
                            { name: 'x2', coef: 1 }
                        ]
                    },
                    subjectTo: [
                        {
                        name: 'cons1',
                            vars: [
                                { name: 'x1', coef: 1.0 },
                                { name: 'x2', coef: 0.0 }
                            ],
                            bnds: { type: glpk.GLP_DB, ub: 1.0, lb: -1.0 }
                        },
                        {
                            name: 'cons2',
                            vars: [
                                { name: 'x1', coef: 0.0 },
                                { name: 'x2', coef: 1.0 }
                            ],
                            bnds: { type: glpk.GLP_DB, ub: 1.0, lb: -1.0 }
                        }
                    ]
                };

Of course, minimum of x1+x2 in such a square is at point (-1,-1). But your script prints:

{
  "name": "LP",
  "time": 0.001,
  "result": {
    "vars": {
      "x1": 0,
      "x2": 0
    },
    "dual": {
      "cons1": 0,
      "cons2": 0
    },
    "z": 0,
    "status": 5
  }
}

\* Problem: LP *\

Minimize
 obj: + x1 + x2

Subject To
 cons1: + x1 - ~r_1 = -1
 cons2: + x2 - ~r_2 = -1

Bounds
 0 <= ~r_1 <= 2
 0 <= ~r_2 <= 2

End

What does it mean? Copy of the the corrected lp.html script is attached in the zip
Moreover, I don't understand ~r_1 and ~r_2 in your problem description. I tried to specify both boundaries: -1 <= x1/x2 <= 1.

lp.zip