ISSE

Search

MiniBrass - Constraint Relationships

Logo

Many combinatorial optimization problems are conveniently expressed using a constraint-based modeling language. They are then solved by powerful constraint programming or mathematical programming solvers.

We provide support for over-constrained problems or problems where desirable properties can be modeled as optional (soft) constraints. Importance is expressed only by means of relations between constraints (see this 1 slide to get an idea). Our library extensions are built on top of MiniZinc that facilitates modeling combinatorial optimization problems for various solvers. The library includes:

Consider our GitHub project page for more information.

Quick Example

First, we define variables, domains, and conventional hard constraints
include "classic_o.mzn"% output of minibrass 
include "soft_constraints/pvs_gen_search.mzn"
 
% the basic, "classic" CSP 
set of int: DOM = 1..3; 
 
var DOM: x; var DOM: y; var DOM: z; 
 
solve 
:: int_search([x,y,z], input_order, indomain_min, complete) 
search pvs_BAB(); 
 
output ["x = \(x); y = \(y); z = \(z)"] ++ 
       [ "\nValuations:  overall = \(topLevelObjective)\n"];
to then go on and define our preference model
include "defs.mbr"
 
PVS: cr1 = new ConstraintPreferences("cr1") { 
   soft-constraint c1: 'x + 1 = y'
   soft-constraint c2: 'z = y + 2'
   soft-constraint c3: 'x + y <= 3'
 
   crEdges : '[| mbr.c2, mbr.c1 | mbr.c3, mbr.c1 |]'
   useSPD: 'false' ; 
}; 
 
solve cr1;

Download and Installation

Quickest start (only requires MiniBrass and MiniZinc):
  1. Download and install the newest MiniZinc IDE version from http://www.minizinc.org/
  2. Download mbr2mzn.jar
  3. Download soft-constraints.zip and unpack it
  4. Locate the directory "./share/minizinc/std" of your MiniZinc installation
  5. Copy the directory "soft_constraints" into "./share/minizinc/std"
  6. Download and extract the code examples
  7. Compile the preference model by using java -jar mbr2mzn.jar -m smallexample_minizinc.mbr
  8. Run minizinc smallexample_minizinc.mzn : Your output should state
    x = 1; y = 2; z = 1
    Valuations:  overall = 1
    ----------
    ==========
    
Slightly slower start (requires MiniBrass, MiniZinc and MiniSearch):
  1. Build MiniSearch according to the instructions at MiniSearch
  2. Download mbr2mzn.jar
  3. Download soft-constraints.zip and unpack it
  4. Locate the directory "./share/minizinc/std" of your MiniSearch installation
  5. Copy the directory "soft_constraints" into "./share/minizinc/std"
  6. Download and extract the code examples
  7. Compile the preference model by using java -jar mbr2mzn.jar smallexample_minisearch.mbr
  8. Run minisearch smallexample_minisearch.mzn : Your output should state
    Intermediate solution:x = 1; y = 1; z = 1
    Valuations:  overall = 1..2
    ----------
    Intermediate solution:x = 1; y = 1; z = 3
    Valuations:  overall = 1..1
    ----------
    Intermediate solution:x = 1; y = 2; z = 1
    Valuations:  overall = 2..2
    ----------
    ==========
    

Citing

If you plan to use constraint relationships in your research, please consider citing Background material can be found in the papers:

Contact

For general information and support please contact Alexander Schiendorfer.