-------- Forwarded Message --------
From: Tóth Tamás <[email protected]>
To: [email protected]
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;
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
