JWally / jsLPSolver

Simple OOP javaScript library to solve linear programs, and mixed integer linear programs
The Unlicense
420 stars 69 forks source link

Cutting Stock and Unexpected Result #63

Closed danvanorden closed 5 years ago

danvanorden commented 7 years ago

The following model generates an unexpected result:

{
  "optimize": "cost",
  "opType": "min",
  "constraints": {
    "length": {
      "min": 25
    }
  },
  "variables": {
    "21": {
      "21": 1,
      "length": 21,
      "cost": 75
    },
    "26": {
      "26": 1,
      "length": 26,
      "cost": 90
    },
    "31": {
      "31": 1,
      "length": 31,
      "cost": 105
    },
    "36": {
      "36": 1,
      "length": 36,
      "cost": 120
    }
  },
  "ints": {
    "21": 1,
    "26": 1,
    "31": 1,
    "36": 1
  }
}

The result I get is:

{  
   "26":-0,
   "36":1,
   "feasible":true,
   "result":120,
   "bounded":true
}

What I'm trying to do is find the minimum number of panel lengths required to cover at least the minimum overall required length (the length of a building) while minimizing final cost of the panels. I believe this is a variation of of the cutting stock problem. In this case, the minimum required length is 25. I would expect the solver to return a result of "26": 1 rather than "36": 1. The cost in that case would be 90 rather than 120.

I'm assuming I constructed the model incorrectly somehow. Is it possible to achieve my intended result with a modification to the model?

JWally commented 7 years ago

@bchevalier @lvenerosy any idea what's happening here? I'm get the same results.

Thanks, -JWW

lvenerosy commented 7 years ago

Checking it today.

lvenerosy commented 7 years ago

This is a problem with the MIR cuts. Inside src/Model.js in the constructor Model, you can change this.useMIRCuts = true; to false. I am not sure of when I will be able to patch it though.

danvanorden commented 7 years ago

Thanks for your insight and engagement on the issue. I'm using @lvenerosy's suggested workaround for now.

JWally commented 5 years ago

Sorry for the long delay. I removed some code, and I think it should work now like you're expecting. Can you re-test and if satisfied; close this? Thanks!

JWally commented 5 years ago

I'm think I got this cleaned up and am going to close. Feel free to re-open if I missed something.