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

[Andrew Makhorin]

>    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