Defining incompatible variables on model

tetri commented 5 years ago

Hey there! jsLPSolver was the unbelievable best library to solve linear programming problems that I found! Congratulations!

I'm having trouble adjusting the template to contain incompatibility restrictions. I've got the following model:

{
    "optimize": "cost",
    "opType": "min",
    "constraints": {
        "c1": { "min": 36000.0, "max": 36800.0 },
        "c2": { "min": 12000.0, "max": 12800.0 },
        "c3": { "equal": 1000.0 }
    },
    "variables": {
        "p1": { "c1": 0, "c2": 0, "c3": 1, "cost": 437.47, },
        "p2": { "c1": 0, "c2": 60.0, "c3": 1, "cost": 1964.49, },
        "p3": { "c1": 34.0, "c2": 0, "c3": 1, "cost": 1428.98, },
        "p4": { "c1": 46.0, "c2": 0, "c3": 1, "cost": 1973.11, }
    },
    "ints": { "p1": 1, "p2": 1, "p3": 1, "p4": 1 }
}

and the feasible result

{ bounded: true, feasible: true, p2: 200, p3: 66, p4: 734, result: 1935473.42 }

as seen on https://runkit.com/tetrimesquita/incompatible-contraint

However, it exists a constraint that p3 and p4 could not be together in the solution, because they are incompatible.

How can I adjust the model to meet this constraint?

tetri commented 5 years ago

I'm thinking about use a constraint like p3 + p4 = 0:

{
    "optimize": "cost",
    "opType": "min",
    "constraints": {
        "c1": { "min": 36000.0, "max": 36800.0 },
        "c2": { "min": 12000.0, "max": 12800.0 },
        "c3": { "equal": 1000.0 },
        "incompatible": { "equal": 0.0 }
    },
    "variables": {
        "p1": { "c1": 0, "c2": 0, "c3": 1, "cost": 437.47, "incompatible": 0.0 },
        "p2": { "c1": 0, "c2": 60.0, "c3": 1, "cost": 1964.49, "incompatible": 0.0 },
        "p3": { "c1": 34.0, "c2": 0, "c3": 1, "cost": 1428.98, "incompatible": 1.0 },
        "p4": { "c1": 46.0, "c2": 0, "c3": 1, "cost": 1973.11, "incompatible": 1.0 }
    },
    "ints": { "p1": 1, "p2": 1, "p3": 1, "p4": 1 }
}

but see what happens to the solution in this case:

{ bounded: true, feasible: false, p2: 200, p3: -3000, p4: 3000, result: 0 }

which is correct but unfeasible.

JWally commented 5 years ago

To be honest, I’m not a mathematician so I could be totally wrong; but I don’t think there’s a way to make variables exclusive to one another (unless you set exact values in the constraints which itself leads to a combinatorial nightmare).

As a hack; you could solve the model twice; once with an equity constraint to equal zero for p3, and another model with an equity constraint of zero on p4.

@bchevalier any thoughts?

JWally / jsLPSolver

Defining incompatible variables on model #85