1 // 2 // Copyright 2012 Hakan Kjellerstrand 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 16 using System; 17 using System.Collections; 18 using System.IO; 19 using System.Linq; 20 using System.Text.RegularExpressions; 21 using Google.OrTools.ConstraintSolver; 22 23 public class SchedulingSpeakers 24 { 25 /** 26 * 27 * Scheduling speakers problem 28 * 29 * From Rina Dechter, Constraint Processing, page 72 30 * Scheduling of 6 speakers in 6 slots. 31 * 32 * See http://www.hakank.org/google_or_tools/scheduling_speakers.py 33 * 34 */ Solve()35 private static void Solve() 36 { 37 Solver solver = new Solver("SchedulingSpeakers"); 38 39 // number of speakers 40 int n = 6; 41 42 // slots available to speak 43 int[][] available = { 44 // Reasoning: 45 new int[] { 3, 4, 5, 6 }, // 2) the only one with 6 after speaker F -> 1 46 new int[] { 3, 4 }, // 5) 3 or 4 47 new int[] { 2, 3, 4, 5 }, // 3) only with 5 after F -> 1 and A -> 6 48 new int[] { 2, 3, 4 }, // 4) only with 2 after C -> 5 and F -> 1 49 new int[] { 3, 4 }, // 5) 3 or 4 50 new int[] { 1, 2, 3, 4, 5, 6 } // 1) the only with 1 51 }; 52 53 // 54 // Decision variables 55 // 56 IntVar[] x = solver.MakeIntVarArray(n, 1, n, "x"); 57 58 // 59 // Constraints 60 // 61 solver.Add(x.AllDifferent()); 62 63 for (int i = 0; i < n; i++) 64 { 65 solver.Add(x[i].Member(available[i])); 66 } 67 68 // 69 // Search 70 // 71 DecisionBuilder db = solver.MakePhase(x, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); 72 73 solver.NewSearch(db); 74 75 while (solver.NextSolution()) 76 { 77 Console.WriteLine(string.Join(",", (from i in x select i.Value()))); 78 } 79 80 Console.WriteLine("\nSolutions: {0}", solver.Solutions()); 81 Console.WriteLine("WallTime: {0}ms", solver.WallTime()); 82 Console.WriteLine("Failures: {0}", solver.Failures()); 83 Console.WriteLine("Branches: {0} ", solver.Branches()); 84 85 solver.EndSearch(); 86 } 87 Main(String[] args)88 public static void Main(String[] args) 89 { 90 Solve(); 91 } 92 } 93