tsLOpt

The TypeScript Linear Optimizer is made with simplicity in mind so that you can dive in, see what is happening or even modify it yourself. Everything has been named and typed carefully so that it is easy to follow. The recommended use case is real time web/browser based applications with small to mid size instances. Commercial solvers are of course necessary for industrial class problems but for the simpler ones, I feel that the optimized data structures and leaner APIs obfuscate the user experience for limited benefits.

FEATURES:

• standard simplex method or it is possible to use your own solving strategy.
• constraint priorities through relaxation.
• either import from CSV then load from JSON, or create the model at runtime through the API, or a combination of both. There are a default CSV parser and a default JSON loader but you can replace them with your own if you want to support other formats.
• the source is in TypeScript for development and is compiled in JavaScript es5 for browser compatibility.

COMING SOON:

• adding more tests in order to improve reliability. For example the Cycling 1 instance makes the solver cycle so an improved pivoting strategy must be implemented.
• revised simplex method with LU decomposition.
• mixed integer linear programs with branch and cut.
• interrupt after a timeout.
• solve again a LP, starting from the previous base. In the case of real time based applications, for example solving every second or even every frame, if the incremental modifications of the LP are small enough, the new base might be the same as the previous one or only a few pivots away.

NPM INSTALLATION:

npm install --save-prod tslopt

const fs = require('fs');
const tsLOpt = require('tslopt');
const { buildFromJson } = tsLOpt;
 
const object = JSON.parse(fs.readFileSync("filePath"));
const tableau = buildFromJson(object);
tableau.log(true);	// default parameters work well with small numbers, if you have bigger number consider bumping the second parameter this way tableau.log(true, 10)
tableau.solve(() => {
    tableau.log(true);
});
 
console.log(JSON.stringify(tableau.basicVariables));
console.log(JSON.stringify(tableau.strategy.solutionStatus));

const tsLOpt = require('tslopt');
const { buildFromSize } = tsLOpt;
 
const tableau = buildFromSize(2, 3);
 
const v1 = tableau.addNonBasicVariable('v1', false, false);
tableau.setCost(v1, -6);
const v2 = tableau.addNonBasicVariable('v2', false, false);
tableau.setCost(v2, -14);
const v3 = tableau.addNonBasicVariable('v3', false, false);
tableau.setCost(v3, -13);
 
tableau.addConstraint([0.5, 2, 1], 24);
tableau.addConstraint([1, 2, 4], 60);
 
tableau.log(true);	// default parameters work well with small numbers, if you have bigger number consider bumping the second parameter this way tableau.log(true, 10)
tableau.solve(() => {
    tableau.log(true);
});
 
console.log(JSON.stringify(tableau.basicVariables));
console.log(JSON.stringify(tableau.strategy.solutionStatus));

For a more in-depth look you can check test/suite/build.js.

MODEL PREPARATION:

• transform the model into a minimization. For example if you have a maximization objective such as x1 - x2, you have to turn it into the minimization -x1 + x2.
• transform the model so that its canonical form is made of only "lesser than or equal" inequalities. For example if you have an equality x1 + x2 = 10, you have to split it into 2 inequalities x1 + x2 <= 10 and x1 + x2 >= 10, and finally transform the second inequality into -x1 - x2 <= -10. This is the brute force way of doing it but doing it the proper way will add more possible breaking points without obvious benefits for the class of problems targeted.

DEFAULT INSTANCE FORMAT:

ID,v1,v2,v3,RHS,PRIORITY,RELAXATION,COMMENTS
OBJECTIVE,-6,-14,-13,0,,,
c1,0.5,2,1,24,0,0,
c2,1,2,4,60,0,0,
INTEGER,FALSE,FALSE,FALSE,,,,
UNRESTRICTED,FALSE,FALSE,FALSE,,,,
EXPECTED,36,0,6,OPTIMAL,,,This row is used for testing purposes

The default loader recognizes the keywords ID, RHS, PRIORITY, RELAXATION, COMMENTS, OBJECTIVE, INTEGER (the mixed integer linear programs are not supported yet) and UNRESTRICTED. The testing suite recognizes the keywords EXPECTED, UNFEASIBLE, OPTIMAL and UNBOUNDED.

The first row is used for the column names and may or may not contain entries for PRIORITY and RELAXATION. In the case PRIORITY is omitted, all the constraints will have the highest priority of 0. In the case RELAXATION is omitted, all the constraints with a lower priority than required, aka greater than 0, will have a relaxation cost of 1. RELAXATION will be ignored if PRIORITY is omitted. The COMMENTS section is there only for metadata, its presence/omission has no impact on the solving.

All the other rows may be in any order. In the case INTEGER is omitted, the variables will be assumed continuous. In the case UNRESTRICTED is omitted, the variables will be assumed non negative. The EXPECTED row can be used for the testing suite in order to check if the result the solver returns is the one we expect, which might need to be updated if there are multiple optimal solutions. Concerning the EXPECTED entry, the RHS property must be set to either UNFEASIBLE, OPTIMAL or UNBOUNDED.

After removing the superfluous information, the instance looks like that:

ID,v1,v2,v3,RHS
OBJECTIVE,-6,-14,-13,0
c1,0.5,2,1,24
c2,1,2,4,60
EXPECTED,36,0,6,-294

TRYING tsLOpt:

1. if you want to use your own instances, put the csv inside /test/scripts. There are already test instances to choose from.
2. do npm run generate-instances to create the json.
3. do npm run solve-instance "<instance path>", for example npm run solve-instance "test/instances/instances - toy instance 1.json", to solve a JSON from the CLI.

BUILD:

npm run build will generate a packaged es5 version of the solver inside /build.

TESTS:

• npm run test-instances to test the solver's source against the instances with an EXPECTED entry.
• npm run test-build to test the built solver against the instances with an EXPECTED entry.

Keywords

linear program, solver, simplex, mixed integer, solver, operations research, optimization, TypeScript, JavaScript, es5.