search

JWally / jsLPSolver

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

Integer constraints don't work for Stock Cutting Problem #84

Closed ccorcos closed 5 years ago

ccorcos commented 5 years ago

Hey there, I submitted an issue where I talked about the Stock Cutting Problem: https://github.com/JWally/jsLPSolver/issues/83

I've come up with a solution that works for one example, cutting 96" boards into:

model = { optimize: 'count',
  opType: 'min',
  variables:
   { version0: { cut7: 13, cut76: 0, cut80: 0, count: 1 },
     version1: { cut7: 2, cut76: 1, cut80: 0, count: 1 },
     version2: { cut7: 2, cut76: 0, cut80: 1, count: 1 } },
  int: { version0: 1, version1: 1, version2: 1 },
  constraints: { cut7: { min: 21 }, cut76: { min: 17 }, cut80: { min: 7 } } }

result = { feasible: true,
  result: 24,
  bounded: true,
  version1: 17,
  version2: 7 }

The versions are the different ways that you can cut 96" board into those pieces. I've constrained the number of each version to be an integer and we have an expected result.

However, when I generalizing that example to a slightly more complicated one, the integer requirements don't work.

The more complicated example involves, cutting 96 inch boards into:

model = { optimize: 'count',
  opType: 'min',
  variables:
   { version0:
      { cut11: 8,
        cut21: 0,
        cut84: 0,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version1:
      { cut11: 6,
        cut21: 1,
        cut84: 0,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version2:
      { cut11: 0,
        cut21: 4,
        cut84: 0,
        'cut3.5': 1,
        'cut79.5': 0,
        count: 1 },
     version3:
      { cut11: 1,
        cut21: 0,
        cut84: 1,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version4:
      { cut11: 0,
        cut21: 0,
        cut84: 1,
        'cut3.5': 1,
        'cut79.5': 0,
        count: 1 },
     version5:
      { cut11: 8,
        cut21: 0,
        cut84: 0,
        'cut3.5': 1,
        'cut79.5': 0,
        count: 1 },
     version6:
      { cut11: 0,
        cut21: 0,
        cut84: 1,
        'cut3.5': 1,
        'cut79.5': 0,
        count: 1 },
     version7:
      { cut11: 0,
        cut21: 1,
        cut84: 0,
        'cut3.5': 19,
        'cut79.5': 0,
        count: 1 },
     version8:
      { cut11: 0,
        cut21: 0,
        cut84: 0,
        'cut3.5': 4,
        'cut79.5': 1,
        count: 1 },
     version9:
      { cut11: 1,
        cut21: 0,
        cut84: 0,
        'cut3.5': 0,
        'cut79.5': 1,
        count: 1 } },
  int:
   { version0: 1,
     version1: 1,
     version2: 1,
     version3: 1,
     version4: 1,
     version5: 1,
     version6: 1,
     version7: 1,
     version8: 1,
     version9: 1 },
  constraints:
   { cut11: { min: 28 },
     cut21: { min: 14 },
     cut84: { min: 8 },
     'cut3.5': { min: 42 },
     'cut79.5': { min: 4 } } }

result = { feasible: true,
  result: 18.8,
  bounded: true,
  version5: 2.5,
  version2: 3.23333333,
  version3: 8,
  version7: 1.06666667,
  version8: 4 }

Notice how the results have decimals when I've clearly specified them in the integer constraints.

Any ideas what I can do about this?

ccorcos commented 5 years ago

I wasn't permuting through all the possible cuts properly in that last one. Here's a more correct example. Still has a problem with not having an integer result value...

model = [ { count: 17, cuts: [ 7, 7, 76 ] },
  { count: 7, cuts: [ 7, 7, 80 ] } ]
{ optimize: 'count',
  opType: 'min',
  variables:
   { version0:
      { cut11: 8,
        cut21: 0,
        cut84: 0,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version1:
      { cut11: 7,
        cut21: 0,
        cut84: 0,
        'cut3.5': 3,
        'cut79.5': 0,
        count: 1 },
     version2:
      { cut11: 6,
        cut21: 1,
        cut84: 0,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version3:
      { cut11: 6,
        cut21: 0,
        cut84: 0,
        'cut3.5': 6,
        'cut79.5': 0,
        count: 1 },
     version4:
      { cut11: 5,
        cut21: 1,
        cut84: 0,
        'cut3.5': 3,
        'cut79.5': 0,
        count: 1 },
     version5:
      { cut11: 5,
        cut21: 0,
        cut84: 0,
        'cut3.5': 9,
        'cut79.5': 0,
        count: 1 },
     version6:
      { cut11: 4,
        cut21: 2,
        cut84: 0,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version7:
      { cut11: 4,
        cut21: 1,
        cut84: 0,
        'cut3.5': 6,
        'cut79.5': 0,
        count: 1 },
     version8:
      { cut11: 4,
        cut21: 0,
        cut84: 0,
        'cut3.5': 12,
        'cut79.5': 0,
        count: 1 },
     version9:
      { cut11: 3,
        cut21: 3,
        cut84: 0,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version10:
      { cut11: 3,
        cut21: 2,
        cut84: 0,
        'cut3.5': 3,
        'cut79.5': 0,
        count: 1 },
     version11:
      { cut11: 3,
        cut21: 1,
        cut84: 0,
        'cut3.5': 9,
        'cut79.5': 0,
        count: 1 },
     version12:
      { cut11: 3,
        cut21: 0,
        cut84: 0,
        'cut3.5': 15,
        'cut79.5': 0,
        count: 1 },
     version13:
      { cut11: 2,
        cut21: 3,
        cut84: 0,
        'cut3.5': 1,
        'cut79.5': 0,
        count: 1 },
     version14:
      { cut11: 2,
        cut21: 2,
        cut84: 0,
        'cut3.5': 7,
        'cut79.5': 0,
        count: 1 },
     version15:
      { cut11: 2,
        cut21: 1,
        cut84: 0,
        'cut3.5': 13,
        'cut79.5': 0,
        count: 1 },
     version16:
      { cut11: 2,
        cut21: 0,
        cut84: 0,
        'cut3.5': 19,
        'cut79.5': 0,
        count: 1 },
     version17:
      { cut11: 1,
        cut21: 4,
        cut84: 0,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version18:
      { cut11: 1,
        cut21: 3,
        cut84: 0,
        'cut3.5': 4,
        'cut79.5': 0,
        count: 1 },
     version19:
      { cut11: 1,
        cut21: 2,
        cut84: 0,
        'cut3.5': 10,
        'cut79.5': 0,
        count: 1 },
     version20:
      { cut11: 1,
        cut21: 1,
        cut84: 0,
        'cut3.5': 16,
        'cut79.5': 0,
        count: 1 },
     version21:
      { cut11: 1,
        cut21: 0,
        cut84: 1,
        'cut3.5': 0,
        'cut79.5': 0,
        count: 1 },
     version22:
      { cut11: 1,
        cut21: 0,
        cut84: 0,
        'cut3.5': 22,
        'cut79.5': 0,
        count: 1 },
     version23:
      { cut11: 1,
        cut21: 0,
        cut84: 0,
        'cut3.5': 1,
        'cut79.5': 1,
        count: 1 },
     version24:
      { cut11: 0,
        cut21: 4,
        cut84: 0,
        'cut3.5': 1,
        'cut79.5': 0,
        count: 1 },
     version25:
      { cut11: 0,
        cut21: 3,
        cut84: 0,
        'cut3.5': 7,
        'cut79.5': 0,
        count: 1 },
     version26:
      { cut11: 0,
        cut21: 2,
        cut84: 0,
        'cut3.5': 13,
        'cut79.5': 0,
        count: 1 },
     version27:
      { cut11: 0,
        cut21: 1,
        cut84: 0,
        'cut3.5': 19,
        'cut79.5': 0,
        count: 1 },
     version28:
      { cut11: 0,
        cut21: 0,
        cut84: 1,
        'cut3.5': 1,
        'cut79.5': 0,
        count: 1 },
     version29:
      { cut11: 0,
        cut21: 0,
        cut84: 0,
        'cut3.5': 25,
        'cut79.5': 0,
        count: 1 },
     version30:
      { cut11: 0,
        cut21: 0,
        cut84: 0,
        'cut3.5': 4,
        'cut79.5': 1,
        count: 1 } },
  int:
   { version0: 1,
     version1: 1,
     version2: 1,
     version3: 1,
     version4: 1,
     version5: 1,
     version6: 1,
     version7: 1,
     version8: 1,
     version9: 1,
     version10: 1,
     version11: 1,
     version12: 1,
     version13: 1,
     version14: 1,
     version15: 1,
     version16: 1,
     version17: 1,
     version18: 1,
     version19: 1,
     version20: 1,
     version21: 1,
     version22: 1,
     version23: 1,
     version24: 1,
     version25: 1,
     version26: 1,
     version27: 1,
     version28: 1,
     version29: 1,
     version30: 1 },
  constraints:
   { cut11: { min: 28 },
     cut21: { min: 14 },
     cut84: { min: 8 },
     'cut3.5': { min: 42 },
     'cut79.5': { min: 4 } } }

result = { feasible: true,
  result: 18.42666667,
  bounded: true,
  version16: 1,
  version9: 4.66666667,
  version21: 8,
  version29: 0.76,
  version23: 4 }

I took the floor of those values to see what sort of remainder was left over...

[ { size: 11, count: 2 },
  { size: 21, count: 2 },
  { size: 3.5, count: 19 } ]

Then I ran my model again on just that remainder...

model = { optimize: 'count',
  opType: 'min',
  variables:
   { version0: { cut11: 8, cut21: 0, 'cut3.5': 0, count: 1 },
     version1: { cut11: 7, cut21: 0, 'cut3.5': 3, count: 1 },
     version2: { cut11: 6, cut21: 1, 'cut3.5': 0, count: 1 },
     version3: { cut11: 6, cut21: 0, 'cut3.5': 6, count: 1 },
     version4: { cut11: 5, cut21: 1, 'cut3.5': 3, count: 1 },
     version5: { cut11: 5, cut21: 0, 'cut3.5': 9, count: 1 },
     version6: { cut11: 4, cut21: 2, 'cut3.5': 0, count: 1 },
     version7: { cut11: 4, cut21: 1, 'cut3.5': 6, count: 1 },
     version8: { cut11: 4, cut21: 0, 'cut3.5': 12, count: 1 },
     version9: { cut11: 3, cut21: 3, 'cut3.5': 0, count: 1 },
     version10: { cut11: 3, cut21: 2, 'cut3.5': 3, count: 1 },
     version11: { cut11: 3, cut21: 1, 'cut3.5': 9, count: 1 },
     version12: { cut11: 3, cut21: 0, 'cut3.5': 15, count: 1 },
     version13: { cut11: 2, cut21: 3, 'cut3.5': 1, count: 1 },
     version14: { cut11: 2, cut21: 2, 'cut3.5': 7, count: 1 },
     version15: { cut11: 2, cut21: 1, 'cut3.5': 13, count: 1 },
     version16: { cut11: 2, cut21: 0, 'cut3.5': 19, count: 1 },
     version17: { cut11: 1, cut21: 4, 'cut3.5': 0, count: 1 },
     version18: { cut11: 1, cut21: 3, 'cut3.5': 4, count: 1 },
     version19: { cut11: 1, cut21: 2, 'cut3.5': 10, count: 1 },
     version20: { cut11: 1, cut21: 1, 'cut3.5': 16, count: 1 },
     version21: { cut11: 1, cut21: 0, 'cut3.5': 22, count: 1 },
     version22: { cut11: 0, cut21: 4, 'cut3.5': 1, count: 1 },
     version23: { cut11: 0, cut21: 3, 'cut3.5': 7, count: 1 },
     version24: { cut11: 0, cut21: 2, 'cut3.5': 13, count: 1 },
     version25: { cut11: 0, cut21: 1, 'cut3.5': 19, count: 1 },
     version26: { cut11: 0, cut21: 0, 'cut3.5': 25, count: 1 } },
  int:
   { version0: 1,
     version1: 1,
     version2: 1,
     version3: 1,
     version4: 1,
     version5: 1,
     version6: 1,
     version7: 1,
     version8: 1,
     version9: 1,
     version10: 1,
     version11: 1,
     version12: 1,
     version13: 1,
     version14: 1,
     version15: 1,
     version16: 1,
     version17: 1,
     version18: 1,
     version19: 1,
     version20: 1,
     version21: 1,
     version22: 1,
     version23: 1,
     version24: 1,
     version25: 1,
     version26: 1 },
  constraints:
   { cut11: { min: 2 }, cut21: { min: 2 }, 'cut3.5': { min: 19 } } }

result = { feasible: true,
  result: 1.42666667,
  bounded: true,
  version16: 0,
  version9: 0.66666667,
  version26: 0.76 }

And I still got decimals...

At the end of the day, 21 * 2 + 11 * 2 = 64 and 19 * 3.5 = 66.5 so I will need to extra boards... but its still a little off that there are decimals there.

tetri commented 5 years ago

@ccorcos, I'm using javascript-lp-solver too and I noticed that there is an error in specifying integer variables in your model. Use "ints" instead of "int" and the result will be as follows:

https://runkit.com/tetrimesquita/5cd439faf17e79001aa31016

JWally commented 5 years ago

I think I have this one under control now. Pull the current version, and try running your model through like this:

{
    "name": "Fancy Stock Cutting Problem",
    "optimize": "count",
    "opType": "min",
    "_timeout": 5000,
    "options": {
        "tolerance": 0.03,
        "timeout": 1500
    },
    "variables": {
        "version0": {
            "cut11": 8,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 0,
            "cut79.5": 0,
            "count": 1
        },
        "version1": {
            "cut11": 7,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 3,
            "cut79.5": 0,
            "count": 1
        },
        "version2": {
            "cut11": 6,
            "cut21": 1,
            "cut84": 0,
            "cut3.5": 0,
            "cut79.5": 0,
            "count": 1
        },
        "version3": {
            "cut11": 6,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 6,
            "cut79.5": 0,
            "count": 1
        },
        "version4": {
            "cut11": 5,
            "cut21": 1,
            "cut84": 0,
            "cut3.5": 3,
            "cut79.5": 0,
            "count": 1
        },
        "version5": {
            "cut11": 5,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 9,
            "cut79.5": 0,
            "count": 1
        },
        "version6": {
            "cut11": 4,
            "cut21": 2,
            "cut84": 0,
            "cut3.5": 0,
            "cut79.5": 0,
            "count": 1
        },
        "version7": {
            "cut11": 4,
            "cut21": 1,
            "cut84": 0,
            "cut3.5": 6,
            "cut79.5": 0,
            "count": 1
        },
        "version8": {
            "cut11": 4,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 12,
            "cut79.5": 0,
            "count": 1
        },
        "version9": {
            "cut11": 3,
            "cut21": 3,
            "cut84": 0,
            "cut3.5": 0,
            "cut79.5": 0,
            "count": 1
        },
        "version10": {
            "cut11": 3,
            "cut21": 2,
            "cut84": 0,
            "cut3.5": 3,
            "cut79.5": 0,
            "count": 1
        },
        "version11": {
            "cut11": 3,
            "cut21": 1,
            "cut84": 0,
            "cut3.5": 9,
            "cut79.5": 0,
            "count": 1
        },
        "version12": {
            "cut11": 3,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 15,
            "cut79.5": 0,
            "count": 1
        },
        "version13": {
            "cut11": 2,
            "cut21": 3,
            "cut84": 0,
            "cut3.5": 1,
            "cut79.5": 0,
            "count": 1
        },
        "version14": {
            "cut11": 2,
            "cut21": 2,
            "cut84": 0,
            "cut3.5": 7,
            "cut79.5": 0,
            "count": 1
        },
        "version15": {
            "cut11": 2,
            "cut21": 1,
            "cut84": 0,
            "cut3.5": 13,
            "cut79.5": 0,
            "count": 1
        },
        "version16": {
            "cut11": 2,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 19,
            "cut79.5": 0,
            "count": 1
        },
        "version17": {
            "cut11": 1,
            "cut21": 4,
            "cut84": 0,
            "cut3.5": 0,
            "cut79.5": 0,
            "count": 1
        },
        "version18": {
            "cut11": 1,
            "cut21": 3,
            "cut84": 0,
            "cut3.5": 4,
            "cut79.5": 0,
            "count": 1
        },
        "version19": {
            "cut11": 1,
            "cut21": 2,
            "cut84": 0,
            "cut3.5": 10,
            "cut79.5": 0,
            "count": 1
        },
        "version20": {
            "cut11": 1,
            "cut21": 1,
            "cut84": 0,
            "cut3.5": 16,
            "cut79.5": 0,
            "count": 1
        },
        "version21": {
            "cut11": 1,
            "cut21": 0,
            "cut84": 1,
            "cut3.5": 0,
            "cut79.5": 0,
            "count": 1
        },
        "version22": {
            "cut11": 1,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 22,
            "cut79.5": 0,
            "count": 1
        },
        "version23": {
            "cut11": 1,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 1,
            "cut79.5": 1,
            "count": 1
        },
        "version24": {
            "cut11": 0,
            "cut21": 4,
            "cut84": 0,
            "cut3.5": 1,
            "cut79.5": 0,
            "count": 1
        },
        "version25": {
            "cut11": 0,
            "cut21": 3,
            "cut84": 0,
            "cut3.5": 7,
            "cut79.5": 0,
            "count": 1
        },
        "version26": {
            "cut11": 0,
            "cut21": 2,
            "cut84": 0,
            "cut3.5": 13,
            "cut79.5": 0,
            "count": 1
        },
        "version27": {
            "cut11": 0,
            "cut21": 1,
            "cut84": 0,
            "cut3.5": 19,
            "cut79.5": 0,
            "count": 1
        },
        "version28": {
            "cut11": 0,
            "cut21": 0,
            "cut84": 1,
            "cut3.5": 1,
            "cut79.5": 0,
            "count": 1
        },
        "version29": {
            "cut11": 0,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 25,
            "cut79.5": 0,
            "count": 1
        },
        "version30": {
            "cut11": 0,
            "cut21": 0,
            "cut84": 0,
            "cut3.5": 4,
            "cut79.5": 1,
            "count": 1
        }
    },
    "ints": {
        "version0": 1,
        "version1": 1,
        "version2": 1,
        "version3": 1,
        "version4": 1,
        "version5": 1,
        "version6": 1,
        "version7": 1,
        "version8": 1,
        "version9": 1,
        "version10": 1,
        "version11": 1,
        "version12": 1,
        "version13": 1,
        "version14": 1,
        "version15": 1,
        "version16": 1,
        "version17": 1,
        "version18": 1,
        "version19": 1,
        "version20": 1,
        "version21": 1,
        "version22": 1,
        "version23": 1,
        "version24": 1,
        "version25": 1,
        "version26": 1,
        "version27": 1,
        "version28": 1,
        "version29": 1,
        "version30": 1
    },
    "constraints": {
        "cut11": {
            "min": 28
        },
        "cut21": {
            "min": 14
        },
        "cut84": {
            "min": 8
        },
        "cut3.5": {
            "min": 42
        },
        "cut79.5": {
            "min": 4
        }
    },
    "expects": {
        "feasible": true,
        "result": 19,
        "version30": 1,
        "version9": 4,
        "version21": 2,
        "version28": 6,
        "version24": 0,
        "version15": 2,
        "version23": 3,
        "version1": 1
    }
}

I get the following:

{ "feasible": true,
  "result": 19,
  "bounded": true,
  "isIntegral": true,
  "version30": 1,
  "version9": 4,
  "version21": 2,
  "version28": 6,
  "version24": 0,
  "version15": 2,
  "version23": 3,
  "version1": 1,
  "messages": [] }
JWally commented 5 years ago

I'm gonna close just so I can do some clean up. Please feel free to re-open if this didn't work. Thanks!