En principio, para problemas de optimización como esto se puede elegir entre los métodos de resolución exacta como Programación lineal y programación de restricción, y métodos aproximados como heurística o cualquier sabor de búsqueda local (que incluye métodos como algoritmos genéticos o recocido simulado).
Para el tamaño del problema que mencionaste, definitivamente usaría un método exacto, ya que solo estos garantizan que encuentres el óptimo global. Con los métodos aproximados, solo puede estar seguro de que ha encontrado el óptimo global si la medida de costo tiene un valor de cero (por ejemplo, no hay infracciones de restricción).
Versión 1: Programación Entera
Su problema puede ser visto como una variante de la Papelera de embalaje. Para este tipo de problema, la programación mixta de enteros (una variante de la programación lineal) es la mejor opción en mi opinión. Necesitará un solucionador MIP, ya que no quiere programar uno usted mismo. El que probablemente sea el mejor gratis se puede encontrar en la biblioteca COIN-OR: CLP/CBC. Está bien, es para problemas pequeños de MIP, pero puede tener problemas con problemas más grandes. Para problemas puros de LP, es bastante bueno, pero para su problema particular, necesita variables de decisión integrales, por lo tanto, MIP. Para problemas MIP de tamaño industrial, necesita un solucionador comercial. Elija entre CPLEX, Xpress o Gurobi. Todos son excelentes
El problema puede ser modelado por lo tanto:
para cada combinación de los asistentes y el taller, se introduce una variable de decisión binaria. La variable será una si el asistente visita el taller. En su ejemplo, habrá 1800 de esas variables.
para cada asistente, la suma de las variables de decisión será el número de talleres visitados. En tu ejemplo, esto es tres.
para cada asistente, la suma de los talleres superpuestas es como máximo 1.
un costo unitario se induce si un asistente debe visitar una opción de reserva
variables de decisión para los cursos que tiene un asistente no seleccionado se establece en cero
El objetivo es, entonces, minimizar el costo total.
Aquí hay un código rápidamente escrita ejemplo en Eclipse (una variante de Prolog):
:- 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]).
He generado asistentes y sus opciones al azar. La lista de exclusión está codificada. Aquí está la salida generada a correr:
?- 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)
es decir, en la solución, 219 veces un asistente se colocó en una opción de reserva. Tenga en cuenta que esto se debe exclusivamente a las restricciones de exclusión de superposición, ya que no hay limitaciones de capacidad en los tamaños de taller en el modelo. Los talleres seleccionados para el primer asistente son 2, 3 y 6. La primera opción de [2,3,4] era inviable, ya que los talleres 3 y 4 se superponen. (He editado los asistentes restantes de la respuesta)
Para esta prueba, he utilizado el solucionador CLP/CBC libre de la biblioteca COIN-OR, que se incluye en la distribución ECLiPSe. COIN-OR también ofrece bibliotecas API para C++ y Python.
Versión 2: Restricción Programación Lógica
Aquí hay una segunda versión, esta vez usando Lógica Programación con restricciones. La Programación de Restricción es otro método de solución exacto. Aquí, yo uso un modelo diferente:
para cada asistente, construya una lista de tres variables.Estas variables denotan los talleres asignados y, por lo tanto, tienen los números del taller como dominio. Las tres variables deben tener valores diferentes.
para romper las simetrías, impongo que las variables deben estar aumentando en su orden.
los talleres no deseados se eliminan de los dominios.
vinculante las variables para reservar opciones induce costos unitarios
elegir un taller para una de las variables elimina cualquier taller superposición del dominio de las otras variables.
La clave para una Programación de Restricción exitosa es seleccionar una estrategia de etiquetado inteligente, donde las variables están vinculadas a los valores. Dado que en este ejemplo, no hay restricciones de capacidad en los talleres, uno simplemente puede elegir talleres preferidos hasta que los dominios contengan solo talleres de reserva (debido a las restricciones de exclusión). Sin embargo, el orden de valores es crucial aquí: uno debe comenzar con los talleres con la menor coincidencia.
Si esto se hace, no será necesaria ninguna optimización: la primera solución será óptima (gracias a la falta de restricciones de capacidad). De lo contrario, uno encontrará una solución que esté cerca de ser óptima, pero luego tendrá que atravesar un enorme árbol de búsqueda para encontrar una mejor solución.
Aquí está el código, de nuevo en Eclipse:
:- 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]).
Tenga en cuenta que los predicados de generación de problemas son los mismos que en la solución MIP. Aquí está la salida de una ejecución:
?- 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)
Como puede ver, es algo más lenta que la solución MIP. Además, la solución real es ligeramente diferente, aunque tiene el mismo costo.
¿Qué versión debe elegir? Depende de qué otras restricciones esperas agregar. Si se trata de restricciones de capacidad, use MIP. Si hay restricciones más complicadas, como restricciones de programación, entonces CLP será mejor. Con un sistema como ECLiPSe también puedes construir algoritmos híbridos.
Usted debe mirar en la [Problema del viajante] (http://en.wikipedia.org/wiki/Travelling_salesman_problem). También [Job Shop] (http://en.wikipedia.org/wiki/Job_shop_scheduling). La dificultad de este problema es que la mayoría de los sistemas de reservación hacen que los usuarios seleccionen los eventos específicos que desean. – DampeS8N
No podía recordar esto por mi vida. Otra variación es el [Knapsack Problem] (http://en.wikipedia.org/wiki/Knapsack_problem). – DampeS8N