3

I'm currently trying to model a problem with GLPK. I am in a situation where I have two binary variables $a, b$ and I need a function

$$f: \{0,1\}^2 \rightarrow \{0,1\}$$ such that

$$f(0,0) := f(0,1) := f(1,0) := 0$$ and $$f(1,1) := 1$$

(So: $f = \land$)

Is it possible to get this with linear operations?

What I've tried

  • $f(a,b) := a \cdot b$, but this is not linear
  • $f(a,b) := \min(a,b) = \frac{a+b-|a-b|}{2}$, but I don't know how to get $|a-b|$ with GLPK (this might not be possible, as the absolute value function is not a linear function)
  • define a function just like I did above: I don't know if / how this is possible with GLPK
  • using a parameter

parameter solution: 

param logicalAnd{i in 0..1, j in 0..1} :=
   if i = 1 and j = 1 then 1
   else 0;

s.t. rest4{i in players, o in players}: 
    sum{j in matches} (
        logicalAnd[x[i, j, 0]][x[o, j, 0]] + 
        logicalAnd[x[i, j, 1]][x[o, j, 1]]
    ) <= 1;

Results in

Reading model section from partition.mod...
partition.mod:33: subscript expression has invalid type
Context: ...rs } : sum { j in matches } ( logicalAnd [ x [ i , j , 0 ] ]
MathProg model processing error
Community
  • 1
Martin Thoma
  • 9,821
  • This would seem to be a problem about programming. There's a website for coding questions. – Gerry Myerson Jul 27 '13 at 08:52
  • 2
    @Gerry The "programming" here is numerical optimization rather than e.g. programming C++ or python, so I think it's on-topic for math.se – user7530 Jul 27 '13 at 09:01

1 Answers1

2

There is no such linear (as in first-order, e.g. affine) function $f$, because

$$f(0,1) + f(1,0) \neq f(0,0) + f(1,1).$$

I don't think you'll be able to encode $f$ using clever extra variables or constraints either, because $f$ is essentially $\min(a,b)$, and linear programming cannot be used to minimize a minimum. You can try to work around this by using "big multiplier" tricks, e.g.

  • Add $Mc$ to your objective function, where $M$ is a very big number;
  • Add the following constraints: $$a+b = c + d; \quad 0 \leq c \leq 1; \quad 0\leq d \leq 1.$$

If $M$ is sufficiently large, the objective will be minimized by setting $c$ to zero except when it's impossible, e.g. when $a$ and $b$ are both one. Thus $c \approx f(a,b)$.

I call this a trick and do not really recommend it, because first of all there's no guarantee that $c = f(a,b)$ unless you can somehow bound your objective function and guarantee you've chosen an $M$ large enough, and second putting large coefficients into your objective can render the LP numerically unstable. The most robust solution is to move beyond LPs and instead use mixed integer programming, etc.

user7530
  • 49,280