[Help-glpk] [Fwd: Newbie help request]

[Andrew Makhorin]

-------- Forwarded Message --------
From: Tóth Tamás <address@hidden>
To: address@hidden
Subject: Newbie help request
Date: Tue, 19 Nov 2013 18:07:17 +0100

Hi all,

I'm totally new in linear programming and I have to solve a 
task-to-employee assignment problem.
Almost everything is fine but I cannot make linear the travelling 
section of problem (I mean it should be summarized how much an employee 
should travel with summarizing the distance between tasks following each 
other).

In the objective expression you can see as I try to filter by calculated 
assignment for both tasks (searching for pairs that follows each other) 
but I got "multiplications of linear forms not allowed".

Please someone tell me if it can be linearized at all and if it's 
possible how.

Thanks in advance.

Best regards,
     Tóth Tamás

PS.: Sorry for my poor english.

My program is:

set TASKS := { "44911405.1396", "45917349.728", "45935255.760", 
"45940559.937", "45940616.810", "45850077.1834", "45867819.665", 
"45875315.776", "45890352.675", "45893970.1566", "45867241.631", 
"45903630.1515", "45934020.614", "45889432.867", "45891512.1801", 
"45918734.827", "45921337.721", "45939669.674" };
set EMPLOYEES := { "105170", "105171", "105172", "105173", "109912", 
"109915", "97819" };
set HOURS := 1..24;

param max_travel_cost := 9.9;
param scheduling{TASKS, HOURS}, binary;
param distances{TASKS, TASKS}, >= 0;
param competence{EMPLOYEES, TASKS}, binary;
param cost{EMPLOYEES, TASKS};
param private_limits{EMPLOYEES}, >= 0, <= 24;

var assignments{EMPLOYEES, TASKS}, binary;

minimize total: card(TASKS) - sum{e in EMPLOYEES, t in TASKS} 
assignments[e,t] * 1000000
                 + sum{t in TASKS, e in EMPLOYEES} assignments[e,t] * 
cost[e,t]
                 + sum{e in EMPLOYEES, h in HOURS, t in TASKS: 
scheduling[t,h] = 1}
                     (assignments[e,t] * if h > 1 then (
                         sum{t2 in TASKS: scheduling[t2,h-1] = 1} 
assignments[e,t2] * distances[t,t2]
                     ) else max_travel_cost);

competent{e in EMPLOYEES, t in TASKS}: assignments[e,t] <= competence[e,t];
overlap{e in EMPLOYEES, h in HOURS}: sum{t in TASKS} assignments[e,t] * 
scheduling[t,h] <= 1;
unique{t in TASKS}: sum{e in EMPLOYEES} assignments[e,t] <= 1;
private_limit{e in EMPLOYEES}: sum{h in HOURS, t in TASKS} 
assignments[e,t] * scheduling[t,h] <= private_limits[e];

solve;
for {e in EMPLOYEES, t in TASKS: assignments[e,t] != 0} printf 
"ASSIGNMENTS %s %s\n", t, e;

data;
param scheduling:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
22 23 24 :=
   "44911405.1396" 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   "45917349.728" 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   "45935255.760" 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   "45940559.937" 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   "45940616.810" 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   "45850077.1834" 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
   "45867819.665" 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
   "45875315.776" 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
   "45890352.675" 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
   "45893970.1566" 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
   "45867241.631" 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
   "45903630.1515" 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
   "45934020.614" 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
   "45889432.867" 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
   "45891512.1801" 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
   "45918734.827" 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
   "45921337.721" 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
   "45939669.674" 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0;
param distances:  "44911405.1396" "45917349.728" "45935255.760" 
"45940559.937" "45940616.810" "45850077.1834" "45867819.665" 
"45875315.776" "45890352.675" "45893970.1566" "45867241.631" 
"45903630.1515" "45934020.614" "45889432.867" "45891512.1801" 
"45918734.827" "45921337.721" "45939669.674" :=
   "44911405.1396" 0 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 0.5687 9.9 9.9 
