CODEWITHSUNDEEP
integer-programmingoperations-research
tetri
tetri

Reputation: 3584

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

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.

Upvotes: 4

Views: 297

Answers (3)

LarrySnyder610
LarrySnyder610

Reputation: 2397

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

Upvotes: 1

LarrySnyder610
LarrySnyder610

Reputation: 2397

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.

Upvotes: 0

Dion
Dion

Reputation: 1552

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.

Upvotes: 0

Related Questions