Генерирайте само валидни конфигурации с ограничения

Ето един доста прост модел за програмиране на ограничения в MiniZinc, който - при правилния решаващ инструмент - генерира всички възможни валидни решения за (моята интерпретация на) проблема. Въпреки това, както посочва @TimChippingtonDerrick, за по-сложни проблемни случаи има твърде много решения.

Въпреки това, ако целта (obj = "2a + 5b") може по някакъв начин да бъде заявена в модела (напр. като се използват някои допълнителни данни на интервюиращия/кандидатите и т.н.), това е просто въпрос на промяната й на оптимизационен проблем, т.е. минимизиране на или максимизиране на тази цел.

И така, ето модела MiniZinc за прост екземпляр на проблем (x=10, y=5, z=10 и m=3). Забележка: в таблицата с интервюта стойността 0 (нула) означава, че няма интервю за интервюиращия по това време.

include "globals.mzn"; 

int: x = 10; % number of time slots
int: y =  5; % number of faculty interviewers
int: z = 10; % number of applicants interviewing

int: m = 3; % number of times each applicants will be interviewed

% decision variables
% The interview table:
%   1..y: rows (interviewers)
%   1..x: columns (time slots)
array[1..y, 1..x] of var 0..z: s;

% solve satisfy;
solve :: int_search([s[i,j] | i in 1..y, j in 1..x], first_fail, indomain_random, complete) satisfy;

constraint

    % A z digit can only appear once in each row/column like Sudoku (because an applicant 
    % can't interview with the same interviewer twice and he/she can't interview twice at once).
    forall(a in 1..z) (
       % rows
       forall(i in 1..y) (
          %sum([bool2int(s[i,j] = a) | j in 1..x]) <= 1
          alldifferent_except_0([bool2int(s[i,j] = a) | j in 1..x])
       )
       /\
       % columns
       forall(j in 1..x) (
          % sum([bool2int(s[i,j] = a) | i in 1..y]) <= 1
          alldifferent_except_0([bool2int(s[i,j] = a) | i in 1..y])
       )
    )

    % There has to be exactly 3 of each z number in the entire table 
    % (because all applicants have to interview exactly 3 times).
    /\
    forall(a in 1..z) (
       count([s[i,j] | i in 1..y, j in 1..x], a, m)
    )
;

% constraint
%   % symmetry breaking: assign applicant a to interviewer a in time a (if possible)
%   forall(a in 1..z where a <= y) (
%      s[a,a] = a
%   )
% ;


output [
   "x (number of time slots (rows): " ++ show(x) ++ "\n" ++
   "y (number of interviews (columns): " ++ show(y) ++ "\n" ++
   "z (number of applicants): " ++ show(z) ++ "\n"
]
++
[
  if j = 1 then "\n" else " " endif ++
    show_int(2,s[i,j])
  | i in 1..y, j in 1..x
];

За този проблем (x=10, y=5, z=10) има огромен брой решения. Ето две от тях:

x (number of time slots (rows): 10
y (number of interviews (columns): 5
z (number of applicants): 10

5  2 10  8  0  6  7  4  3  9
3  1  5  7  0  2  9  6  8  4
8  0  0  5  6  1 10  3  0  7
2 10  1  0  0  9  0  0  0  0
0  0  0  0  0  4  0  0  0  0
----------
x (number of time slots (rows): 10
y (number of interviews (columns): 5
z (number of applicants): 10

 5  2 10  8  0  6  7  4  3  9
 3  1  5  7  0  2  9  6  8  4
 8  0  0  5  6  1 10  3  0  7
 2 10  0  1  0  9  0  0  0  0
 0  0  0  0  0  4  0  0  0  0

(Този модел MiniZinc също е тук: http://www.hakank.org/minizinc/interview_scheduling.mzn )

Числен коментар за по-прост проблем (x=6,y=3,z=3, m=3), за да се покаже множеството на проблема: Има 317760 различни решения, когато не се използва нарушаването на симетрията (което е коментирано в код). С нарушаването на симетрията има много по-малко решения: 1300. Ето едно от тези решения:

1  0  0  3  2  0
3  2  1  0  0  0
0  1  3  2  0  0

Неговият вид е неизложен в отговорите по-горе, вероятно защото е очевиден за някои от нас, но просто опитът да се изброят всички легални комбинации ще работи само в много малки тестови случаи на този вид проблем. Бързо ще ударите стената във времето за изчисление, ако опитате наивна реализация.

Както беше предложено от други, ще трябва да разгледате използването на някои инструменти за оптимизация, ако искате да направите това за проблеми в реален мащаб. Или един от безплатните решаващи програми като COIN-OR, glpk или lpsolve; или някой от търговските инструменти - те могат да станат скъпи, но ако имате достатъчно голям проблем, тогава те лесно си заслужават цената.