help-glpk
[Top][All Lists]

## Re: [Help-glpk] Problem representing c = min (a, b)

 From: Andrew Makhorin Subject: Re: [Help-glpk] Problem representing c = min (a, b) Date: Thu, 18 Nov 2010 17:38:30 +0300

```>    I am trying to represent a problem using linear programming and I
> got stuck in how to model the minimum function. My problem is being
> c,a,b variables of the problem (not params), I would like to declare c
> as c = min(a,b). I have tried the approach of introducing a new binary
> variable B, such as:
>
>    # c = min (a, b)
>    (a-b)B >= 0
>    (a-b)(1-B) <= 0
>    c = aB+b(1-B)
>
>    But the problem is that I receive a "multiplication of linear forms
> not allowed". Does anybody have any suggestion or solution on how to
> model this type of requirement? In order to clarify the context of the
> problem, imagine that a set of machines can be assigned different
> network cards (type A with speed 10, type B with speed 100). The
> assignation of type A and type B depends on the cost function, let's
> say A cost 100€ and B cost 200€. In this scenario I now want to add the
> cost of transfering data between 2 machines which is limited by the
> minimum speed.
>

If in optimal solution c is expected to take on value a or b, you can
replace the constraint c = min(a, b) with the following two linear
inequality constraints:

c <= a
c <= b

In more general case you can model min, which is a piecewise linear
function, using auxiliary binary variables; for details see:
http://winglpk.sourceforge.net/media/glpk-sos2_02.pdf

```