[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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:

reply via email to

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