Integer programming: Is it possible to define an incompatibility constraint?

Question

I'm using jsLPSolver to solve an integer-programming problem.

I'm having trouble adjusting the model to contain incompatibility constraints. 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 }

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

Is it possible to define an incompatibility constraint to define that p3 and p4 is incompatible variables?

EDIT

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 }

as seen on https://runkit.com/tetrimesquita/incompatible-contraint, which is correct but unfeasible.

What does incompatible mean? Only one of the variables can be nonzero? — Dion, May 13 '19 at 11:32
Alternatively, you could solve your system twice - once without `p3`, and once without `p4`, then take the solution with the lower cost. — Dion, May 13 '19 at 11:46
I'll try `p3 * p4 = 0`, teorically it should work... if works, I'll ask you to answer and you can win 200 reputation bounty ;) — tetri, May 13 '19 at 11:52
I had a closer look at `jsLPSolver`, and realized it is a *linear* solver. So you probably can't specify `p3 * p4 = 0`, since that would be a non-linear constraint. But you can always try my second idea. — Dion, May 13 '19 at 12:19

LarrySnyder610 · Answer 1 · 2019-05-17T03:12:49.527

I see now that p3 and p4 are continuous. (If they are actually binary, see this answer.) In that case, add two new binary variables, say z3 and z4, that equal 1 if p3 and p4 (respectively) are greater than zero:

p3 <= Mz3
p4 <= Mz4

where M is a large number. Then add a constraint

z3 + z4 <= 1

The first two constraints say that if p3 > 0, then z3 must equal 1 (and similarly for p4 and z4). The third constraint says at most one of z3 and z4 can equal 1, i.e., at most one of p3 and p4 can be positive.

If p3 and p4 are unrestricted (allowed to be positive or negative) and you want to require at most one of them to be nonzero, then also add:

-p3 <= Mz3
-p4 <= Mz4

score 0 · Answer 2 · answered May 13 '19 at 12:24

Probably not the most elegant version out there, but this should do it:

var solver = require("javascript-lp-solver");

var 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, },
    },
    "ints": { "p1": 1, "p2": 1, "p3": 1}
}

var results_p3 = solver.Solve(model);

var 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, },
        "p4": { "c1": 46.0, "c2": 0, "c3": 1, "cost": 1973.11, }
    },
    "ints": { "p1": 1, "p2": 1, "p4": 1 }
}

var results_p4 = solver.Solve(model);

var finalResults = (results_p3.feasible && (results_p3.result < results_p4.result)) ? results_p3 : results_p4;

console.log(results_p3);
console.log(results_p4);
console.log(finalResults);

The idea is that you run the model twice - once where p3 is fixed, and once where p4 is fixed. Then you take the solution that obeys the constraints and yields the better result [1].

See output here:

https://runkit.com/dionhaefner/so-incompatible-constraint

[1] You should probably polish that last check a little. E.g., what should happen if both results are infeasible? What if both have a result of 0? You might have to check the bounded property, too.

score 0 · Answer 3 · answered May 13 '19 at 13:18

0

If p3 and p4 are binary, you can just use

p3 + p4 <= 1

Or if you want exactly one of them to equal 1, then use

p3 + p4 = 1

I'm not familiar with the syntax for jsLPSolver, but the constraints above provide the logic.

answered May 13 '19 at 13:18

LarrySnyder610

2,277
12
24

Integer programming: Is it possible to define an incompatibility constraint?

3 Answers3