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.
- 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.
- 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 install --save-prod tslopt
const fs = ;const tsLOpt = ;const buildFromJson = tsLOpt;const object = JSON;const tableau = ;tableau; // default parameters work well with small numbers, if you have bigger number consider bumping the second parameter this way tableau.log(true, 10)tableau;console;console;
const tsLOpt = ;const buildFromSize = tsLOpt;const tableau = ;const v1 = tableau;tableau;const v2 = tableau;tableau;const v3 = tableau;tableau;tableau;tableau;tableau; // default parameters work well with small numbers, if you have bigger number consider bumping the second parameter this way tableau.log(true, 10)tableau;console;console;
For a more in-depth look you can check
- 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 <= 10and
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
INTEGER (the mixed integer linear programs are not supported yet) and
UNRESTRICTED. The testing suite recognizes the keywords
The first row is used for the column names and may or may not contain entries for
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
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
- if you want to use your own instances, put the csv inside
/test/scripts. There are already test instances to choose from.
npm run generate-instancesto create the json.
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.
npm run build will generate a packaged es5 version of the solver inside
npm run test-instancesto test the solver's source against the instances with an
npm run test-buildto test the built solver against the instances with an