सिद्धांत रूप में के लिए अच्छा है इस तरह आप की तरह सटीक हल करने के तरीकों के बीच विकल्प नहीं है अनुकूलन समस्याओं के लिए है रैखिक प्रोग्रामिंग और बाधा प्रोग्रामिंग, और ह्यूरिस्टिक्स या स्थानीय खोज के किसी भी स्वाद जैसे अनुमानित तरीकों (जिसमें जेनेटिक एल्गोरिदम या सिम्युलेटेड एनीलिंग जैसी विधियां शामिल हैं)।
आपके द्वारा उल्लिखित समस्या के आकार के लिए, मैं निश्चित रूप से एक सटीक विधि का उपयोग करूंगा, क्योंकि केवल ये गारंटी है कि आपको वैश्विक इष्टतम मिल जाएगा। अनुमानित तरीकों के साथ, आप केवल यह सुनिश्चित कर सकते हैं कि यदि वैश्विक मूल्य शून्य का मूल्य है (उदाहरण के लिए, कोई बाधा उल्लंघन नहीं है) तो आपको वैश्विक इष्टतम मिल गया है।
संस्करण 1: पूर्णांक प्रोग्रामिंग
आपकी समस्या बिन पैकिंग का एक प्रकार के रूप में देखा जा सकता है। इस प्रकार की समस्या के लिए, मिश्रित इंटीजर प्रोग्रामिंग (रैखिक प्रोग्रामिंग का एक संस्करण) मेरी राय में सबसे अच्छा विकल्प है। आपको एक एमआईपी सॉल्वर की आवश्यकता होगी, क्योंकि आप खुद को प्रोग्राम नहीं करना चाहते हैं। शायद सबसे अच्छा मुफ्त एक कोइन-ओआर पुस्तकालय में पाया जा सकता है: सीएलपी/सीबीसी। यह छोटी एमआईपी समस्याओं के लिए ठीक है- लेकिन बड़े लोगों के साथ परेशानियों में भाग सकता है। शुद्ध एलपी समस्याओं के लिए, यह काफी अच्छा है, लेकिन आपकी विशेष समस्या के लिए, आपको अभिन्न निर्णय चर की आवश्यकता है, इसलिए एमआईपी। औद्योगिक आकार की एमआईपी समस्याओं के लिए, आपको एक वाणिज्यिक सॉल्वर की आवश्यकता है। सीपीएलईएक्स, एक्सप्रेस, या गुरुबी का अपना चयन लें। वे सभी उत्कृष्ट हैं।
समस्या इस प्रकार तैयार किया जा सकता:
- प्रतिभागी और कार्यशाला के प्रत्येक संयोजन के
, आप एक द्विआधारी निर्णय चर परिचय। यदि कर्मचारी कार्यशाला का दौरा करता है तो चर एक होगा। आपके उदाहरण में, 1800 ऐसे चर होंगे। प्रत्येक उपस्थिति के लिए
, निर्णय चर के योग विज़िट की गई कार्यशालाओं की संख्या होगी। आपके उदाहरण में, यह तीन है।
- प्रत्येक उपस्थित व्यक्ति के लिए
, ओवरलैपिंग कार्यशालाओं की राशि अधिक से अधिक 1.
अगर एक प्रतिभागी पाठ्यक्रम में उपस्थित होने वाले है कि के लिए एक आरक्षित पसंद
निर्णय चर पर जाना होगा एक इकाई लागत प्रेरित है है चयनित नहीं हैं
उद्देश्य कुल लागत को कम करने के लिए है।
:- lib(eplex).
:- lib(random).
:- lib(listut).
:- local struct(attendee(choices, reserve, workshops)).
generate_attendees(NA, NW, NC, NR, Atts) :-
seed(1), % always generate the same set
(for(I, 1, NW), foreach(I, WD) do true),
(
for(_I, 1, NA),
foreach(Att, Atts),
param(NC, NR, WD)
do
Att = attendee{},
generate_choices(Att, NC, NR, WD)
).
generate_choices(Att, NC, NR, WD) :-
(
for(_I, 1, NC),
fromto(WD, DI, DO, RD),
foreach(C, Choices)
do
select_course(DI, C, DO)
),
(
for(_I, 1, NR),
fromto(RD, DI, DO, _),
foreach(R, Reserve)
do
select_course(DI, R, DO)
),
Att = attendee{choices:Choices, reserve:Reserve}.
select_course(L, E, RL) :-
length(L, LL),
random(R),
N is R mod LL,
nth0(N, L, E, RL).
solve_with_mip(Atts, NA, NW, NC, Excl) :-
decision_vars(NA, NW, Decs),
workshop_visits(Decs, NA, NW, NC),
workshop_choices(Atts, Decs, NA, NW, Cost),
workshop_exclusions(Decs, NA, Excl),
% set up solver and solve
eplex:eplex_solver_setup(min(Cost), Cost, [], []),
eplex:eplex_solve(Result),
printf("Found solution with cost: %w%n", [Result]),
% retrieve solution
eplex:eplex_get(vars, Vars),
eplex:eplex_get(typed_solution, Vals),
Vars = Vals,
retrieve_solution(Atts, Decs, NA, NW).
% make array of decision variables
decision_vars(NA, NW, Decs):-
dim(Decs, [NA,NW]),
(
multifor(Idx, 1, [NA,NW]),
foreach(D, Ds),
param(Decs)
do
subscript(Decs, Idx, D),
eplex:(D $>= 0),
eplex:(D $=< 1)
),
eplex:integers(Ds).
% each attendee visits NC workshops
workshop_visits(Decs, NA, NW, NC) :-
(
for(AIdx, 1, NA),
param(Decs, NW, NC)
do
(
for(WIdx, 1, NW),
fromto(0, R, D+R, Sum),
param(AIdx, Decs)
do
subscript(Decs, [AIdx, WIdx], D)
),
eplex:(Sum $= NC)
).
% each attendee must not visit a workshop not in
% her list of choices or reserve choices
% choosing a reserve workshop induces a unit cost
workshop_choices(Atts, Decs, NA, NW, Cost):-
(
for(AIdx, 1, NA),
foreach(Att, Atts),
fromto(0, CI, CO, Cost),
param(Decs, NW)
do
Att = attendee{choices:Cs, reserve:Rs},
(
for(WIdx, 1, NW),
fromto(CI, ACI, ACO, CO),
param(Decs, AIdx, Cs, Rs)
do
(
memberchk(WIdx, Cs)
->
% choices do not induce cost
ACO = ACI
;
memberchk(WIdx, Rs)
->
% reserves induce unit cost
% (if decision variable is 1)
subscript(Decs, [AIdx, WIdx], D),
ACO = ACI + D
;
% other workshops must not be chosen
subscript(Decs, [AIdx, WIdx], D),
eplex:(D $= 0),
ACO = ACI
)
)
).
% some workshops overlap, so exclude each other
workshop_exclusions(Decs, NA, Excl) :-
(
foreach(W1-W2, Excl),
param(Decs, NA)
do
(
for(AIdx, 1, NA),
param(Decs, W1, W2)
do
subscript(Decs, [AIdx, W1], D1),
subscript(Decs, [AIdx, W2], D2),
eplex:(D1+D2 $=< 1)
)
).
% retrieve workshopnumbers for attendees
retrieve_solution(Atts, Decs, NA, NW) :-
(
for(AIdx, 1, NA),
foreach(Att, Atts),
param(Decs, NW)
do
(
for(WIdx, 1, NW),
fromto([], WI, WO, Ws),
param(Decs, AIdx)
do
subscript(Decs, [AIdx, WIdx], D),
(D == 1 -> WO = [WIdx|WI] ; WO = WI)
),
Att = attendee{workshops:Ws}
).
test(Atts) :-
NA = 300,
NW = 6,
NC = 3,
NR = 2,
% list of exclusions
Excl = [1-2, 1-3, 3-4, 5-6],
generate_attendees(NA, NW, NC, NR, Atts),
cputime(T1),
solve_with_mip(Atts, NA, NW, NC, Excl),
cputime(T2),
D1 is T2-T1,
printf("Found solution with MIP in %w seconds.%n", [D1]).
मैं बेतरतीब ढंग से उपस्थित लोग और उनकी विकल्प पैदा किया:
यहाँ एक जल्दी से लिखा उदाहरण ग्रहण में कोड (Prolog का एक प्रकार) है। बहिष्करण सूची हार्ड कोडित है।
?- test(Atts).
Found solution with cost: 219.0
Found solution with MIP in 0.119999999999997 seconds.
Atts = [attendee([2, 3, 4], [5, 6], [6, 3, 2]), attendee(...), ...]
Yes (0.12s cpu)
अर्थात, और समाधान में, 219 बार में उपस्थित होने वाले एक आरक्षित चुनाव में रखा गया था: यहाँ उत्पादन एक रन के लिए उत्पन्न है। ध्यान दें कि यह ओवरलैप बहिष्करण बाधाओं के कारण पूरी तरह से है, क्योंकि मॉडल में कार्यशाला आकारों पर कोई क्षमता बाधा नहीं है। पहली उपस्थिति के लिए चयनित कार्यशालाएं 2, 3, और 6 हैं। [2,3,4] की पहली पसंद अक्षम थी, क्योंकि कार्यशालाएं 3 और 4 ओवरलैप थीं। (मैंने शेष उपस्थित लोगों को उत्तर से संपादित किया है)
इस परीक्षण के लिए, मैंने सीओआईएन-सी पुस्तकालय से मुफ्त सीएलपी/सीबीसी सॉल्वर का उपयोग किया है, जो ईसीएलआईपीएस वितरण में शामिल है। सीओआईएन-या सी ++ और पायथन के लिए एपीआई लाइब्रेरी भी प्रदान करता है।
संस्करण 2: बाधा तर्क प्रोग्रामिंग
यहाँ एक दूसरा संस्करण, इस समय बाधा तर्क प्रोग्रामिंग का उपयोग कर रहा है। प्रतिबंध प्रोग्रामिंग एक और सटीक समाधान विधि है। यहां, मैं एक अलग मॉडल का उपयोग करता हूं:
प्रत्येक उपस्थिति के लिए, तीन चर की एक सूची बनाएं।ये चर निर्दिष्ट कार्यशालाओं को दर्शाते हैं, और इसलिए कार्यशाला संख्या डोमेन के रूप में होती है। सभी तीन चरों में अलग-अलग मान होना चाहिए।
समरूपता तोड़ने के लिए, मैं लागू करता हूं कि चर उनके क्रम में बढ़ रहे हैं।
अवांछित कार्यशालाओं को डोमेन से हटा दिया जाता है।
चर बाध्यकारी विकल्पों आरक्षण इकाई लागत
को प्रेरित करता है के लिए चर में से एक अन्य चर के डोमेन से किसी भी अतिव्यापी कार्यशाला को हटा एक कार्यशाला चुनने।
सफल बाधा प्रोग्रामिंग के लिए कुंजी एक चतुर लेबलिंग रणनीति है, जहां चर मूल्यों के लिए बाध्य कर रहे हैं का चयन किया गया है। चूंकि इस उदाहरण में, कार्यशालाओं पर कोई क्षमता बाधा नहीं है, कोई भी पसंदीदा वर्कशॉप चुन सकता है जब तक कि डोमेन में केवल आरक्षित कार्यशालाएं न हों (बहिष्करण बाधाओं के कारण)। हालांकि, मूल्य आदेश यहां महत्वपूर्ण है: किसी को कम से कम ओवरलैप के साथ कार्यशालाओं के साथ शुरू करना चाहिए।
यदि यह किया जाता है, तो कोई अनुकूलन आवश्यक नहीं होगा: पहला समाधान इष्टतम होगा (क्षमता बाधाओं की कमी के कारण)। अन्यथा, एक ऐसे समाधान को मिलेगा जो इष्टतम के करीब है, लेकिन फिर बेहतर समाधान खोजने के लिए एक विशाल खोज पेड़ को पार करना होगा।
यहाँ ग्रहण में कोड है, फिर से:
:- lib(ic).
:- lib(random).
:- lib(lists).
:- lib(listut).
:- local struct(attendee(choices, reserve, workshops)).
solve_with_clp(Atts, NA, NW, NC, Excl) :-
decision_vars_clp(NA, NW, NC, Decs),
workshop_choices_clp(Atts, Decs, NA, NW, NC, CostSum),
workshop_exclusions_clp(Decs, NA, NW, Excl, BestOrder),
% solve
Cost #= eval(CostSum),
% order for labeling worskhops
% start with workshop with fewest exclusions
% should be computed!
label(Decs, Atts, BestOrder),
printf("Found solution with cost: %w%n", [Cost]),
% retrieve solution
retrieve_solution_clp(Atts, Decs, NA).
% search solution
label(Decs, Atts, BestOrder) :-
(
foreacharg(A, Decs),
foreach(Att, Atts),
param(BestOrder)
do
Att = attendee{choices:Cs, reserve:Rs},
label_att(A, Cs, Rs, BestOrder)
).
label_att(A, Cs, Rs, BestOrder) :-
(
foreacharg(C, A),
param(Cs, Rs, BestOrder)
do
(
member(V, BestOrder),
memberchk(V, Cs)
;
member(V, BestOrder),
memberchk(V, Rs)
),
C#= V
).
% make array of decision variables
% for each attendee, one variable for every visited course is created
decision_vars_clp(NA, NW, NC, Decs):-
dim(Decs, [NA,NC]),
(
multifor(Idx, 1, [NA,NC]),
foreach(D, Ds),
param(Decs)
do
subscript(Decs, Idx, D)
),
Ds #:: 1..NW,
% for each attendee, each variable must have a different value
(
for(AIdx, 1, NA),
param(Decs, NC)
do
(
for(CIdx, 1, NC),
foreach(C, Cs),
param(Decs, AIdx)
do
subscript(Decs, [AIdx,CIdx], C)
),
alldifferent(Cs),
% break symmetry by requiring ascending order
Cs = [H|T],
(
foreach(C, T),
fromto(H, L, C, _)
do
C#> L
)
).
% each attendee must not visit a workshop not in
% her list of choices or reserve choices
% choosing a reserve workshop induces a unit cost
workshop_choices_clp(Atts, Decs, NA, NW, NC, Cost):-
(
for(AIdx, 1, NA),
foreach(Att, Atts),
fromto(0, CI, CO, Cost),
param(Decs, NW, NC)
do
Att = attendee{choices:Cs, reserve:Rs},
% make list of costs
functor(RCost, c, NW),
(
for(I, 1, NW),
param(Rs, RCost)
do
(memberchk(I, Rs) -> arg(I, RCost, 1) ; arg(I, RCost, 0))
),
RCost =.. [_|RCL],
% remove unwanted workshops
(
for(CIdx, 1, NC),
param(Decs, AIdx, Cs, Rs, NW)
do
subscript(Decs, [AIdx, CIdx], C),
(
for(I, 1, NW),
param(Cs, Rs, C)
do
(
(memberchk(I, Cs) ; memberchk(I, Rs))
->
true
;
C#\= I
)
)
),
% add costs for workshops
(
for(CIdx, 1, NC),
fromto(CI, ACI, ACO, CO),
param(Decs, AIdx, RCL)
do
subscript(Decs, [AIdx, CIdx], C),
element(C, RCL, CCost),
ACO = ACI+CCost
)
).
% some workshops overlap, so exclude each other
% assumption: W1 < W2
% also compute best order to label workshops:
% start with lowest number of overlaps
workshop_exclusions_clp(Decs, NA, NW, Excl, BestOrder) :-
(
foreach(W1-W2, Excl),
param(Decs, NA)
do
(
for(AIdx, 1, NA),
param(Decs, W1, W2)
do
subscript(Decs, [AIdx], ACs),
ACs =.. [_|ACList],
(
fromto(ACList, [H|T], T, [_]),
param(W1, W2)
do
(
foreach(N, T),
param(H, W1, W2)
do
(H #= W1 => N #\= W2),
(N #= W2 => H #\= W1)
)
)
)
),
% compute best order for labeling workshops
(
for(W, 1, NW),
foreach(C-W, CWs),
param(Excl)
do
(
foreach(W1-W2, Excl),
fromto(0, I, O, C),
param(W)
do
(memberchk(W, [W1,W2]) -> O is I+1 ; O = I)
)
),
sort(CWs, SCWs),
(foreach(_-W, SCWs), foreach(W, BestOrder) do true).
% retrieve workshop numbers for attendees
retrieve_solution_clp(Atts, Decs, NA) :-
(
for(AIdx, 1, NA),
foreach(Att, Atts),
param(Decs)
do
subscript(Decs, [AIdx], AD),
AD =.. [_|Ws],
Att = attendee{workshops:Ws}
).
test(Atts1) :-
NA = 300,
NW = 6,
NC = 3,
NR = 2,
% list of exclusions
Excl = [1-2, 1-3, 3-4, 5-6],
generate_attendees(NA, NW, NC, NR, Atts1),
cputime(T1),
solve_with_clp(Atts1, NA, NW, NC, Excl),
cputime(T2),
D is T2-T1,
printf("Found solution with CLP in %w seconds.%n", [D]).
ध्यान दें कि समस्या पीढ़ी विधेय MIP समाधान में जैसे ही हैं। यहां एक रन के लिए आउटपुट है:
?- test(A).
Found solution with cost: 219
Found solution with CLP in 0.330000000000002 seconds.
A = [attendee([2, 3, 4], [5, 6], [2, 4, 5]), ...]
Yes (0.34s cpu, solution 1, maybe more)
जैसा कि आप देख सकते हैं, यह एमआईपी समाधान से कुछ हद तक धीमा है। इसके अलावा, वास्तविक समाधान थोड़ा अलग है, हालांकि इसकी एक ही कीमत है।
आपको कौन सा संस्करण चुनना चाहिए? यह इस बात पर निर्भर करता है कि आप कौन सी बाधाओं को जोड़ना चाहते हैं। यदि इसकी क्षमता बाधाएं हैं, तो एमआईपी का उपयोग करें। यदि वहां शेड्यूलिंग बाधाओं जैसी अधिक जटिल बाधाएं हैं, तो सीएलपी बेहतर होगा। ECLiPSe जैसी प्रणाली के साथ आप हाइब्रिड एल्गोरिदम भी बना सकते हैं।
आप [यात्रा विक्रेता की समस्या] ध्यान देना चाहिए (http://en.wikipedia.org/wiki/Travelling_salesman_problem)। इसके अलावा [जॉब शॉप] (http://en.wikipedia.org/wiki/Job_shop_scheduling)। इस समस्या की कठिनाई यह है कि अधिकांश आरक्षण प्रणालियां उपयोगकर्ताओं को चुनती हैं कि वे कौन सा विशिष्ट घटना समय चाहते हैं। – DampeS8N
मुझे यह मेरे जीवन के लिए याद नहीं आया। एक और भिन्नता [Knapsack समस्या] (http://en.wikipedia.org/wiki/Knapsack_problem) है। – DampeS8N