[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[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)
- [Help-glpk] Modeling Choice,
Evin Robertson <=