[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] [Fwd: Newbie help request]
From: |
Andrew Makhorin |
Subject: |
[Help-glpk] [Fwd: Newbie help request] |
Date: |
Tue, 19 Nov 2013 22:13:51 +0400 |
-------- 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;
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Help-glpk] [Fwd: Newbie help request],
Andrew Makhorin <=