Создавайте только допустимые конфигурации с ограничениями

Вот довольно простая модель программирования с ограничениями в 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 )

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

Это не указано в ответах выше, вероятно, потому, что это очевидно для некоторых из нас, но просто попытка перечислить все допустимые комбинации будет работать только в очень небольших тестовых случаях такого рода проблемы. Вы быстро упретесь во время вычислений, если попытаетесь реализовать наивную реализацию.

Как было предложено другими, вам нужно будет изучить некоторые инструменты оптимизации, если вы хотите сделать это для задач реального масштаба. Любой из бесплатных решателей, таких как COIN-OR, glpk или lpsolve; или один из коммерческих инструментов — они могут стать дорогими, но если у вас достаточно большая проблема, то они легко окупятся.