9.9 9.9 9.9 9.9 0.1045
   "45917349.728" 9.9 0 9.9 9.9 9.9 0.1076 0.5568 0.4025 9.9 9.9 9.9 
0.0948 0.0417 9.9 9.9 1.8267 2.8377 9.9
   "45935255.760" 9.9 9.9 0 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 
9.9 9.9 9.9 9.9
   "45940559.937" 9.9 9.9 9.9 0 0.1142 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 
9.9 9.9 9.9 9.9 9.9
   "45940616.810" 9.9 9.9 9.9 0.1142 0 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 
9.9 9.9 9.9 9.9 9.9
   "45850077.1834" 9.9 0.1076 9.9 9.9 9.9 0 0.4898 0.4699 9.9 9.9 9.9 
0.1428 0.0749 9.9 9.9 1.7899 2.7741 9.9
   "45867819.665" 9.9 0.5568 9.9 9.9 9.9 0.4898 0 0.6026 9.9 9.9 9.9 
0.6289 0.5168 9.9 9.9 1.3237 2.2845 9.9
   "45875315.776" 9.9 0.4025 9.9 9.9 9.9 0.4699 0.6026 0 9.9 9.9 9.9 
0.4852 0.4063 9.9 9.9 1.627 2.7272 9.9
   "45890352.675" 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 0 9.9 9.9 9.9 9.9 9.9 
9.9 9.9 9.9 9.9
   "45893970.1566" 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 0 9.9 9.9 9.9 9.9 
9.9 9.9 9.9 9.9
   "45867241.631" 0.5687 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 0 9.9 9.9 
9.9 9.9 9.9 9.9 0.605
   "45903630.1515" 9.9 0.0948 9.9 9.9 9.9 0.1428 0.6289 0.4852 9.9 9.9 
9.9 0 0.1213 9.9 9.9 1.9149 2.9133 9.9
   "45934020.614" 9.9 0.0417 9.9 9.9 9.9 0.0749 0.5168 0.4063 9.9 9.9 
9.9 0.1213 0 9.9 9.9 1.7939 2.7991 9.9
   "45889432.867" 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 0 
9.9 9.9 9.9 9.9
   "45891512.1801" 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 
9.9 0 9.9 9.9 9.9
   "45918734.827" 9.9 1.8267 9.9 9.9 9.9 1.7899 1.3237 1.627 9.9 9.9 9.9 
1.9149 1.7939 9.9 9.9 0 1.1831 9.9
   "45921337.721" 9.9 2.8377 9.9 9.9 9.9 2.7741 2.2845 2.7272 9.9 9.9 
9.9 2.9133 2.7991 9.9 9.9 1.1831 0 9.9
   "45939669.674" 0.1045 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 9.9 0.605 9.9 
9.9 9.9 9.9 9.9 9.9 0;
param cost:  "44911405.1396" "45917349.728" "45935255.760" 
"45940559.937" "45940616.810" "45850077.1834" "45867819.665" 
"45875315.776" "45890352.675" "45893970.1566" "45867241.631" 
"45903630.1515" "45934020.614" "45889432.867" "45891512.1801" 
"45918734.827" "45921337.721" "45939669.674" :=
  "105170" 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 
200 200 200
  "105171" 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 
200 200 200
  "105172" 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 
200 200 200
  "105173" 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 
200 200 200
  "109912" 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 
200 200 200
  "109915" 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 
200 200 200
  "97819" 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 
200 200 200;
param competence:  "44911405.1396" "45917349.728" "45935255.760" 
"45940559.937" "45940616.810" "45850077.1834" "45867819.665" 
"45875315.776" "45890352.675" "45893970.1566" "45867241.631" 
"45903630.1515" "45934020.614" "45889432.867" "45891512.1801" 
"45918734.827" "45921337.721" "45939669.674" :=
  "105170" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  "105171" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  "105172" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  "105173" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  "109912" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  "109915" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  "97819" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1;
param private_limits:=  ["105170"] 24 ["105171"] 24 ["105172"] 24 
["105173"] 24 ["109912"] 24 ["109915"] 24 ["97819"] 24;
end;