javascript-lp-solver - npm Package Compare versions

Comparing version 0.4.10 to 0.4.12

gruntfile.js

@@ -5,4 +5,5 @@ // --------------------------------
 //
-// 1.) TO TEST: grunt test
-// 2.) TO TEST SPEED: grunt speed
+// 1.) TO TEST: grunt test-sanity
+// 2.) TO TEST SPEED: grunt test-speed
+// 3.) TO TEST AD-HOC / WIP: grunt test-wip
 // 3.) TO BUILD EVERYTHING: grunt prod
@@ -32,4 +33,4 @@ //
                 "options": {
-                    "reporter": "spec",
-                    "quite": "true"
+                    "reporter": "json",
+                    "quite": "false"
                 },
@@ -36,0 +37,0 @@ "src": ["test/solver.problems.js"]

package.json

 {
   "name": "javascript-lp-solver",
   "description": "Easy to use, JSON oriented Linear Programming and Mixed Int. Programming Solver",
-  "version": "0.4.10",
+  "version": "0.4.12",
   "private": false,
@@ -6,0 +6,0 @@ "authors": [

README.md

@@ -6,3 +6,4 @@ jsLPSolver
 
-## What Can I do with it?
+What Can I do with it?
+-----------------------
 
@@ -106,2 +107,29 @@ You can solve problems that fit the following fact pattern like this one
 
+What if my Mixed-Integer Problem takes too long to Solve?
+----------------------
+
+For large scale integer problems the solving process can take increasingly long. However, oftentimes the solution to these problems does not have to be the absolute best possible solution, but rather a solution relatively close to the optimal one. 
+In these cases, a variable called ```tolerance``` can be specified in the model object. The value assigned to the ```tolerance``` variable states that the solver should stop the solution process when the proportional difference between the solution found and the best theoretical objective value is guaranteed to be smaller than the given termination tolerance.
+
+```javascript
+   model = {
+        "optimize": "profit",
+        "opType": "max",
+        "tolerance": 0.5,
+        ...
+        }
+```
+
+Additionally, a ```timeout``` variable can be added to the JSON model that will return the best solution after {{user-defined}} milliseconds.
+
+```javascript
+   model = {
+        "optimize": "profit",
+        "opType": "max",
+        "timeout": 9000,
+        ...
+        }
+```
+
+
 How Fast is it?
@@ -112,6 +140,9 @@ ----------------------
 ```javascript
-{ Relaxed: { variables: 2, time: 0.004899597 },
-  Unrestricted: { constraints: 1, variables: 2, time: 0.001273972 },
+{ 
+  'Monster Problem': { constraints: 576, variables: 552, time: 0.017 },
+  'monster_II': { constraints: 842, variables: 924, ints: 112, time: 0.323 },
+  'Relaxed': { variables: 2, time: 0.004899597 },
+  'Unrestricted': { constraints: 1, variables: 2, time: 0.001273972 },
   'Chevalier 1': { constraints: 5, variables: 2, time: 0.000112002 },
-  Artificial: { constraints: 2, variables: 2, time: 0.000101994 },
+  'Artificial': { constraints: 2, variables: 2, time: 0.000101994 },
   'Wiki 1': { variables: 3, time: 0.000358714 },
@@ -136,6 +167,6 @@ 'Degenerate Min': { constraints: 5, variables: 2, time: 0.000097377 },
   'Shift Work Problem': { constraints: 6, variables: 6, time: 0.000127012 },
-  'Monster Problem': { constraints: 576, variables: 552, time: 0.054285454 },
-  monster_II: { constraints: 842, variables: 924, ints: 112, time: 0.649073406 } }
+}
 ```
 
+
 Alternative Model Formats
@@ -142,0 +173,0 @@ -----------

src/main.js

@@ -7,2 +7,3 @@ /*global describe*/
 /*global process*/
+/*global setTimeout*/
 
@@ -99,2 +100,6 @@
             store.bounded = solution.bounded;
+            
+            if(solution._tableau.__isIntegral){
+                store.isIntegral = true;
+            }
 
@@ -101,0 +106,0 @@ // 3.) Load all of the variable values

src/Model.js

@@ -294,2 +294,8 @@ /*global describe*/
 
+    this.tolerance = jsonModel.tolerance || 0;
+    
+    if(jsonModel.timeout){
+        this.timeout = jsonModel.timeout;
+    }
+
     var integerVarIds = jsonModel.ints || {};
@@ -296,0 +302,0 @@ var binaryVarIds = jsonModel.binaries || {};

src/Tableau/branchAndCut.js

@@ -68,2 +68,20 @@ /*global describe*/
     var iterations = 0;
+    var tolerance = this.model.tolerance;
+    var toleranceFlag = true;
+    var terminalTime = 1e99;
+    
+    //
+    // Set Start Time on model...
+    // Let's build out a way to *gracefully* quit
+    // after {{time}} milliseconds
+    //
+    
+    // 1.) Check to see if there's a timeout on the model
+    //
+    if(this.model.timeout){
+        // 2.) Hooray! There is!
+        //     Calculate the final date
+        //
+        terminalTime = Date.now() + this.model.timeout;
+    }
 
@@ -84,6 +102,13 @@ // This is the default result
     branches.push(branch);
-
     // If all branches have been exhausted terminate the loop
-    while (branches.length > 0) {
-
+    while (branches.length > 0 && toleranceFlag === true && Date.now() < terminalTime) {
+        
+        var acceptableThreshold = this.bestPossibleEval * (1 - (tolerance/100));
+        // Abort while loop if termination tolerance is both specified and condition is met
+        if (tolerance > 0) {
+            if (bestEvaluation < acceptableThreshold) {
+                toleranceFlag = false;
+            }
+        }
+        
         // Get a model from the queue
@@ -132,2 +157,9 @@ branch = branches.pop();
         if (this.isIntegral() === true) {
+            
+            //
+            // Store the fact that we are integral
+            //
+            this.__isIntegral = true;
+            
+            
             if (iterations === 1) {
@@ -134,0 +166,0 @@ this.branchAndCutIterations = iterations;

src/Tableau/simplex.js

@@ -220,2 +220,3 @@ /*global describe*/
             this.setEvaluation();
+            this.simplexIters += 1;
             return iterations;
@@ -222,0 +223,0 @@ }

src/Tableau/Tableau.js

@@ -37,2 +37,3 @@ /*global describe*/
     this.evaluation = 0;
+    this.simplexIters = 0;
 
@@ -243,4 +244,9 @@ this.varIndexByRow = null;
     var evaluation = this.matrix[this.costRowIndex][this.rhsColumn];
-    this.evaluation =
+    var roundedEvaluation =
         Math.round(evaluation * roundingCoeff) / roundingCoeff;
+
+    this.evaluation = roundedEvaluation;
+    if (this.simplexIters === 0) {
+        this.bestPossibleEval = roundedEvaluation;
+    }
 };
@@ -247,0 +253,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

53566101

increased by0.07%

Number of package files

99

increased by1.02%

Lines of code

1784578

increased by0.07%

Number of lines in readme file

348

increased by9.78%

Number of medium supply chain risk alerts

0

decreased by-100%

No dependency changes