[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Error : multiplication of linear forms not allowed
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Error : multiplication of linear forms not allowed |
Date: |
Thu, 1 Apr 2010 22:37:49 +0400 |
> I'm trying to solve a subset selection problem using GLPK.
> I have n connected processes to be deployed in two machines. Each
> process has different performance cost for each machine. Initially all
> the processes are deployed in machine 1, I need to move subset of
> these processes to machine 2 to minimize the total performance cost.
> If two connected processes are deployed in different machines there is
> transfer cost, this also should be taken into account when calculating
> the total cost.
> Assume processes are connected in the order of P1, P2, ......., Pn . I
> represented each process as a binary variable Pi, if the process i to
> be moved machine 2, Pi = 1, else 0.
> So my objective function is minimize: sum {i in Processes} (M1i - (M1i
> -M2i-Ti)* Pi) where M1i - cost of running ith process in machine 1 M2i
> - cost of running ith process in machine 2 Ti - transfer cost between
> ith process & (i+1)th process if they are in different machines
> If both Pi & Pi+1 are moved to machine 2 transfer cost between them
> should be set to zero. My problem is how to specify this constraint in
> GLPK ??
> I tried to do it as
> minimize: sum {i in Processes} (M1i - (M1i -M2i-(Pi+1)*Ti)*Pi) but it
> gives me an error saying "multiplication of linear forms not allowed"
> Is there any other way to do this or is this problem cannot be solved
> using GLPK?
You need to introduce auxiliary binary variables, say, z[i], where
z[i] = P[i] * P[i+1]. Assuming that all P[i] are binary, this equality
can be replaced by the following equivalent constraint:
0 <= P[i] + P[i+1] - 2 * z[i] <= 1
that allows you avoiding multiplication.