[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
   c - b >= 1
   c - a <= -1
   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
  c - b + 1000 * x >= 1
  c - a - 1000 * y <= -1
  c - a + 1000 * z >= 1
  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)

reply via email to

[Prev in Thread] Current Thread [Next in Thread]