Objective-CP

The Objective-CP platform consist of a collection of libraries useful for solving combinatorial optimization problems. In particular, it offers a technology independent modeling library where models are first class objects. It also provides interfaces to concrete solvers such as MIP or CP. Its CP solver is brand new and based on a microkernel architecture.

Implementation

The platform is implemented in Objective-C, an object-oriented descendant of Smalltalk that builds upon a pure C language core. Its object-oriented capabilities are all offered through a runtime library and the language is therefore 100% compatible with pure C.

In addition, Apple recently (June 2015) announced that its new flagship language (Swift) was going to be open-sourced in Fall’15. Swift is completely backward compatible with Objective-C, yet it offers a modern syntax with many amenities that programmers love. In particular, it supports operator overloading which allows us to write truly elegant models that rivals with Algebraic Modeling Language in term of their elegance.

Microkernel

The Objective-CP solver is based on a microkernel architecture. This page provides links to the benchmarks that were used to evaluate the performance of the solver. In particular, it provides COMET, Choco 3.3.1 and Objective-CP source source for the models, including the search procedures.

License

Mozilla Public License

Copyright © 2015 NICTA, Laurent Michel and Pascal Van Hentenryck

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

Examples in Swift

A model for the 8-queens

This is a simple example showing the library accessed from Swift.

import ORProgram
 
autoreleasepool {
   let n : ORInt = 8
   let model = ORFactory.createModel()
   let R     = ORFactory.intRange(model, low: 0, up: n - 1)
   let x     = ORFactory.intVarArray(model, range: R, domain: R)
   for  i : ORInt in 0..<n  {
      for j : ORInt in i+1..<n {
         model.add(x[i] != x[j])
         model.add(x[i] != x[j] + (i-j))
         model.add(x[i] != x[j] + (j-i))
      }
   }
   let cp = ORFactory.createCPProgram(model)
   cp.search {
      firstFail(cp, x)
   }
   println("Number of solutions: \(cp.solutionPool().count())")
}

Magic series

This second example illustrate more complex algebraic equations and aggregates in particular. It still follows the classic model with redundant constraints

import ORProgram
 
autoreleasepool {
   println("magicSerie in swift!")
   let n : ORInt = 14
   let m = ORFactory.createModel()
   let R = range(m,0...n-1)
   let x = ORFactory.intVarArray(m, range: R, domain: R)
   for i in 0..<n {
      m.add(sum(m, R) {k in x[k] == i} == x[i])
   }
   m.add(sum(m,R) {i in x[i] * i    } == n)
   m.add(sum(m,R) {i in x[i] * (i-1)} == 0)
    
   let cp = ORFactory.createCPProgram(m)
   cp.search { firstFail(cp, x) }
   println("Number of solutions: \(cp.solutionPool().count())")
   if let sol = cp.solutionPool().best() {
      let z = [ORInt](0..<n).map { k in sol.intValue(x[k])}
      println("Solution is: " + z.description)
   }
   ORFactory.shutdown()
}

Example in Objective-C

For completeness sake, here is the same n-queens in native Objective-C

#import <ORProgram/ORProgram.h>
#import "ORCmdLineArgs.h"
 
int main (int argc, const char * argv[])
{
   @autoreleasepool {
      ORCmdLineArgs* args = [ORCmdLineArgs newWith:argc argv:argv];
      [args measure:^struct ORResult(){
         int n = [args size];
         id<ORModel> model = [ORFactory createModel];
         id<ORIntRange> R = RANGE(model,0,n-1);
         id<ORMutableInteger> nbSol = INTEGER(model,0);
         id<ORIntVarArray> x = [ORFactory intVarArray:model range:R domain: R];
         for(ORUInt i =0;i < n; i++) {
            for(ORUInt j=i+1;j< n;j++) {
               [model add: [x[i] neq: x[j]]];
               [model add: [x[i] neq: [x[j] plus: @(i-j)]]];
               [model add: [x[i] neq: [x[j] plus: @(j-i)]]];
            }
         }
         id<CPProgram> cp = [ORFactory createCPProgram: model];
         [cp clearOnSolution]; // If one does not wish to save solutions
         [cp solveAll: ^{
            [cp labelArrayFF: x];
            [nbSol incr:cp];
         }];
         printf("GOT %d solutions\n",[nbSol intValue:cp]);
         NSLog(@"Solver status: %@\n",cp);
         struct ORResult r = REPORT([nbSol intValue:cp], 
                                    [cp.explorer nbFailures], 
                                    [cp.explorer nbChoices], 
                                    [cp.engine nbPropagation]);
         [ORFactory shutdown];
         return r;
      }];      
   }
   return 0;
}