examples/notebook/steel_mill_slab_sat.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copyright 2010-2017 Google\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "\n",
    "from __future__ import print_function\n",
    "import argparse\n",
    "import time\n",
    "from ortools.sat.python import cp_model\n",
    "from ortools.linear_solver import pywraplp\n",
    "\n",
    "PARSER = argparse.ArgumentParser()\n",
    "\n",
    "PARSER.add_argument(\n",
    "    '--problem', default=2, type=int, help='Problem id to solve.')\n",
    "PARSER.add_argument(\n",
    "    '--break_symmetries',\n",
    "    default=True,\n",
    "    type=bool,\n",
    "    help='Break symmetries between equivalent orders.')\n",
    "PARSER.add_argument(\n",
    "    '--solver',\n",
    "    default='sat_table',\n",
    "    help='Method used to solve: sat, sat_table, sat_column, mip_column.')\n",
    "PARSER.add_argument(\n",
    "    '--output_proto',\n",
    "    default='',\n",
    "    help='Output file to write the cp_model proto to.')\n",
    "\n",
    "def BuildProblem(problem_id):\n",
    "  \"\"\"Build problem data.\"\"\"\n",
    "  if problem_id == 0:\n",
    "    capacities = [\n",
    "        0, 12, 14, 17, 18, 19, 20, 23, 24, 25, 26, 27, 28, 29, 30, 32, 35, 39,\n",
    "        42, 43, 44\n",
    "    ]\n",
    "    num_colors = 88\n",
    "    num_slabs = 111\n",
    "    orders = [\n",
    "        (4, 1),  # (size, color)\n",
    "        (22, 2),\n",
    "        (9, 3),\n",
    "        (5, 4),\n",
    "        (8, 5),\n",
    "        (3, 6),\n",
    "        (3, 4),\n",
    "        (4, 7),\n",
    "        (7, 4),\n",
    "        (7, 8),\n",
    "        (3, 6),\n",
    "        (2, 6),\n",
    "        (2, 4),\n",
    "        (8, 9),\n",
    "        (5, 10),\n",
    "        (7, 11),\n",
    "        (4, 7),\n",
    "        (7, 11),\n",
    "        (5, 10),\n",
    "        (7, 11),\n",
    "        (8, 9),\n",
    "        (3, 1),\n",
    "        (25, 12),\n",
    "        (14, 13),\n",
    "        (3, 6),\n",
    "        (22, 14),\n",
    "        (19, 15),\n",
    "        (19, 15),\n",
    "        (22, 16),\n",
    "        (22, 17),\n",
    "        (22, 18),\n",
    "        (20, 19),\n",
    "        (22, 20),\n",
    "        (5, 21),\n",
    "        (4, 22),\n",
    "        (10, 23),\n",
    "        (26, 24),\n",
    "        (17, 25),\n",
    "        (20, 26),\n",
    "        (16, 27),\n",
    "        (10, 28),\n",
    "        (19, 29),\n",
    "        (10, 30),\n",
    "        (10, 31),\n",
    "        (23, 32),\n",
    "        (22, 33),\n",
    "        (26, 34),\n",
    "        (27, 35),\n",
    "        (22, 36),\n",
    "        (27, 37),\n",
    "        (22, 38),\n",
    "        (22, 39),\n",
    "        (13, 40),\n",
    "        (14, 41),\n",
    "        (16, 27),\n",
    "        (26, 34),\n",
    "        (26, 42),\n",
    "        (27, 35),\n",
    "        (22, 36),\n",
    "        (20, 43),\n",
    "        (26, 24),\n",
    "        (22, 44),\n",
    "        (13, 45),\n",
    "        (19, 46),\n",
    "        (20, 47),\n",
    "        (16, 48),\n",
    "        (15, 49),\n",
    "        (17, 50),\n",
    "        (10, 28),\n",
    "        (20, 51),\n",
    "        (5, 52),\n",
    "        (26, 24),\n",
    "        (19, 53),\n",
    "        (15, 54),\n",
    "        (10, 55),\n",
    "        (10, 56),\n",
    "        (13, 57),\n",
    "        (13, 58),\n",
    "        (13, 59),\n",
    "        (12, 60),\n",
    "        (12, 61),\n",
    "        (18, 62),\n",
    "        (10, 63),\n",
    "        (18, 64),\n",
    "        (16, 65),\n",
    "        (20, 66),\n",
    "        (12, 67),\n",
    "        (6, 68),\n",
    "        (6, 68),\n",
    "        (15, 69),\n",
    "        (15, 70),\n",
    "        (15, 70),\n",
    "        (21, 71),\n",
    "        (30, 72),\n",
    "        (30, 73),\n",
    "        (30, 74),\n",
    "        (30, 75),\n",
    "        (23, 76),\n",
    "        (15, 77),\n",
    "        (15, 78),\n",
    "        (27, 79),\n",
    "        (27, 80),\n",
    "        (27, 81),\n",
    "        (27, 82),\n",
    "        (27, 83),\n",
    "        (27, 84),\n",
    "        (27, 79),\n",
    "        (27, 85),\n",
    "        (27, 86),\n",
    "        (10, 87),\n",
    "        (3, 88)\n",
    "    ]\n",
    "  elif problem_id == 1:\n",
    "    capacities = [0, 17, 44]\n",
    "    num_colors = 23\n",
    "    num_slabs = 30\n",
    "    orders = [\n",
    "        (4, 1),  # (size, color)\n",
    "        (22, 2),\n",
    "        (9, 3),\n",
    "        (5, 4),\n",
    "        (8, 5),\n",
    "        (3, 6),\n",
    "        (3, 4),\n",
    "        (4, 7),\n",
    "        (7, 4),\n",
    "        (7, 8),\n",
    "        (3, 6),\n",
    "        (2, 6),\n",
    "        (2, 4),\n",
    "        (8, 9),\n",
    "        (5, 10),\n",
    "        (7, 11),\n",
    "        (4, 7),\n",
    "        (7, 11),\n",
    "        (5, 10),\n",
    "        (7, 11),\n",
    "        (8, 9),\n",
    "        (3, 1),\n",
    "        (25, 12),\n",
    "        (14, 13),\n",
    "        (3, 6),\n",
    "        (22, 14),\n",
    "        (19, 15),\n",
    "        (19, 15),\n",
    "        (22, 16),\n",
    "        (22, 17),\n",
    "        (22, 18),\n",
    "        (20, 19),\n",
    "        (22, 20),\n",
    "        (5, 21),\n",
    "        (4, 22),\n",
    "        (10, 23)\n",
    "    ]\n",
    "  elif problem_id == 2:\n",
    "    capacities = [0, 17, 44]\n",
    "    num_colors = 15\n",
    "    num_slabs = 20\n",
    "    orders = [\n",
    "        (4, 1),  # (size, color)\n",
    "        (22, 2),\n",
    "        (9, 3),\n",
    "        (5, 4),\n",
    "        (8, 5),\n",
    "        (3, 6),\n",
    "        (3, 4),\n",
    "        (4, 7),\n",
    "        (7, 4),\n",
    "        (7, 8),\n",
    "        (3, 6),\n",
    "        (2, 6),\n",
    "        (2, 4),\n",
    "        (8, 9),\n",
    "        (5, 10),\n",
    "        (7, 11),\n",
    "        (4, 7),\n",
    "        (7, 11),\n",
    "        (5, 10),\n",
    "        (7, 11),\n",
    "        (8, 9),\n",
    "        (3, 1),\n",
    "        (25, 12),\n",
    "        (14, 13),\n",
    "        (3, 6),\n",
    "        (22, 14),\n",
    "        (19, 15),\n",
    "        (19, 15)\n",
    "    ]\n",
    "\n",
    "  elif problem_id == 3:\n",
    "    capacities = [0, 17, 44]\n",
    "    num_colors = 8\n",
    "    num_slabs = 10\n",
    "    orders = [\n",
    "        (4, 1),  # (size, color)\n",
    "        (22, 2),\n",
    "        (9, 3),\n",
    "        (5, 4),\n",
    "        (8, 5),\n",
    "        (3, 6),\n",
    "        (3, 4),\n",
    "        (4, 7),\n",
    "        (7, 4),\n",
    "        (7, 8),\n",
    "        (3, 6)\n",
    "    ]\n",
    "\n",
    "  return (num_slabs, capacities, num_colors, orders)\n",
    "\n",
    "class SteelMillSlabSolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
    "  \"\"\"Print intermediate solutions.\"\"\"\n",
    "\n",
    "  def __init__(self, orders, assign, load, loss):\n",
    "    cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "    self.__orders = orders\n",
    "    self.__assign = assign\n",
    "    self.__load = load\n",
    "    self.__loss = loss\n",
    "    self.__solution_count = 0\n",
    "    self.__all_orders = range(len(orders))\n",
    "    self.__all_slabs = range(len(assign[0]))\n",
    "    self.__start_time = time.time()\n",
    "\n",
    "  def OnSolutionCallback(self):\n",
    "    current_time = time.time()\n",
    "    objective = sum(self.Value(l) for l in self.__loss)\n",
    "    print('Solution %i, time = %f s, objective = %i' %\n",
    "          (self.__solution_count, current_time - self.__start_time, objective))\n",
    "    self.__solution_count += 1\n",
    "    orders_in_slab = [[\n",
    "        o for o in self.__all_orders if self.Value(self.__assign[o][s])\n",
    "    ] for s in self.__all_slabs]\n",
    "    for s in self.__all_slabs:\n",
    "      if orders_in_slab[s]:\n",
    "        line = '  - slab %i, load = %i, loss = %i, orders = [' % (\n",
    "            s, self.Value(self.__load[s]), self.Value(self.__loss[s]))\n",
    "        for o in orders_in_slab[s]:\n",
    "          line += '#%i(w%i, c%i) ' % (o, self.__orders[o][0],\n",
    "                                      self.__orders[o][1])\n",
    "        line += ']'\n",
    "        print(line)\n",
    "\n",
    "class SolutionPrinterWithObjective(cp_model.CpSolverSolutionCallback):\n",
    "  \"\"\"Print intermediate solutions.\"\"\"\n",
    "\n",
    "  def __init__(self):\n",
    "    cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "    self.__solution_count = 0\n",
    "    self.__start_time = time.time()\n",
    "\n",
    "  def OnSolutionCallback(self):\n",
    "    current_time = time.time()\n",
    "    print('Solution %i, time = %f s, objective = %i' %\n",
    "          (self.__solution_count, current_time - self.__start_time,\n",
    "           self.ObjectiveValue()))\n",
    "    self.__solution_count += 1\n",
    "\n",
    "def SteelMillSlab(problem, break_symmetries, output_proto):\n",
    "  \"\"\"Solves the Steel Mill Slab Problem.\"\"\"\n",
    "  ### Load problem.\n",
    "  (num_slabs, capacities, num_colors, orders) = BuildProblem(problem)\n",
    "\n",
    "  num_orders = len(orders)\n",
    "  num_capacities = len(capacities)\n",
    "  all_slabs = range(num_slabs)\n",
    "  all_colors = range(num_colors)\n",
    "  all_orders = range(len(orders))\n",
    "  print('Solving steel mill with %i orders, %i slabs, and %i capacities' %\n",
    "        (num_orders, num_slabs, num_capacities - 1))\n",
    "\n",
    "  # Compute auxilliary data.\n",
    "  widths = [x[0] for x in orders]\n",
    "  colors = [x[1] for x in orders]\n",
    "  max_capacity = max(capacities)\n",
    "  loss_array = [\n",
    "      min(x for x in capacities if x >= c) - c for c in range(max_capacity + 1)\n",
    "  ]\n",
    "  max_loss = max(loss_array)\n",
    "  orders_per_color = [\n",
    "      [o for o in all_orders if colors[o] == c + 1] for c in all_colors\n",
    "  ]\n",
    "  unique_color_orders = [\n",
    "      o for o in all_orders if len(orders_per_color[colors[o] - 1]) == 1\n",
    "  ]\n",
    "\n",
    "  ### Model problem.\n",
    "\n",
    "  # Create the model and the decision variables.\n",
    "  model = cp_model.CpModel()\n",
    "  assign = [[\n",
    "      model.NewBoolVar('assign_%i_to_slab_%i' % (o, s)) for s in all_slabs\n",
    "  ] for o in all_orders]\n",
    "  loads = [\n",
    "      model.NewIntVar(0, max_capacity, 'load_of_slab_%i' % s) for s in all_slabs\n",
    "  ]\n",
    "  color_is_in_slab = [[\n",
    "      model.NewBoolVar('color_%i_in_slab_%i' % (c + 1, s)) for c in all_colors\n",
    "  ] for s in all_slabs]\n",
    "\n",
    "  # Compute load of all slabs.\n",
    "  for s in all_slabs:\n",
    "    model.Add(sum(assign[o][s] * widths[o] for o in all_orders) == loads[s])\n",
    "\n",
    "  # Orders are assigned to one slab.\n",
    "  for o in all_orders:\n",
    "    model.Add(sum(assign[o]) == 1)\n",
    "\n",
    "  # Redundant constraint (sum of loads == sum of widths).\n",
    "  model.Add(sum(loads) == sum(widths))\n",
    "\n",
    "  # Link present_colors and assign.\n",
    "  for c in all_colors:\n",
    "    for s in all_slabs:\n",
    "      for o in orders_per_color[c]:\n",
    "        model.AddImplication(assign[o][s], color_is_in_slab[s][c])\n",
    "        model.AddImplication(color_is_in_slab[s][c].Not(), assign[o][s].Not())\n",
    "\n",
    "  # At most two colors per slab.\n",
    "  for s in all_slabs:\n",
    "    model.Add(sum(color_is_in_slab[s]) <= 2)\n",
    "\n",
    "  # Project previous constraint on unique_color_orders\n",
    "  for s in all_slabs:\n",
    "    model.Add(sum(assign[o][s] for o in unique_color_orders) <= 2)\n",
    "\n",
    "  # Symmetry breaking.\n",
    "  for s in range(num_slabs - 1):\n",
    "    model.Add(loads[s] >= loads[s + 1])\n",
    "\n",
    "  # Collect equivalent orders.\n",
    "  width_to_unique_color_order = {}\n",
    "  ordered_equivalent_orders = []\n",
    "  for c in all_colors:\n",
    "    colored_orders = orders_per_color[c]\n",
    "    if not colored_orders:\n",
    "      continue\n",
    "    if len(colored_orders) == 1:\n",
    "      o = colored_orders[0]\n",
    "      w = widths[o]\n",
    "      if w not in width_to_unique_color_order:\n",
    "        width_to_unique_color_order[w] = [o]\n",
    "      else:\n",
    "        width_to_unique_color_order[w].append(o)\n",
    "    else:\n",
    "      local_width_to_order = {}\n",
    "      for o in colored_orders:\n",
    "        w = widths[o]\n",
    "        if w not in local_width_to_order:\n",
    "          local_width_to_order[w] = []\n",
    "        local_width_to_order[w].append(o)\n",
    "      for w, os in local_width_to_order.items():\n",
    "        if len(os) > 1:\n",
    "          for p in range(len(os) - 1):\n",
    "            ordered_equivalent_orders.append((os[p], os[p + 1]))\n",
    "  for w, os in width_to_unique_color_order.items():\n",
    "    if len(os) > 1:\n",
    "      for p in range(len(os) - 1):\n",
    "        ordered_equivalent_orders.append((os[p], os[p + 1]))\n",
    "\n",
    "  # Create position variables if there are symmetries to be broken.\n",
    "  if break_symmetries and ordered_equivalent_orders:\n",
    "    print('  - creating %i symmetry breaking constraints' %\n",
    "          len(ordered_equivalent_orders))\n",
    "    positions = {}\n",
    "    for p in ordered_equivalent_orders:\n",
    "      if p[0] not in positions:\n",
    "        positions[p[0]] = model.NewIntVar(0, num_slabs - 1,\n",
    "                                          'position_of_slab_%i' % p[0])\n",
    "        model.AddMapDomain(positions[p[0]], assign[p[0]])\n",
    "      if p[1] not in positions:\n",
    "        positions[p[1]] = model.NewIntVar(0, num_slabs - 1,\n",
    "                                          'position_of_slab_%i' % p[1])\n",
    "        model.AddMapDomain(positions[p[1]], assign[p[1]])\n",
    "      # Finally add the symmetry breaking constraint.\n",
    "      model.Add(positions[p[0]] <= positions[p[1]])\n",
    "\n",
    "  # Objective.\n",
    "  obj = model.NewIntVar(0, num_slabs * max_loss, 'obj')\n",
    "  losses = [model.NewIntVar(0, max_loss, 'loss_%i' % s) for s in all_slabs]\n",
    "  for s in all_slabs:\n",
    "    model.AddElement(loads[s], loss_array, losses[s])\n",
    "  model.Add(obj == sum(losses))\n",
    "  model.Minimize(obj)\n",
    "\n",
    "  ### Solve model.\n",
    "  solver = cp_model.CpSolver()\n",
    "  status = solver.Solve(model)\n",
    "\n",
    "  ### Output the solution.\n",
    "  if status == cp_model.OPTIMAL:\n",
    "    print('Loss = %i, time = %f s, %i conflicts' %\n",
    "          (solver.ObjectiveValue(), solver.WallTime(), solver.NumConflicts()))\n",
    "  else:\n",
    "    print('No solution')\n",
    "\n",
    "class AllSolutionsCollector(cp_model.CpSolverSolutionCallback):\n",
    "  \"\"\"Collect all solutions callback.\"\"\"\n",
    "\n",
    "  def __init__(self, variables):\n",
    "    cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "    self.__solutions = []\n",
    "    self.__variables = variables\n",
    "\n",
    "  def OnSolutionCallback(self):\n",
    "    solution = [self.Value(v) for v in self.__variables]\n",
    "    self.__solutions.append(tuple(solution))\n",
    "\n",
    "  def AllSolutions(self):\n",
    "    return self.__solutions\n",
    "\n",
    "def CollectValidSlabs(capacities, colors, widths, loss_array, all_colors):\n",
    "  \"\"\"Collect valid columns (assign, loss) for one slab.\"\"\"\n",
    "  max_capacity = max(capacities)\n",
    "  all_orders = range(len(colors))\n",
    "  orders_per_color = [\n",
    "      [o for o in all_orders if colors[o] == c + 1] for c in all_colors\n",
    "  ]\n",
    "\n",
    "  model = cp_model.CpModel()\n",
    "  assign = [model.NewBoolVar('assign_%i' % o) for o in all_orders]\n",
    "  load = model.NewIntVar(0, max_capacity, 'load')\n",
    "\n",
    "  color_in_slab = [model.NewBoolVar('color_%i' % (c + 1)) for c in all_colors]\n",
    "\n",
    "  # Compute load.\n",
    "  model.Add(sum(assign[o] * widths[o] for o in all_orders) == load)\n",
    "\n",
    "  # Link present_colors and assign.\n",
    "  for c in all_colors:\n",
    "    for o in orders_per_color[c]:\n",
    "      model.AddImplication(assign[o], color_in_slab[c])\n",
    "      model.AddImplication(color_in_slab[c].Not(), assign[o].Not())\n",
    "    model.AddBoolOr([color_in_slab[c].Not()] +\n",
    "                    [assign[o] for o in orders_per_color[c]])\n",
    "\n",
    "  # At most two colors per slab.\n",
    "  model.Add(sum(color_in_slab) <= 2)\n",
    "\n",
    "  # Compute loss.\n",
    "  loss = model.NewIntVar(0, max(loss_array), 'loss')\n",
    "  model.AddElement(load, loss_array, loss)\n",
    "\n",
    "  ### Solve model and collect columns.\n",
    "  print('Collect Valid Slabs...DONE')\n",
    "  solver = cp_model.CpSolver()\n",
    "  collector = AllSolutionsCollector(assign + [loss, load])\n",
    "  solver.SearchForAllSolutions(model, collector)\n",
    "  print('Collect Valid Slabs...DONE')\n",
    "  return collector.AllSolutions()\n",
    "\n",
    "def SteelMillSlabWithValidSlabs(problem, break_symmetries, output_proto):\n",
    "  \"\"\"Solves the Steel Mill Slab Problem.\"\"\"\n",
    "  ### Load problem.\n",
    "  (num_slabs, capacities, num_colors, orders) = BuildProblem(problem)\n",
    "\n",
    "  num_orders = len(orders)\n",
    "  num_capacities = len(capacities)\n",
    "  all_slabs = range(num_slabs)\n",
    "  all_colors = range(num_colors)\n",
    "  all_orders = range(len(orders))\n",
    "  print('Solving steel mill with %i orders, %i slabs, and %i capacities' %\n",
    "        (num_orders, num_slabs, num_capacities - 1))\n",
    "\n",
    "  # Compute auxilliary data.\n",
    "  widths = [x[0] for x in orders]\n",
    "  colors = [x[1] for x in orders]\n",
    "  max_capacity = max(capacities)\n",
    "  loss_array = [\n",
    "      min(x for x in capacities if x >= c) - c for c in range(max_capacity + 1)\n",
    "  ]\n",
    "  max_loss = max(loss_array)\n",
    "\n",
    "  ### Model problem.\n",
    "\n",
    "  # Create the model and the decision variables.\n",
    "  model = cp_model.CpModel()\n",
    "  assign = [[\n",
    "      model.NewBoolVar('assign_%i_to_slab_%i' % (o, s)) for s in all_slabs\n",
    "  ] for o in all_orders]\n",
    "  loads = [model.NewIntVar(0, max_capacity, 'load_%i' % s) for s in all_slabs]\n",
    "  losses = [model.NewIntVar(0, max_loss, 'loss_%i' % s) for s in all_slabs]\n",
    "\n",
    "  unsorted_valid_slabs = CollectValidSlabs(capacities, colors, widths,\n",
    "                                           loss_array, all_colors)\n",
    "  # Sort slab by descending load/loss. Remove duplicates.\n",
    "  valid_slabs = sorted(unsorted_valid_slabs, key=lambda c: 1000 * c[-1] + c[-2])\n",
    "  num_valid_slabs = len(valid_slabs)\n",
    "  print('  - %i valid slab combinations' % num_valid_slabs)\n",
    "\n",
    "  for s in all_slabs:\n",
    "    model.AddAllowedAssignments(\n",
    "        [assign[o][s] for o in all_orders] + [losses[s], loads[s]], valid_slabs)\n",
    "\n",
    "  # Orders are assigned to one slab.\n",
    "  for o in all_orders:\n",
    "    model.Add(sum(assign[o]) == 1)\n",
    "\n",
    "  # Redundant constraint (sum of loads == sum of widths).\n",
    "  model.Add(sum(loads) == sum(widths))\n",
    "\n",
    "  # Symmetry breaking.\n",
    "  for s in range(num_slabs - 1):\n",
    "    model.Add(loads[s] >= loads[s + 1])\n",
    "\n",
    "  # Collect equivalent orders.\n",
    "  if break_symmetries:\n",
    "    print('Breaking symmetries')\n",
    "    width_to_unique_color_order = {}\n",
    "    ordered_equivalent_orders = []\n",
    "    orders_per_color = [\n",
    "        [o for o in all_orders if colors[o] == c + 1] for c in all_colors\n",
    "    ]\n",
    "    for c in all_colors:\n",
    "      colored_orders = orders_per_color[c]\n",
    "      if not colored_orders:\n",
    "        continue\n",
    "      if len(colored_orders) == 1:\n",
    "        o = colored_orders[0]\n",
    "        w = widths[o]\n",
    "        if w not in width_to_unique_color_order:\n",
    "          width_to_unique_color_order[w] = [o]\n",
    "        else:\n",
    "          width_to_unique_color_order[w].append(o)\n",
    "      else:\n",
    "        local_width_to_order = {}\n",
    "        for o in colored_orders:\n",
    "          w = widths[o]\n",
    "          if w not in local_width_to_order:\n",
    "            local_width_to_order[w] = []\n",
    "            local_width_to_order[w].append(o)\n",
    "        for w, os in local_width_to_order.items():\n",
    "          if len(os) > 1:\n",
    "            for p in range(len(os) - 1):\n",
    "              ordered_equivalent_orders.append((os[p], os[p + 1]))\n",
    "    for w, os in width_to_unique_color_order.items():\n",
    "      if len(os) > 1:\n",
    "        for p in range(len(os) - 1):\n",
    "          ordered_equivalent_orders.append((os[p], os[p + 1]))\n",
    "\n",
    "    # Create position variables if there are symmetries to be broken.\n",
    "    if ordered_equivalent_orders:\n",
    "      print('  - creating %i symmetry breaking constraints' %\n",
    "            len(ordered_equivalent_orders))\n",
    "      positions = {}\n",
    "      for p in ordered_equivalent_orders:\n",
    "        if p[0] not in positions:\n",
    "          positions[p[0]] = model.NewIntVar(0, num_slabs - 1,\n",
    "                                            'position_of_slab_%i' % p[0])\n",
    "          model.AddMapDomain(positions[p[0]], assign[p[0]])\n",
    "        if p[1] not in positions:\n",
    "          positions[p[1]] = model.NewIntVar(0, num_slabs - 1,\n",
    "                                            'position_of_slab_%i' % p[1])\n",
    "          model.AddMapDomain(positions[p[1]], assign[p[1]])\n",
    "          # Finally add the symmetry breaking constraint.\n",
    "        model.Add(positions[p[0]] <= positions[p[1]])\n",
    "\n",
    "  # Objective.\n",
    "  obj = model.NewIntVar(0, num_slabs * max_loss, 'obj')\n",
    "  model.Add(obj == sum(losses))\n",
    "  model.Minimize(obj)\n",
    "\n",
    "  print('Model created')\n",
    "\n",
    "  # Output model proto to file.\n",
    "  if output_proto:\n",
    "    f = open(output_proto, 'w')\n",
    "    f.write(str(model.ModelProto()))\n",
    "    f.close()\n",
    "\n",
    "  ### Solve model.\n",
    "  solver = cp_model.CpSolver()\n",
    "  solution_printer = SteelMillSlabSolutionPrinter(orders, assign, loads, losses)\n",
    "  status = solver.SolveWithSolutionCallback(model, solution_printer)\n",
    "\n",
    "  ### Output the solution.\n",
    "  if status == cp_model.OPTIMAL:\n",
    "    print('Loss = %i, time = %f s, %i conflicts' %\n",
    "          (solver.ObjectiveValue(), solver.WallTime(), solver.NumConflicts()))\n",
    "  else:\n",
    "    print('No solution')\n",
    "\n",
    "def SteelMillSlabWithColumnGeneration(problem, output_proto):\n",
    "  \"\"\"Solves the Steel Mill Slab Problem.\"\"\"\n",
    "  ### Load problem.\n",
    "  (num_slabs, capacities, num_colors, orders) = BuildProblem(problem)\n",
    "\n",
    "  num_orders = len(orders)\n",
    "  num_capacities = len(capacities)\n",
    "  all_slabs = range(num_slabs)\n",
    "  all_colors = range(num_colors)\n",
    "  all_orders = range(len(orders))\n",
    "  print('Solving steel mill with %i orders, %i slabs, and %i capacities' %\n",
    "        (num_orders, num_slabs, num_capacities - 1))\n",
    "\n",
    "  # Compute auxilliary data.\n",
    "  widths = [x[0] for x in orders]\n",
    "  colors = [x[1] for x in orders]\n",
    "  max_capacity = max(capacities)\n",
    "  loss_array = [\n",
    "      min(x for x in capacities if x >= c) - c for c in range(max_capacity + 1)\n",
    "  ]\n",
    "\n",
    "  ### Model problem.\n",
    "\n",
    "  # Generate all valid slabs (columns)\n",
    "  unsorted_valid_slabs = CollectValidSlabs(capacities, colors, widths,\n",
    "                                           loss_array, all_colors)\n",
    "  # Sort slab by descending load/loss. Remove duplicates.\n",
    "  valid_slabs = sorted(unsorted_valid_slabs, key=lambda c: 1000 * c[-1] + c[-2])\n",
    "  num_valid_slabs = len(valid_slabs)\n",
    "  all_valid_slabs = range(num_valid_slabs)\n",
    "  print('  - %i valid slab combinations' % num_valid_slabs)\n",
    "\n",
    "  # create model and decision variables.\n",
    "  model = cp_model.CpModel()\n",
    "  selected = [model.NewBoolVar('selected_%i' % i) for i in all_valid_slabs]\n",
    "\n",
    "  for o in all_orders:\n",
    "    model.Add(\n",
    "        sum(selected[i] for i in all_valid_slabs if valid_slabs[i][o]) == 1)\n",
    "\n",
    "  # Redundant constraint (sum of loads == sum of widths).\n",
    "  model.Add(\n",
    "      sum(selected[i] * valid_slabs[i][-1]\n",
    "          for i in all_valid_slabs) == sum(widths))\n",
    "\n",
    "  # Objective.\n",
    "  max_loss = max(valid_slabs[i][-2] for i in all_valid_slabs)\n",
    "  obj = model.NewIntVar(0, num_slabs * max_loss, 'obj')\n",
    "  model.Add(obj == sum(\n",
    "      selected[i] * valid_slabs[i][-2] for i in all_valid_slabs))\n",
    "  model.Minimize(obj)\n",
    "\n",
    "  print('Model created')\n",
    "\n",
    "  # Output model proto to file.\n",
    "  if output_proto:\n",
    "    f = open(output_proto, 'w')\n",
    "    f.write(str(model.ModelProto()))\n",
    "    f.close()\n",
    "\n",
    "  ### Solve model.\n",
    "  solver = cp_model.CpSolver()\n",
    "  solution_printer = SolutionPrinterWithObjective()\n",
    "  status = solver.SolveWithSolutionCallback(model, solution_printer)\n",
    "\n",
    "  ### Output the solution.\n",
    "  if status == cp_model.OPTIMAL:\n",
    "    print('Loss = %i, time = %f s, %i conflicts' %\n",
    "          (solver.ObjectiveValue(), solver.WallTime(), solver.NumConflicts()))\n",
    "  else:\n",
    "    print('No solution')\n",
    "\n",
    "def SteelMillSlabWithMipColumnGeneration(problem):\n",
    "  \"\"\"Solves the Steel Mill Slab Problem.\"\"\"\n",
    "  ### Load problem.\n",
    "  (num_slabs, capacities, num_colors, orders) = BuildProblem(problem)\n",
    "\n",
    "  num_orders = len(orders)\n",
    "  num_capacities = len(capacities)\n",
    "  all_slabs = range(num_slabs)\n",
    "  all_colors = range(num_colors)\n",
    "  all_orders = range(len(orders))\n",
    "  print('Solving steel mill with %i orders, %i slabs, and %i capacities' %\n",
    "        (num_orders, num_slabs, num_capacities - 1))\n",
    "\n",
    "  # Compute auxilliary data.\n",
    "  widths = [x[0] for x in orders]\n",
    "  colors = [x[1] for x in orders]\n",
    "  max_capacity = max(capacities)\n",
    "  loss_array = [\n",
    "      min(x for x in capacities if x >= c) - c for c in range(max_capacity + 1)\n",
    "  ]\n",
    "\n",
    "  ### Model problem.\n",
    "\n",
    "  # Generate all valid slabs (columns)\n",
    "  start = time.time()\n",
    "  unsorted_valid_slabs = CollectValidSlabs(capacities, colors, widths,\n",
    "                                           loss_array, all_colors)\n",
    "  # Sort slab by descending load/loss. Remove duplicates.\n",
    "  valid_slabs = sorted(unsorted_valid_slabs, key=lambda c: 1000 * c[-1] + c[-2])\n",
    "  num_valid_slabs = len(valid_slabs)\n",
    "  all_valid_slabs = range(num_valid_slabs)\n",
    "  generate = time.time()\n",
    "  print('  - %i valid slab combinations generated in %f s' % (num_valid_slabs,\n",
    "                                                              generate - start))\n",
    "\n",
    "  # create model and decision variables.\n",
    "  solver = pywraplp.Solver('Steel', pywraplp.Solver.BOP_INTEGER_PROGRAMMING)\n",
    "  selected = [\n",
    "      solver.IntVar(0.0, 1.0, 'selected_%i' % i) for i in all_valid_slabs\n",
    "  ]\n",
    "\n",
    "  for order in all_orders:\n",
    "    solver.Add(\n",
    "        sum(selected[i] for i in all_valid_slabs if valid_slabs[i][order]) == 1)\n",
    "\n",
    "  # Redundant constraint (sum of loads == sum of widths).\n",
    "  solver.Add(\n",
    "      sum(selected[i] * valid_slabs[i][-1]\n",
    "          for i in all_valid_slabs) == sum(widths))\n",
    "\n",
    "  # Objective.\n",
    "  solver.Minimize(\n",
    "      sum(selected[i] * valid_slabs[i][-2] for i in all_valid_slabs))\n",
    "\n",
    "  status = solver.Solve()\n",
    "\n",
    "  ### Output the solution.\n",
    "  if status == pywraplp.Solver.OPTIMAL:\n",
    "    print('Objective value = %f found in %f s' % (solver.Objective().Value(),\n",
    "                                                  time.time() - generate))\n",
    "  else:\n",
    "    print('No solution')\n",
    "\n",
    "'''Main function'''\n",
    "if args.solver == 'sat':\n",
    "  SteelMillSlab(args.problem, args.break_symmetries, args.output_proto)\n",
    "elif args.solver == 'sat_table':\n",
    "  SteelMillSlabWithValidSlabs(args.problem, args.break_symmetries,\n",
    "                              args.output_proto)\n",
    "elif args.solver == 'sat_column':\n",
    "  SteelMillSlabWithColumnGeneration(args.problem, args.output_proto)\n",
    "else:  # 'mip_column'\n",
    "  SteelMillSlabWithMipColumnGeneration(args.problem)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}