help-glpk
[Top][All Lists]

## [Help-glpk] Modeling Choice

 From: Evin Robertson Subject: [Help-glpk] Modeling Choice Date: Mon, 16 Dec 2002 13:22:57 -0500 User-agent: Mozilla/5.0 (X11; U; Linux ppc; en-US; rv:1.2.1) Gecko/20021210 Debian/1.2.1-3

```
```
In my problem I have a number of constraints over integer variables where I require at least one of several inequalities to be true, often like:
```
c - b <= -1
or
c - b >= 1
or
c - a <= -1
or
c - a >= 1

(essentially c != b || c != a)

```
Previously I was managing all of these myself, feeding one at a time into the solver, backtracking over all the possibilities to find a feasible/optimal solution.
```
```
I noticed that I could model the above choice with some binary variables w, x, y, and z, like:
```
c - b - 1000 * w <= -1
and
c - b + 1000 * x >= 1
and
c - a - 1000 * y <= -1
and
c - a + 1000 * z >= 1
and
w + x + y + z = 3

```
When w, x, y, or z is 1, the inequality containing it is trivially satisfied. And the final equation requires that one of these variables be 0.
```
```
So I wouldn't have to rerun the solver from scratch everytime I tried another choice. My assumption was that this would be much faster, but instead it ran at about half the speed of my previous solution.
```
```
Is there some better way, using integer linear programming, to assert that one of a list of inequalities must hold?
```
(using glpk 3.2.3 called from C)

```