1 // Copyright 2011 Hakan Kjellerstrand hakank@gmail.com 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 package com.google.ortools.contrib; 14 15 import com.google.ortools.Loader; 16 import com.google.ortools.constraintsolver.DecisionBuilder; 17 import com.google.ortools.constraintsolver.IntVar; 18 import com.google.ortools.constraintsolver.OptimizeVar; 19 import com.google.ortools.constraintsolver.Solver; 20 import java.io.*; 21 import java.text.*; 22 import java.util.*; 23 24 public class SetCovering2 { 25 /** Solves a set covering problem. See http://www.hakank.org/google_or_tools/set_covering2.py */ solve()26 private static void solve() { 27 Solver solver = new Solver("SetCovering2"); 28 29 // 30 // data 31 // 32 33 // Example 9.1-2 from 34 // Taha "Operations Research - An Introduction", 35 // page 354ff. 36 // Minimize the number of security telephones in street 37 // corners on a campus. 38 39 int n = 8; // maximum number of corners 40 int num_streets = 11; // number of connected streets 41 42 // corners of each street 43 // Note: 1-based (handled below) 44 int[][] corner = { 45 {1, 2}, {2, 3}, {4, 5}, {7, 8}, {6, 7}, {2, 6}, {1, 6}, {4, 7}, {2, 4}, {5, 8}, {3, 5}}; 46 47 // 48 // variables 49 // 50 IntVar[] x = solver.makeIntVarArray(n, 0, 1, "x"); 51 52 // number of telephones, to be minimize 53 IntVar z = solver.makeSum(x).var(); 54 55 // 56 // constraints 57 // 58 59 // ensure that all cities are covered 60 for (int i = 0; i < num_streets; i++) { 61 IntVar[] b = new IntVar[2]; 62 b[0] = x[corner[i][0] - 1]; 63 b[1] = x[corner[i][1] - 1]; 64 solver.addConstraint(solver.makeSumGreaterOrEqual(b, 1)); 65 } 66 67 // 68 // objective 69 // 70 OptimizeVar objective = solver.makeMinimize(z, 1); 71 72 // 73 // search 74 // 75 DecisionBuilder db = solver.makePhase(x, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT); 76 solver.newSearch(db, objective); 77 78 // 79 // output 80 // 81 while (solver.nextSolution()) { 82 System.out.println("z: " + z.value()); 83 System.out.print("x: "); 84 for (int i = 0; i < n; i++) { 85 System.out.print(x[i].value() + " "); 86 } 87 System.out.println(); 88 } 89 solver.endSearch(); 90 91 // Statistics 92 System.out.println(); 93 System.out.println("Solutions: " + solver.solutions()); 94 System.out.println("Failures: " + solver.failures()); 95 System.out.println("Branches: " + solver.branches()); 96 System.out.println("Wall time: " + solver.wallTime() + "ms"); 97 } 98 main(String[] args)99 public static void main(String[] args) throws Exception { 100 Loader.loadNativeLibraries(); 101 SetCovering2.solve(); 102 } 103 } 104