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