fixpoint

#
# Assignment problems in Elixir.
#
  # Different assignments problem, both minimization and maximization.
  # See the sources of the problem below.

  # Compare to the following MiniZinc models, from which these problems
  # are taken:
  # * http://www.hakank.org/minizinc/assignment.mzn
  # * http://www.hakank.org/minizinc/assignment2.mzn
  # * http://www.hakank.org/minizinc/assignment2_2.mzn
  # * http://www.hakank.org/minizinc/assignment3.mzn
  # * http://www.hakank.org/minizinc/assignment5.mzn
  # * http://www.hakank.org/minizinc/assignment6.mzn

# This program was created by Hakan Kjellerstrand, hakank@gmail.com
# See also my Elixir page: http://www.hakank.org/elxir/
#
defmodule CPSolver.Examples.Hakank.Assignment do

  alias CPSolver.IntVariable
  # alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
  alias CPSolver.Constraint.Sum
  alias CPSolver.Constraint.LessOrEqual
  # alias CPSolver.Constraint.NotEqual
  # alias CPSolver.Constraint.Equal
  alias CPSolver.Model
  alias CPSolver.Objective

  import CPSolver.Constraint.Factory
  import CPSolver.Variable.View.Factory

  import Hakank.CPUtils
  #
  # Data from
  # Winston "Operations Research", Assignment Problems, page 393f
  # I added the fifth column
  #
  def problem(1) do
    op = :minimize
    cost = [[14,  5, 8,  7, 15],
            [ 2, 12, 6,  5,  3],
            [ 7,  8, 3,  9,  7],
            [ 2,  4, 6, 10,  1]]
    [op,cost]
  end

  #
  # Winston "Operations Research", page 398, swimming team example
  # (original version]
  # See http://www.hakank.org/minizinc/assignment2.mzn
  #
  def problem(2) do
    op = :minimize
    cost = [[54, 54, 51, 53],
            [51, 57, 52, 52],
            [50, 53, 54, 56],
            [56, 54, 55, 53]]
    [op,cost]
  end

  #
  # Winston "Operations Research", page 398, swimming team example
  # See http://www.hakank.org/minizinc/assignment2_2.mzn
  # expanded version
  #
  def problem(3) do
    op = :minimize
    cost = [[54, 54, 51, 53,   50,60,70,80,90,100],
            [51, 57, 52, 52,   40,50,60,70,80, 90],
            [50, 53, 54, 56,   40,50,60,80,93, 69],
            [56, 54, 55, 53,   60,80,40,60,50,100]]
    [op,cost]
  end


  #
  # Winston "Operations Research", page 399
  #
  # """
  # Tom Cruise, Freddy Prinze Jr, Harrison Ford, and Matt LeBlanc
  # are marooned on a desert island with Jennifer Anniston,
  # Courtney Cos, Gwynneth Paltrow, and Julia Roberts.
  # The 'compatibility matrix' in Table 52 indicate how much happiness
  # each couple would experience if the spend all their time toghether.
  # The happiness earned by a couple is proportional to the fraction
  # of time the spend toghether.
  # ...
  # The optimal solution requires that that each person send all their
  # time with one person of the opposite sex, so this result is often
  # referred to as the Marriage Theorem.
  # """
  #
  # See http://www.hakank.org/minizinc/assignment3.mzn

  # males:
  # 1 "Tom Cruise"
  # 2 "Freddie Prinz Jr"
  # 3 "Harrison Ford"
  # 4 "Mark LeBlanc"
  #
  # females:
  # 1 "Jennifer Anniston"
  # 2 "Courtney Cox"
  # 3 "Gwynneth Paltrow"
  # 4 "Julia Roberts"
  def problem(4) do
    op = :maximize
    cost = [[7, 5, 8, 2],
            [7, 8, 9, 4],
            [3, 5, 7, 9],
            [5, 5, 6, 7]]
    [op,cost]
  end


  # From
  #  "SAS OR 9.1 User's Guide Mathematical Programming"
  # """
  # Consider assigning five programmers to five programming jobs. Each
  # programmer prefers specific programming job over others. [...]
  # Suppose you ask each programmer to rank the jobs according to preference
  # (using 1 for the most preferred job and 5 for the least preffered job].
  # PROC ASSIGN maximizes the total preference of the group by minimizing the
  # sum of the preferences.
  #
  #    PROGRAMMER     JOB1 JOB2 JOB3 JOB4 JOB5
  #    PROGRAMMER1    4    1    3    5    2
  #              2    2    1    3    4    5
  #              3    3    2    4    1    5
  #              4    2    3    4    5    1
  #              5    4    2    3    1    5
  #
  # """
  #
  # See http://www.hakank.org/minizinc/assignment5.mzn
  #
  def problem(5) do
    op = :minimize
    cost = [[4, 1, 3, 5, 2],
            [2, 1, 3, 4, 5],
            [3, 2, 4, 1, 5],
            [2, 3, 4, 5, 1],
            [4, 2, 3, 1, 5]]
    [op,cost]
  end


  #
  # From GLPK:s example assign.mod:
  # """
  # The assignment problem is one of the fundamental combinatorial
  # optimization problems.
  #
  # In its most general form, the problem is as follows:
  #
  # There are a number of agents and a number of tasks. Any agent can be
  # assigned to perform any task, incurring some cost that may vary
  # depending on the agent-task assignment. It is required to perform all
  # tasks by assigning exactly one agent to each task in such a way that
  # the total cost of the assignment is minimized.
  #
  # (From Wikipedia, the free encyclopedia.]
  # """
  #
  # """
  # These data correspond to an example from [Christofides].
  # """
  #
  # See http://www.hakank.org/minizinc/assignment6.mzn
  #
  ## Boris Okner: modified to sync with the latest API,
  ## change naming and result handling.
  ##
  def problem(6) do
    op = :minimize
    cost = [[13, 21, 20, 12,  8, 26, 22, 11],
            [12, 36, 25, 41, 40, 11,  4,  8],
            [35, 32, 13, 36, 26, 21, 13, 37],
            [34, 54,  7,  8, 12, 22, 11, 40],
            [21,  6, 45, 18, 24, 34, 12, 48],
            [42, 19, 39, 15, 14, 16, 28, 46],
            [16, 34, 38,  3, 34, 40, 22, 24],
            [26, 20,  5, 17, 45, 31, 37, 43]]
    [op,cost]
  end



  def run() do

    for p <- 1..6 do
      IO.puts("\nProblem #{p}")
      [op,cost] = problem(p)
      assignment(op, cost)
    end

  end

  def assignment(op, cost) do

    rows = length(cost)
    cols = length(Enum.at(cost,0))

    # Who to assign to what task
    x = for i <- 0..rows-1 do
           for j <- 0..cols-1 do
              IntVariable.new(0..1, name: "x[#{i},#{j}]")
           end
    end

    x_flatten = x |> List.flatten

    total_cost = IntVariable.new(0..Enum.sum(cost |> List.flatten), name: "total_cost")


    # exacly one assignment per row, all rows must be assigned
    row_constraints = for i <- 0..rows-1  do
                        Sum.new(1,for j <- 0..cols-1 do mat_at(x,i,j) end)
    end

    # zero or one assignments per column
    column_constraints = for j <- 0..cols-1  do
                                           {c_var,c_cons} = sum(for i <- 0..rows-1 do mat_at(x,i,j) end)
                                           less_cons = LessOrEqual.new(c_var,1)
                                           [c_cons,less_cons]
    end

    # calculate total_cost
    total_cost_constraint = Sum.new(total_cost, for i <- 0..rows-1, j <- 0..cols-1 do
                                                    mul(mat_at(x,i,j),mat_at(cost,i,j))
                                                end)

    model = Model.new(x_flatten ++ [total_cost],
      (row_constraints ++ column_constraints ++ [total_cost_constraint]) |> List.flatten,
      objective: if op == :minimize do Objective.minimize(total_cost) else Objective.maximize(total_cost) end
    )

    Logger.configure(level: :info)

    opts = [
      search: {:first_fail, :indomain_min},
      #search: {:input_order, :indomain_min},
      # search: {:first_fail, :indomain_random},
      timeout: :infinity,
      # stop_on: {:max_solutions, 2},
      ]
    {:ok, res} = CPSolver.solve(model,
                                     opts
                                     )
    # IO.inspect(res.statistics)
    sol = res.solutions |> List.last

    total_cost_val = Enum.at(sol,rows*cols)
    IO.puts("total_cost: #{total_cost_val}")
    mat = Enum.take(sol,rows*cols)
    print_matrix(mat,rows,cols)

    for i <- 0..rows-1, j <- 0..cols-1, Enum.at(mat,i*cols+j) == 1 do j end
    |> IO.inspect(label: "assigned")


  end

end