Home

JSR-331 User Manual

1. Returns a type of this value selector ud public ValueSelectorType getType return ValueSelectorType CUSTOM Such custom selectors can take into consideration the business objects potentially attached to every constrained variable Similar selectors for other types of constrained variables will be added later on More Search Strategies At this stage of the JSR 331 development the only way for a user to utilize search strategies different from the default one is to become implementation dependent For example if an implementation provide a BoundBacktrackingSearchStrategy as a subclass of javax constraints impl search AbstractSeachStrategy then to use this strategy a user may write SearchStrategy strategy new BoundBacktrackingSearchStrategy 100 steps solver setSearchStrategy strategy Interface Solution The standard interface Solution specifies solutions can be generated by such Solver methods as findSolution findOptimalSolution and by solution iterators This interface is completely implemented on the common level in the class javax constraints impl search BasicSolution but any JSR 331 implementation may extend it with its own subclass javax constraints impl search Solution A solution instance contains copies of all decision variables that were used by a search strategy that created this solution These copies are in the state in which original variable would be left
2. Cost 3XY 4Z Var cost x multiply y multiply 3 minus z multiply 4 cost setName Cost problem post cost 2 2 problem post cost 25 return problem public void testOneSolution Problem problem defineCsp problem log One solution Solver solver problem getSolver Solution solution solver findSolution if solution null problem log No Solutions else solution log problem log After Search problem getVars assertTrue solution getValue X 2 assertTrue solution getValue Y 6 530 JSR 331 Constraint Programming API assertTrue solution getValue Z 8 assertTrue testOneSolution Invalid Cost solution getValue Cost 4 public void testAllSolutions Problem problem defineCsp problem log All solutions Solver solver problem getSolver Solver setMaxNumberOfSolutions 4 Solution solutions solver findAllSolutions for Solution sol solutions sol log assertTrue solutions length 4 public void testSolutionIterator Problem problem defineCsp problem log Solution Iterator Solver solver problem getSolver SolutionIterator iter solver solutionIterator int n 0 while iter hasNext Solution solution iter next solution log ntt assertTrue n 5 public void testOptimalSolution Problem problem defineCsp p
3. Constraint postElement Var vars Var indexVar String CP oper Var var solver This method creates posts and returns a new linear constraint such as vars indexVar lt value Here vars indexVar denotes a constrained integer variable whose domain consists of integer values from the domain of the vars i where iis within the domain of the indexVar For example if oper is lt it means that a variable vars indexVar must be less than the variable var All possible comparison operators have been described above These constraints do NOT assume a creation of intermediate variables for values indexVar the fact that may allow more efficient implementations Cardinality Constraints The Problem interface specifies convenience methods for creating constraints that deal with cardinalities of the arrays of constrained variables These constraints count how often certain values are taken by an array of constrained variables The cardinality variable is a constrained variable that is equal to the number of those elements in the array vars that are bound to the value cardValue Consider an example when you want to limit capacity of suppliers that defined as an array of constrained integer variables The maximal capacities are defined in a regular array int capacities 1 4 2 1 3 Here is the proper constraint for int j 0 j lt nbSuppliers j p postCardinality suppliers j
4. it means that variable var must be less or equal to the value Constraint linear Var varl String oper Var var2 CP This method creates and returns a new constraint such as varl lt var2 solver For example if oper is lt it means that the variable var1 must be less than the variable var2 Constraint linear Var vars String oper int value CP This method creates and returns a new linear constraint such as solver sum vars lt value For example if oper is it means that a sum of all of the variables from the array vars must be less or equal to the value Constraint linear Var vars String oper Var var CP This method creates and returns a new linear constraint such as solver sum vars lt var For example if oper is lt it means that a sum of all of the variables from the array vars must be less than the variable var 28 JSR 331 Constraint Programming API Constraint linear int values Var vars String oper CP int value solver This method creates and returns a new linear constraint such as values vars lt value For example if oper is lt it means that a scalar product of all values and all variables vars must be less than the value The arrays values and vars must have the same size otherwise a runtime exception will be thrown Constraint linear int values V
5. lt capacities j The entire problem is described and solved below Here is the list of Problem s methods for posting cardinality constrains Methods of the interface Problem Impl Level Constraint postCardinality Var vars int cardValue String CP oper int value solver This method creates posts and returns a new cardinality constraint such as cardinality vars cardValue lt value Here cardinality vars cardValue denotes a constrained integer variable that is equal to the number of those elements in the array vars that are bound to the cardValue For example if oper is lt it means that the variable cardinality vars cardValue must be less than the value Constraint postCardinality Var vars int cardValue String CP oper Var var solver This method is similar to the one above but instead of value the cardinality vars cardValue is being constrained by var 319 JSR 331 Constraint Programming API Constraint postCardinality Var vars Var cardVar CP String oper int value solver This method creates posts and returns a new cardinality constraint such as cardinality vars cardVar value Here cardinality vars cardVar denotes a constrained integer variable that is equal to the number of those elements in the array vars that are equal to cardVar For example if oper is it means that the variable card
6. problem getSolver SearchStrategy typeStrategy solver getSearchStrategy typeStrategy setVars types SearchStrategy countStrategy solver newSearchStrategy countStrategy setVars counts countStrategy setVarSelectorType VarSelectorType MIN DOMAIN solver addSearchStrategy countStrategy solution solver findSolution There are several convenience methods that allow a user to add additional strategies to the execution list without explicitly creating new search strategies The method addSearchStrategy also supports different combinations of parameters Var VarSelector and ValueSelector The above code may be written more compactly as Solver solver problem getSolver solver getSearchStrategy setVars types solver addSearchStrategy counts VarSelectorType MIN DOMAIN solution solver findSolution Adding Non Search Strategies The JSR 331 allows a user to add non search strategies to the search strategy execution list The common JSR 331 implementation provides an example of such non search strategy called StrategyLogVariables A user may use this strategy to display a state of problem variables after different search iterations like in this example Solver solver p getSolver solver addStrategyLogVariables Solution solution solver findOptimalSolution Objective MAXIMIZE p getVar cost if solution null solution log else p log No Solutions 440 JSR 331 Cons
7. 0 10 a user may write Var vars p variableArray A O 10 100 Note Any JSR 331 implementation may provide other Var constructors that may take 199 JSR 331 Constraint Programming API advantage of its specific features At the same time a user should be warned that the use of CP solver specific constructors renders the application code dependent on that particular implementation As more Var constructors become commonly acceptable for different implementations they will be added to the standard Problem interface Manipulating Integer Variables The Var interface provides the following methods that allow a user to evaluate the state of constrained integer variables int getDomainSize returns the current number of elements in the domain DomainType getDomainType returns the domain type boolean isBound returns true if the variable is already instantiated with a single value domain s size 1s 1 int getValue returns a value with which the variable was instantiated If this variable 1s not bound this method throws a runtime exception int getMin returns the minimal value from the current domain int getMax returns the maximal value from the current domain The JSR 331 does not allow a user to modify variables directly e g using setters like setMin or setMax they are simply not defined Instead a user may only post the 66 00 proper linear constraints for the problem p p
8. strategy setVarSelectorType VarSelectorType MIN DOMAIN MIN VALUE strategy setValueSelectorType ValueSelectorType MIN Solution solution solver findSolution if solution null p log no solutions found else solution log solver logStats public static void main String args String arg args length 0 1000 args 0 int n Integer parseInt arg Queens q new Queens n q define q solve A JSR 331 test implementation produced the following results Queens 1000 Solution 1 x 0 0 x 1 555 x 2 1 x 3 502 x 4 2 x 5 507 Execution Profile Number of Choice Points 996 Number of Failures 8 Execution time 1093 msec 550 JSR 331 Constraint Programming API Warehouse Construction Problem This problem was specified in ILOG Solver User Guide Let s assume that a company plans to create a network of warehouses to supply its existing stores Let s suppose in addition that the company already has a number of suitable sites for building warehouses and thus wants to know whether or not to create a warehouse on each such site For each site chosen the company wants to determine the optimal capacity for the warehouse The company considers the average merchandise turnover as identical from one store to another However the distance among locations and the transportation infrastructure both lead to varying transportation costs for each pair consisting of a store an
9. CP solvers by changing only implementation specific jar files in their classpath Note An ability to switch between underlying solvers with no changes in the application code comes with a price the fixed naming convention for implementation packages means that JSR 331 based applications cannot mix two different implementations at the same application code The choice of an underlying implementation is defined only by a jar file in the application classpath Application Deployment Model The deployed business applications that utilize the JSR 331 API require the following jar files to be added to their classpaths jsr331 jar includes all standard specification interfaces and classes jsr331 solver jar includes all implementation specific classes solver jar include all classes for the CP solver based on which this implementation was created For example a CP based deployment that utilize Constrainer will need the following jars FSP Skaj aE jsr331 constrainer jar constrainer light jar For example a LP based deployment that utilize Gurobi will need the following jars jsr331 jar jsr331 linear jar jsr33l gurobi jar Note The JSR 331 does not depend on a particular implementation of logging mechanisms and does not need logging jars However all JSR 831 implementations provide their own logging by implementing only basic methods log string debug string and error string inside the class Problem For convenience the sta
10. after the solution search is completed but before a possible state restoration There are no requirements that all decision variables should be instantiated it depends on the used search strategy Here are main Solution s methods 490 JSR 331 Constraint Programming API Method of the interface Solution Impl Level public Var getVars This method returns an array of variables with the same names as all variables that were added to the problem These variables keep a current state of the initial variables when the solution was found Common public Var getVar String name This method returns the variable with the name name saved within this solution It throws a runtime exception if the proper variable does not exist Itis a copy of the actual problem s variable with the name name but it is in the state in which original variable would be left after the solution search is completed before a possible state restoration Common public int getValue String name This method returns the found value of the variable with the name name saved within this solution It throws a runtime exception if the proper variable does not exist or was not instantiated during the solution search Common public boolean isBound This method returns true only if all solution variables are instantiated bound Common public boolean isBound String name This method returns true only if a so
11. have different values find a solution that satisfies the following constraints X x Y X Y 2 Z 24 3X 4Y 5Z 2R gt 0 X Y 2Z2 R gt 15 2X AY 5Z2 R gt X Y The following code demonstrates how this problem can be defined and solved using JSR 331 API import javax constraints public class Test Problem p ProblemFactory newProblem Test public void define PROBLEM DEFINITION Define variables Var x p variable X 1 10 Var y p variable Y 1 10 Var z p variable Z 1 10 Var r p variable R 1 10 Var vars x y Z r Define and post constraints try p post x y X X p post z 4 Z gt A4 p post x plus y z X Y 4AZ p postAllDifferent vars int coefl 3 4 5 2 p post coefl vars 0 3x 4y 5z 2r gt 0 p post vars gt 15 x yt 2 4r gt 15 110 JSR 331 Constraint Programming API int coef2 2 4 5 1 p post coef2 vars gt x multiply y 2x 4y 5z r gt x y catch Exception e p log Brror posting constraints e System exit 1 public void solve PROBLEM RESOLUTION p log Find Solution Solver solver p getSolver Solution solution solver findSolution if solution null solution log else p log No Solution solver logStats public static void
12. stating that all constrained integer variables of the array vars must take different values from each other There are similar methods for other types of variables Note The latest example also allows posting with different consistency levels 29 JSR 331 Constraint Programming API Element Constraints The Problem interface also specifies convenience methods for creating constraints that deal with elements of the arrays of constrained variables If a constrained integer variable indexVar serves as an index within an array values then the result of the operation values indexVar will be another constrained variable Consider an example when you want to limit a yet unknown loan term to be at least 36 months or more Here is the proper constraint int loanTerms 12 24 36 48 72 Var indexVar p variable index 0 loanTerms length 1 p postElement loanTerms indexVar 36 Similarly in the above Bin example we used to limit bin capacity variables by posting element constraints based on bin type variables capacity p variable capacity 0 capacityMax Hn p postElement binCapacities type capacity While Java does not allow us to overload the operator the standard interface uses the Problem methods to create element constraints Here is the list of such methods limited to integer variables Methods of the interface Problem Impl Level Constraint postEl
13. 12000 set limits stallnodes 1000 set limits gap 1 05 set heuristics emphasis aggressive rem set SOLVER org jcp jsr331 linear scip lib jsr331 scip jar LPCOMMON rem set OPTIONS DLP_SOLVER_OPTIONS Threads 1 Cuts 2 timelimit 15000 rem set SOLVER org jcp jsr331 linear gurobi lib jsr331 gurobi jar LPCOMMON 50 JSR 331 Constraint Programming API set LIBS bin LIB jsr331 jar SOLVER ZLOGLIBS java Xms1024m Xmx1024m ZOPTIONS classpath LIBS PROGRAM echo done To switch between CP solvers you need to modify the file run bat For example the above text defines SOLVER as constrainer To switch to choco put rem in front of set SOLVER lib constrainer and remove rem in front of set SOLVER 1lib choco If you work with UNIX LINUX you need to replace bat files with similar sh files Working under Eclipse IDE To use the JSR 331 with Eclipse IDE simply import the folder jsr331 into your Eclipse workspace You may run all samples directly from Eclipse by selecting their sources with a right click and then Run as Java Application To switch between underlying solvers just select the Project Properties and simply change Libraries inside Java Build Path Current JSR 331 Implementations The current list of JSR 331 implementations is presented on the following diagram below Greyed out solvers are consider for future implementations 60 JSR 331 Constraint Programmin
14. Common Interface ConstrainedVariable The interface ConstrainedVariable defines common methods for all types of constrained variables Here is a summary of these methods Method of the interface Comment Impl ConstrainedVariable Level public void Defines the name of this variable Common setName String name public String Returns the name of this variable Common getName public void This method defines a concrete Common setImpl Object impl implementation of this variable provided by a specific CP solver public This method returns a concrete Common Object getImpl implementation of this variable provided by a specific CP solver public void setObject This method is used to attach a Business Common Object obj Object to this variable public Object This methods returns a Business Object Common getObject associated with this variable The methods setObject and getObject provide an ability to associate any application objects with constrained variables These objects may be effectively used by application developers to define custom constraints and variable value selectors The method setImpl is used by an underlying JSR 331 implementation to associate an implementation object with an instance of a standard constrained variable It is used 16 9 JSR 331 Constraint Programming API internally by JSR 331 implementations but also provides a user an ability to switch to an implementation
15. Execution List The search strategy execution list allows a user to mix strategies for different types of decision variables and to control their execution order For example for scheduling and resource allocation problems a user may decide first to schedule all activities and then assign resources to already scheduled activities But a user may also decide first to assign resources and only then to schedule activities based on resource availability 430 JSR 331 Constraint Programming API The Solver method SearchStrategy getSearchStrategy returns the first search strategy specific for this particular JSR 331 implementation A user may specify decision variables and set different variable selectors and value selectors for the default strategy The Solver method SearchStrategy newSearchStrategy returns a new instance of the default search strategy specific for this particular JSR 331 implementation A user may specify decision variables and selectors for this strategy and then add it to the end of the search strategy execution list The Solver executes all strategies from this list in the order they were added and the execution succeeds only when all strategies from the list are successfully executed Let s assume that a user has two arrays of decision variables types and counts and wants Solver first instantiate all types and only then all counts possibly using different selectors Here 1s how it can be done Solver solver
16. JSR 331 Java Constraint Programming API USER MANUAL Version 1 1 0 Status Maintenance Release Specification Maintenance Lead Jacob Feldman OpenRules Inc Java Community Process www jcp org October 2012 JSR 331 Constraint Programming API Table of Contents ENAA LCE a P MH 4 Document Conventions m 4 InstallabtiO8 eee sete ede e CURE PER RENT ERE IRE EIER ES E FEDERER EIER EUR ERES 4 Usine a Standalone Version ensisi boo EE ES Em ERE EE qoe ERI En ERE Eo reepedis 5 Working under Echpse IDE 5 56 ht he haeresi rae eere I oia rae AE REAREN 6 Current JSR 331 Implementations sss eee eene nnn eren tn nre 6 Implementation Structure sssesessseseseeeeenre nennen entere er nnns n nett r siente sienten seen nennen nnns 8 Application Deployment Model cccceccccscccceceesesssseseccceceesenssseeeeeeceesensasseeeeeceeserssssseeeeeeeenes 9 Constraint Satisfaction Problem CSP iiiiieis ion edere beer voee ape dro aee e doo aae ere aaa ev be aan iiaae 10 Formal Definition inei rtt eret Eier Ee ada eine asini Fa E deste dae enne dca endo 10 Major ISR 331 Concepbssoicee reiecit nin eium iuit mni 10 Introductory Example eenei neee e ee enero EE E ret even cute se Deux Peso dee ee studies AEE at eTA 11 Problem Definition Concepts cccccecccccsccessessssscecececeesesssscecececeesesssseeeecceceesesssseeeeseeceenestsaeaeeees 13 Interface Problema c 13 Creating Variab
17. PUT ORDER smallest lower bound MIN VALUE largest upper bound 45 JSR 331 Constraint Programming API i MAX VALUE min size of domain tie break undefined ui MIN DOMAIN 7 ck min size of domain smallest lower bound tie break und MIN DOMAIN MIN VALUE kk min size of domain random tie break ay MIN DOMAIN RANDOM y k k random selection of variables RE RANDOM ck min size of domain as first criteria tie break by degree that is the number of attached constraints MIN DOMAIN MAX DEGREE 7 ck min value of fraction of domain size and degree ay MIN DOMAIN OVER DEGREE min value of domain size over weighted degr ay MIN DOMAIN OVER WEIGHTED DEGREE ck largest number of recorded failures in attached constraints uri MAX WEIGHTED DEGREE largest impact select variable which when assigned restricts the domains of all other variables by the largest amount y MAX IMPACT ck largest number of attached constraints 7 MAX DEGREE largest difference between smallest 46 JSR 331 Constraint Programming API and second smallest value in domain g MAX RE GRET custom variable selector CUSTOM Not all these selectors have to be implemented by every JSR 331 implementation Most of variable selectors have been already included in the common implementation in the package javax constra
18. alCardinality Var vars int Common values int cardMin int cardMax or CP This method creates and posts a new constraint that states solver For each index i the number of times the value values i occurs in the array vars should be between cardMin i and cardMax i inclusive The arrays values cardMin and cardMax should have the same size otherwise a RuntimeException will be thrown A newly created constraint is posted The common JSR 331 implementation provides the default implementations of both these constraints using simple decompositions Concrete implementation may or may not provide their own implementation class GlobalCardinality that supports both variants of this popular constraint with different consistency levels Min Max Constraints The Problem interface also specifies convenience methods for creating and posting constraints for constrained variables that are equal to a minimum and a maximum of other variables Methods of the interface Problem Impl Level Constraint postMin Var vars String oper int value Common This method creates and posts a new constraint that states The minimal variable in the array vars should be less that value if the oper is lt Replace the word less for the proper words for all other comparison operators A newly created constraint is posted Constraint postMin Var vars String oper Var var Common This method creates and posts a n
19. an be inherited from the common usually abstract classes defined in the package with the same name but on the specification level e g class javax constraints impl Problem extends javax constraints impl AbstractP roblem that implements javax constraints Problem javax constraints impl constraint This is a Library of Constraints that contains implementations of basic and global constraints which are based on concrete CP solvers javax constraints impl search This is a Library of Search Strategies that contains implementations of search strategies which are based on concrete CP solvers Additionally every implementation may also provide its own native constraints and search strategies assuming that they follow the standardized interfaces javax constraints Constraint and javax constraints SearchStrategy A user should be aware if s he uses a solver specific constraints or search strategies s he 80 JSR 331 Constraint Programming API commits to this particular solver the concepts not included in the standard may not be available in another solver The fact that all JSR 331 implementations will use the same names for packages major classes and methods will allow business application developers to easily switch between different implementations without any changes in the application code They can write application specific constraint based engines once using only common CP API and use different
20. ar vars String oper CP Var var solver This method creates and returns a new linear constraint such as values vars lt var For example if oper is lt it means that a scalar product of all values and all variables vars must be less than the variable var The arrays values and vars must have the same size otherwise a runtime exception will be thrown Instead of the methods with name linear a user may use the method constraint with the same parameters In this case a constraint not only will be created but also posted When a user post the constraint sum vars 20 in this way p post vars 20 there is no assumption that an intermediate variable for the sum vars will be created it depends on a concrete constraint implementation If a user actually needs this sum variable s he may write a code similar to this one Var sumVar p variable sum min max p linear vars sumVar post p post sumVar 20 Or easier p post sum vars 20 or even more easier p post vars 20 All Different Constraint The JSR 331 interface Problem defines a simple way to create and post the most popular constraint commonly known as allDifferent public Constraint postAllDifferent Var vars There is also a more compact synonym public Constraint postAllDiff Var vars These methods create post and return a new constraint
21. ars to the default solver log public Var min Var varl Var var2 Common This method returns a new variable constrained to be the minimum of variables varl and var2 public Var max Var varl Var var2 Common This method returns a new variable constrained to be the maximum of variables varl and var2 public Var min Var vars Common This method creates a new Var constrained to be the minimum of all variables in the array vars public Var max Var vars Common This method creates a new Var constrained to be the maximum of all variables in the array vars 15 9 JSR 331 Constraint Programming API public Var sum Var vars Common This method creates a new Var constrained to be the sum of all variables in the array vars public Var scalProd int values Var vars Common This method creates a new Var constrained to be the scalar product of the array of values and the array of variables vars public Var element int values Var indexVar Common This method creates a new constrained variable that is an element of the integer array values with an index defined by another constrained variable indexVar public Var element Var vars Var indexVar Common This method creates a new constrained variable that is an element of the array of constrained variables vars with an index defined by another constrained variable indexVar
22. ayList Solution while iter hasNext Solution solution iter next solutions add solution Solution array new Solution solutions size for int i 0 i lt array length i array i solutions get i return array The common implementation also takes into consideration the current limits for a maximal number of solutions and for the total available time This code provides an example of how a user may navigate through different solutions A user may add its own code to decide which solutions to save and when to stop the search In a similar way we a user may implement its own search for an optimal solution public Solution findOptimalSolution Var objectiveVar SolutionIterator iter solutionIterator int bestValue Integ r MAX VALUE Solution solution null while iter hasNext solution iter next try int newValue solution getValue objectiveVar getName if bestValue gt newValue bestValue newValue getProblem post obj newValue may fail catch Exception e break objectiveVar setName oldName return solution The common implementation of this method in the package javax constraints impl search AbstractSolver also takes into consideration 519 JSR 331 Constraint Programming API the current limits for a maximal number of solutions and for the total available time The Objective MAXIMIZE can be replaced by Object
23. batch files that can be used to run different examples For example runBins bat will execute the example jsr331 src org jcp jsr331 samples Bins java All batch files are based on the file run bat echo off cd dpe if not X1 goto defined set PROGRAM org jcp jsr331 samples SendMoreMoney goto run defined set PROGRAM org jcp jsr331 samples 71 run echo Run PROGRAM set LIB org jcp jsr331 tck lib set LOGLIBS XLIBX logging commons logging 1 1 janr XLIBX logging commons logging api 1 1 jar LIB logging log4j 1 2 15 jar rem set SOLVER org jcp jsr331 tck lib constrainer jsr331 constrainer jar org jcp jsr331 tck lib constrainer constrainer light jar set SOLVER lib choco jsr331 choco jar lib choco choco solver 2 1 5 20120603 with sources jar rem set SOLVER 1lib jacop jsr331 jacop jar lib jacop jacop 3 0 jar rem set SOLVER 1lib jsetl jsr331 jsetl jar lib jsetl jsetl jar set LPCOMMON org jcp jsr331 linear 1lib jsr331 linear jar set OPTIONS rem set SOLVER org jcp jsr331 linear glpk lib jsr331 glpk jar LPCOMMON rem set SOLVER org jcp jsr331 linear cplex lib jsr331 cplex jar LPCOMMON rem set SOLVER org jcp jsr331 linear 1lpsolve lib jsr331 lpsolve jar LPCOMMON rem set SOLVER org jcp jsr331 linear coin lib jsr331 coin jar LPCOMMON rem set SOLVER org jcp jsr331 linear ojAlgo lib ojalgo jar LPCOMMON rem set OPTIONS DLP SOLVER OPTIONS set limits time
24. c3 post blue can contain glass steel copper cl p linear type blue c2 p linear counts plastic 0 c3 p linear counts wood 0 cl implies c2 and c3 post green can contain plastic wood copper cl p linear type green c2 p linear counts glass 0 c3 p linear counts steel 0 cl implies c2 and c3 post wood requires plastic cl p linear counts wood 0 c2 p linear counts plastic 0 270 JSR 331 Constraint Programming API cl implies c2 post glass exclusive copper cl p linear counts glass 0 c2 p linear counts copper 0 cl or c2 post copper exclusive plastic cl p linear counts copper 0 c2 p linear counts plastic 0 cl or c2 post Linear Constraints All constraints that deal with a comparison of constrained expressions use the standardized comparison operators expressed as strings man Less Than lt Less than or Equal to d Equal to gt Greater than or Equal to dd Greater Than i Not Equal Here is the list of linear constraints limited to constrained integer variables Methods of the interface Problem Impl Level Constraint linear Var String oper int value CP This method creates and returns a new constraint such as var lt value solver For example if oper is lt
25. d a warehouse The objective is to minimize total cost by determining for each warehouse which stores should be supplied by it and what its capacity should be The total is then the sum of supply costs plus the costs of building each warehouse import javax constraints public class Warehouse Problem p ProblemFactory newProblem Test Var suppliers Var open Var costs Var totalCost public Warehouse int nbStores int nbSuppliers int buildingCost int capacities int costMatrix suppliers new Var nbStores open new Var nbSuppliers try 1 suppliers p variableArray supplier 0 nbSuppliers 1 nbStores costs new Var nbStores open p variableArray open 0 1 nbSuppliers int maxCost 0 int maxSumCost 0 for inti 0 i lt nbStores i for int j 0 j lt costMatrix i length j if maxCost lt costMatrix il jl maxCost costMatrix i j costs i p variable cost i 0 maxCost p postElement costMatrix i suppliers i costs i p postElement open suppliers i 1 maxSumCost maxCost cardinality constraint for int j 0 j lt nbSuppliers j p postCardinality suppliers j lt capacities j totalCost sum cost sum open buildCost Var sumCost p variable sumCost 0 maxSumCost p post costs sumCost Var sumOpen variable sumOpen 0 nbSuppliers p post open sumOpen post totalCost sumOpen
26. d to be the product of this solver variable and the given value public Var multiply Var var this var CP This method creates a new Var constrained to be the product of this solver variable and the given variable var public Var divide int value this value Common This method creates a new Var constrained to be the quotient of this or CP variable and the given value It throws a Runtime Exception if value 0 solver public Var divide Var var throws Exception this Common var or CP This method creates a new Var constrained to be quotient of this variable solver and the given variable var public Var mod int value this value Common This method creates a new Var constrained to be the remainder after performing integer division of this variable by the given value It throws a Runtime Exception if value 0 public Var sqr this this Common This method creates a new Var constrained to be the product of this variable and itself public Var power int value this value Common This optional method creates a new Var constrained to be this variable or CP raised to the power of the given value solver public Var abs abs this CP This method creates a new Var constrained to be the absolute value of solver this variable optional Note that all these methods only create new constrained variables but do not add them to the problem If necessary it should be done exp
27. e Luxemburg asBool multip p linear L p linear L H uxemburg Germany asBool multip uxemburg Belgium asBool multip Optimization objective Var weighteds weightedSum setName Total Constraint Violations Solution solu um tion p sum weightVars p getSolver findOptimalSolution weightedSum null solution log if solution y 257 ly 9043 ly 568 4109 JSR 331 Constraint Programming API for int i 0 i lt vars length i String name vars i getName p log namet colors solution getValue name else p log no solution found catch Exception ex ex printStackTrace This problem may produce the results that may look like below Solution 1 Belgium 0 Denmark 0 France 1 Germany 2 Netherland 1 Luxemburg 1 Total Constraint Violations 257 Belgium red Denmark red France green Germany blue Netherland green Luxemburg green Interface SearchStrategy The JSR 331 utilizes the concept SearchStrategy to allow a user to choose between different search algorithms provided by different implementations Search strategies are used by those Solver s methods that find a solution find all solutions find an optimal solution and by solution iterators A search strategy should know all decision variables it will try to instantiate during the search and may need external selecto
28. ect Bin a constructor only the complete implementation is included in the standard package org jcp jsr331 samples see Bins java Static final int red 0 blue 1 green 2 static final int glass 0 plastic 1 steel 2 wood 3 copper 4 class Bin public int id public Var type public Var capacity public Var counts per component public Bin Problem p int binId id binId type p variable Bin id Type 0 binTypes length 1 p Log Capacity constraints int capacityMax 0 for int i 0 i lt binCapacities length i if binCapacities i gt capacityMax capacityMax binCapacities i capacity p variable capacity 0 capacityMax p postElement binCapacities type capacity counts new Var components length for int i 0 i lt components length i counts i p variable countName i 0 capacityMax Sum of counts lt capacity p post counts lt capacity p log Containment constraints Constraint cl 02 C3 red contains at most 1 of wood cl p linear type red c2 p linear counts wood lt 1 cl implies c2 post green contains at most 2 of wood cl p linear type green c2 p linear counts wood 2 cl implies c2 post red can contain glass wood copper cl p linear type red c2 p linear counts plastic 0 c3 p linear counts steel 0 cl implies c2 and
29. em SENDMORY public void define Problem Definition define variables Var S p variable S 1 9 Var E p variable E 0 9 Var N p variable N 0 9 Var D p variable D 0 9 Var M p variable M 1 9 Var O p variable O 0 9 Var R p variable R 0 9 Var Y p variable Y 0 9 Post all different constraint Var vars new Var S E N D M O R Y p postAllDifferent vars Define constraint SEND MORE MONEY int coef 1000 100 10 1 1000 100 10 1 10000 1000 100 10 1 Var sendmoremoney new Var S E N D M O R E M O N E Y p post coef sendmoremoney 0 public void solve Problem Resolution Solution s p getSolver findSolution if s null p log No Solutions else s log public static void main String args Solution 1 SendMoreMoney sm new SendMoreMoney sm define sm solve S 9 E 5 N 6 D 7 M 1 O 0 R 8 Y 2 PROBLEM RESOLUTION CONCEPTS To represent the Problem Resolution part of any CSP the JSR 331 uses the interface Solver The solver allows a user to solve the problem by finding feasible or optimal Solutions Here is an example of a simple problem resolution 36 JSR 331 Constraint Programming API p log Find One solution Solver solver p getSolver Solution solution solve
30. ement int values Var indexVar String CP oper int value solver This method creates posts and returns a new linear constraint such as values indexVar value Here values indexVar denotes a constrained integer variable whose domain consists of integer values i where i is within the domain of the indexVar For example if oper is lt it means that a variable values indexVar must be less than the value Constraint postElement int values Var indexVar String CP oper Var var solver This method creates posts and returns a new linear constraint such as values indexVar value Here values indexVar denotes a constrained integer variable whose domain consists of integer values i where i is within the domain of the indexVar For example if oper is lt it means that a variable values indexVar must be less than the variable var Constraint postElement Var vars Var indexVar String CP oper int value solver This method creates posts and returns a new linear constraint such as vars indexVar lt value Here vars indexVar denotes a constrained integer variable whose domain consists of integer values from the domain of the vars i where iis within the domain of the indexVar For example if oper is lt it means that a variable vars indexVar must be less than the value 30 JSR 331 Constraint Programming API
31. ew constraint that states The minimal variable in the array vars should be less that var if the oper is lt Replace the word less for the proper words for all other comparison operators A newly created constraint is posted There are similar constraints postMax defined for maximal variables in the array vars More Constraints Any JSR 331 compliant CP solver provides its own implementations of major constraints specified in the standard interface Problem At the same time as the standard evolves JSR 331 implementations may provide other constructors for already defined constraints and for other constraints they have implemented The only requirement is that constraints not included in the standard should still implement the interface javax constraints Constraint This approach allows a user to take advantage of 33 JSR 331 Constraint Programming API the implementation specific features At the same time a user should be warned that the use of implementation specific constructors renders the application code dependent on that particular implementation The common JSR 331 implementation javax constraints impl constraint already provides several additional constraints that do not depend on a particular CP solver Among them e ConstraintTrue always successful e ConstraintFalse always fails when posted e ConstraintTraceVar used by the common Solver to implement methods trace e ConstraintMax
32. g API Generated Standard Problem Representation MPS LP Format Ju COIN The current release includes three implementations that are based on open source CP solvers e Choco BSD license e Constrainer GNU LGPL license e JSetL GNU GPL license One more CP based implementation JaCoP is temporarily withdrawn There are also seven implementations that are based on the following LP tools Commercial LP Solvers e IBM CPLEX e GUROBI Open Source LP Solvers e SCIP e GLPK 70 JSR 331 Constraint Programming API e COIN e LP SOLVE e OJALGO More implementations will be included in the standard installation as they become available Implementation Structure Any implementation of the JSR 331 specification is based on a concrete CP or LP solver and provides implementation classes for all interfaces defined in the package javax constraints Some implementation classes directly implement the standard interfaces and others can be inherited from common implementations provided in the specification package javax constraints imp1 The JSR 331 requires any implementation to provide as a minimum a strictly defined list of implementation classes within the following Java packages Java Package Description javax constraints impl Java classes such as Problem and Solver that provide final implementations for problem definition and resolution concepts and methods These implementation classes c
33. hat is a difference between solution objectives during two consecutive process iterations see the method setOptimizationTolerance MaxNumberOfSolutions that is the total number of considered solutions may be limited by the method setMaxNumberOfSolutions TimeLimit that is the total number of milliseconds allocated for the entire optimization process as it can be set by the method setTimeLimit The common implementation is based on the SolutionIterator see below public SolutionIterator solutionIterator This method creates and returns a solution iterator that allows a user to find and navigate through multiple solutions if any using the current search strategy public void setSearchStrategy SearchStrategy strategy This method sets a search strategy defined as a parameter as a new default search strategy to be used by methods findSolution findOptimalSolution findAllSolutions and by solution iterators At least one search strategy should be defined by every implementation as the default search strategy public SearchStrategy getSearchStrategy This method returns the current search strategy that was set by an implementation as the default search strategy or by the latest call of the method setSearchStrategy A user may adjust the search strategy by changing its default decision variables its variable selector and or its value selector Search strategy are used by methods findSolution findOptimalSol
34. he problem solvable It also demonstrates how to find an optimal solution of the problem that in this case is a solution that minimizes the total constraint violation Consider a map coloring problem that involves choosing colors for the countries on a map in a such way that no two neighboring countries have the same colors When there are not enough colors some of these constraints have to be violated based of their relative importance Below is a solution of this problem as it is presented in the JSR 331 TCK package org jcp jsr331 samples import javax constraints public class MapColoringWithViolations Problem p ProblemFactory newProblem MapColoring static final String LJ cx olors red green blue public MapColoringWithViolations try Variables int n Colors length 1 Var Belgium Var Denmark Var France Var Germany Var Netherlands Var Luxemburg Var vars p variable Belgium 0 n p variable Denmark 0 n p variable France 0 n p variable Germany 0 n p variable Netherland 0 n p variable Luxemburg 0O n Belgium Denmark France Germany Netherlands Luxemburg Hard Constraints p post France Belgium p post France Germany p post Belgium Netherlands p post Belgium Germany p post Germany Netherlands p post Germany Denmark Soft Constraints Var weightVars p linear Franc
35. hrough the generic Problem interface Here are examples of predefined constraints 1 A constraint x lt y between two constrained variables for the problem p may be expressed as p post x lt y 2 To express the fact a sum of all variables from the array vars of the type Var should be less than 20 a user may write p post vars 20 3 To express the fact that four variables x y z and t are subject to the constraint d x 4y b z 2 t gt ey a user may create and post the following constraint Var xy x multiply y non linear int coefs 3 4 5 2 Y Vari vars x y z t p post coefs vars gt xy 22 JSR 331 Constraint Programming API 4 If a user has an array of constrained variables vars and wants to state that all variables inside this array are different s he may write p postAllDifferent vars All above examples use Problem s factory methods starting with the word post to create and post constraints Posting a constraint means that this constraint will control the domain of all involved variables Every time when constrained variables are modified the posted constraints defined on these variables will try to remove inconsistent values from their domains This process is known as constraint propagation If some domains become empty constraints throw exceptions If an exception happens during the search then a search strategy will catch such excepti
36. ill be used as the default for subsequent creation of variables using var and varArray methods public Var add Var var This method adds already created variable of the type Var to the problem Common making its available for the for the proper method getVar name All added variables will also be included in the future solutions of the problem public Var add String name Var var This method adds already created variable of the type Var to the problem Common giving this variable name name public Var getVar String name Common This method returns a Var that previously was added to the problem under the name name public Var getVars Common This method returns all variables of the type Var that were previously added to the problem Any JSR 331 implementation provides at least this standard constructor public Var Problem problem String name int min int max It means that a user may also create and add a variable this way Var digitVar new Var problem A 0 9 problem add digitVar In this case a user should add import javax constraints impl Var However an implementation may use other forms of constructors too So it is not recommended to use constructors directly because it may potentially make a commitment to a selected 189 JSR 331 Constraint Programming API implementation diminishing the value of the standardization Domain Types Integer con
37. inality vars cardValue must beless than the value Constraint postCardinality Var vars Var cardVar CP String oper Var var solver This method is similar to the one above but instead of value the cardinality vars cardVar is being constrained by var All possible comparison operators have been described above These constraints do NOT assume a creation of intermediate cardinality variables the fact that may allow more efficient implementations Global Cardinality Constraints The Problem interface also specifies convenience methods for creating global cardinality constraints known as GCC that represent not one but multiple cardinalities at the same time You may see how the GCC constraint being used in the standard example GraphColoring Here is the list of Problem s methods that post global cardinality constraints Methods of the interface Problem Impl Level Constraint postGlobalCardinality Var vars int values Common Var cardinalityVars or CP This method creates and posts a new constraint that states solver For each index i the number of times the value values i occurs in the array vars is exactly cardinalityVars i The arrays cardinalityVars and values should have the same size otherwise a RuntimeException will be thrown A newly created constraint 1s posted 32 JSR 331 Constraint Programming API Constraint postGlob
38. interface DOCUMENT CONVENTIONS The regular Century Schoolbook font is used for information that is prescriptive by this specification The italic Century Schoolbook font is used for notes clarifying the text The Courier New font is used for code examples INSTALLATION The JSR 331 is available for downloads from the JCP Download Page at http jcp org en jsr summary id 331 You will download a zip file jsr331 zip that includes Sources with examples of constraint satisfaction and optimization problems inside the folder src org jcp jsr311 samples Libraries with jar files inside the folder lib o jsr331 jar JSR331 interfaces javax constraints and common solver independent implementations javax constraints impl o logging jar Apache Logging jars o choco jar jars for Choco s implementation of the JSR 331 40 JSR 331 Constraint Programming API o constrainer jar jars for Constrainer s implementation of the JSR 331 o jsetl jar jars for JSetL s implementation of the JSR 331 o linear jar jars for Linear solvers All JSR 331 related jars come with the proper sources so a user may easily debug not only his her own code but look at the actual implementations The software is provided under the terms of open source licenses included in the folders for the proper solvers Using a Standalone Version You may use JSR 331 directly from your file system The folder 3sr331 contains
39. ints impl search selectors However the variable selectors MIN DOMAIN OVER WEIGHTED DEGREE and MAX WEIGHTED DEGREE are optional and may be implemented by a particular implementation only To set a new variable selector such as MIN DOMAIN a user may write SearchStrategy strategy solver setSearchStrategy strategy setVarSelectorType VarSelectorType MIN DOMAIN A user can easily implement her own variable selector as a subclass of the standard class avax constraints impl search selectors VarSelectorI by overloading only this abstract method ck Returns the index of the selected variable in the array of constrained variables passed to the selector as a constructor parameter If no variables to select it returns 1 y abstract public int select Such custom selector can take into consideration the business objects potentially attached to every constrained variable Similar selectors for other types of constrained variables will be added later on Value Selectors The JSR 331 specifies a set of standard value selectors that can be used by an end user to customize the standard search strategy These value selectors are defined by the standard interface ValueSelector using the following enum static public enum ValueSelectorType try values in increasing order one at a time without removing failed values on backtracking d IN DOMAIN try values in increasing order re
40. ive MINIMIZE for the objectiveVar that is opposite to the original objective These implementations are given only as examples for end users who may organize their own solution iteration cycles For example a user may decide to find 3 best solutions within 10 seconds It becomes a matter of setting the proper filters inside the above main loop right after iter next A user may also utilize business objects associated with decision variables to compare different solutions Note that the described implementations can be used with any search strategy Below is in a very simplified and inefficient but working implementation of the interface SolutionIterator public class BasicSolutionIterator implements SolutionIterator Solver solver Solution solution int solutionNumber boolean noSolutions public BasicSolutionIterator Solver solver this solver solver solution null noSolutions false solutionNumber 0 public boolean hasNext if noSolutions return false solution solver findSolution ProblemState RESTORE if solution null return false else return true public Solution next solution setSolutionNumber solutionNumber Var vars solver getSearchStrategy getVars int values new int vars length for inti 0 i lt values length i values i solution getValue vars i getName try new ConstraintNotAllEqual vars values post catch Exceptio
41. les erem GG ebrei ie PG Trbrimd ods ane erre e PU PE PUR iS 13 Creatiip and Posting Congbradmts o ee iie iei dirmi eer etiem euis 14 Common Methods sseeg e ronis p IRE o ie a E pee eddust ee eode paved dae eu do deoa idus peu ode 15 Common Interface ConstrainedVariable sees eene 16 Constrained Integer Variables Var sees eren nennen nnne seen en nenne nn nennen 17 Creating Integer Variables pe pite ceret boe de Popes Ces Ti pas Pre ava e adeps 17 Manipulating Integer Variables 5 nne Ee i roter e SERRE ONE ER e Ya e aO Tea E eds 20 Arithmetic Operations with Integer Variables ccccccccceesssssceeececeesessseseeceeceeserssaseeeess 20 Constrained Boolean Variables esses eene enne tenente nentes 22 Constrained Real Variables aei aenieiai pre e iiei eter euet deti epu etus ote 22 Constrained Set Variables nee rentrer eiae roin e LEARTES REER REEE EEEE E 22 Defining Cons EATtUs u ioca mirar EH re EP P erac va E PE Fore ideni e E Se e RR HE EAR io Oeo gs 22 JSR 331 Constraint Programming API Common Interface Constraints esie er nre ONERE TER e NES IEE R ERTER er PE PEORES 23 Common Implementation Constraint 3 ure tre rtr ors ER EE I THEO cece 25 Posting COoBSLEATRUS uccide d ees oleic cs conve etae io rid eee eMe eus Eod eges eda e NENE eae ME o eR vae Seu qa ban 26 Example of a Problem with Various Constraints sesssseseseseeeeeneeeen nennen 26 Linear Constrain
42. level by using the method getimpl1 While it violates a solver independence principle in certain situations a user still may want to take an advantage of a selected CP solver by casting implementation objects to solver specific classes and using them directly with additional methods provided by this particular solver The standard interface defines the following sub interfaces of the common interface ConstrainedVariable Var integer VarBool boolean VarReal floating point VarSet set Constrained Integer Variables Var Constrained integer variables are the most popular type of the constrained variable the reason why the name of this type Var does not have an additional identifier like VarInt Each variable of the type Var has a finite domain of integer values Each JSR 331 implementation provides implementation of the major Var methods in the class javax constraints impl Var Creating Integer Variables The standard interface Problem provides multiple methods for creating new variables of the type Var For example a user may write Var digitVar problem variable A 0 9 A new constrained integer variable with an initial domain 0 9 will be created and added to the problem under the name A Here is the list of the major methods from the interface Problem that deal with creation and accessing constrained integer variables Methods of the interface Problem Impl Level public Var variable String
43. licitly with the Problem s method add var A user should be warned that while the above operations might be convenient to create arithmetic expressions and then post constraints on them these operations may create internally a lot of intermediate variables and constraints For example a user may represent constraint 3x 4y 7z gt 10 as Var exp x multiply 3 plus y multiply 4 minus z multiple 7 p post exp 10 However it may be more efficient to use this constraint instead 219 JSR 331 Constraint Programming API int coefl 3 4 7 Var vars x y z 3 p post coefl vars gt 10 Note The names of the above operations correspond to the default names used by such dynamic languages as Groovy to allow operator overloading So for example the above 3 lines may be replaced by only one line in Groovy post x 3 y 4 z 7 gt 10 Constrained Boolean Variables Boolean variables of the standard type VarBool may be considered as integer variables with domain 0 1 where 0 stand for false and 1 stands for true More details will be provided in the next releases Constrained Real Variables More details will be provided in the next releases Constrained Set Variables More details will be provided in the next releases Defining Constraints The JSR 331 specifies many major constraints that define relationships between constrained variables These constraints are available t
44. lution variable with the given name is bound Common public int getSolutionNumber This method returns a number associated with this solution Solution numbers start with 1 Common public void setSolutionNumber int number This method sets a solution number This method is to be used by a solution strategy that creates this solution Common public void log This method logs all Solution s variables to the Problem s log These variables have shown in the state as there were when the solution was found some variables could remain non instantiated Common public Solver getSolver This method returns a solver which generated this solution Common There are similar methods for other types of variables 50 JSR 331 Constraint Programming API Solution Iterator The standard interface SolutionIterator allows a user to find and iterate through multiple solutions and execute different application specific actions with each found solution The intended use of a solution iterator is presented by the following code SolutionIterator iter solver solutionIterator while iter hasNext Solution solution iter next For example a solution iterator may be uses to provide a very simple implementation of the Solver s method indAllSolutions public Solution findAllSolutions SolutionIterator iter solutionIterator ArrayList Solution solutions new Arr
45. main String args Test t new Test t define t solve This code will produce the results that may look like below Find Solution Solution 1 X 1 Y 4 Z 5 R 6 Execution Profile Number of Choice Points 3 Number of Failures 1 Occupied memory 4503712 Execution time 15 msec Instead of finding one solution of the problem we may try to find an optimal solution For example we may find a solution that maximizes the sum of all 4 variables in the array vars To do this it is enough to replace the line Solution solution solver findSolution with Solution solution solver findOptimalSolution Objective MAXIMIZE p sum vars The modified code will produce the results that may look like below Solution 8 X 4 Y 6 Z 10 R 9 sum 29 129 JSR 331 Constraint Programming API PROBLEM DEFINITION CONCEPTS In the JSR 331 Problem Definition uses the following interfaces to represent a CSP with different constrained variables and constraints Problem Var VarBool VarReal VarSet Constraint Below we describe major methods of the CP interfaces and provide examples of their use The descriptions will include the column Implementation Level that states on which level Common or CP solver these methods should be implemented The methods that are not normative are marked as optional Interface Problem The JSR 331 provides a generic interface Problem for any c
46. move value on backtracking 470 JSR 331 Constraint Programming API a MIN try values in decreasing order remove value on backtracking wy MAX 4 try to alternate minimal and maximal values 7 MIN MAX ALTERNATE try values in the middle of domain the closest to min max 2 oy MIDDLE 7 k try the median values first e g if domain has 5 values try the third value first y MEDIAN ck try a random value 7 RANDOM try a value which causes the smallest domain reduction in all other variables ey MIN IMPACT custom value selector 7 CUSTOM Not all these selectors have to be implemented by every JSR 331 implementation Most of the value selectors are already included in the common implementation in the package avax constraints impl search selectors However the value selectors IN DOMAIN and MIN IMPACT are optional and may be implemented by a particular implementation only To set a new variable selector such as MEDIAN a user may write SearchStrategy strategy solver getSearchStrategy strategy setValueSelectorType ValueSelectorType MEDIAN 48 JSR 331 Constraint Programming API A user can easily create her own value selector by implementing the standard interface javax constraints ValueSelector with only two methods Returns a value from the domain of constrained variable var xy public int select Var var
47. multiply buildingCost plus sumCost totalCost setName TotalCost p add totalCost catch Exception e p log Error in prolem definition e 56 JSR 331 Constraint Programming API throw new RuntimeException Cannot create a problem public Solution findSolution Solver solver p getSolver Var vars new Var suppliers length open length int v 0 for int i 0 i lt suppliers length i vars vt suppliers i for int i 0 i lt open length i vars vt open i solver getSearchStrategy setVars vars Solution solution solver findOptimalSolution totalCost return solution public void printSolution Solution solution if solution null p log No Solutions return solution log public static void main String args long startMS System currentTimeMillis Problem Definition int nbStores 10 int nbSuppliers 5 int buildingCost 30 int capacities 1 4 2 1 3 int costMatrix new int 20 24 11 25 30 28 27 82 83 74 fr 74 97 71 96 70 2 55 73 69 61 46 96 59 83 4 42 225 29 67 59 Lh 1 5 73 59 506 Fy 10 73 13 43 96 Ll t 93 359 63 85 406 Fz 47 65 55 71 95 c0 o0 0 c Warehouse wh new Warehouse nbStores nbSuppliers buildingCost capacities costMatrix Problem Resolu
48. n e noSolutions true return solution Thus any JSR 331 implementation may reuse common implementations or overload these methods for a better performance However if a JSR 331 implementation provides at least one search strategy all other problem resolution methods can be taken from the 520 JSR 331 Constraint Programming API common implementation MORE IMPLEMENTATION EXAMPLES The following examples demonstrate how to apply the described Problem and Solver methods to find one solution all solutions and an optimal solution of a simple arithmetic problem apply an efficient search strategy to solve the notorious Queens problem These problems are included in the standard JSR 331 installation Simple Arithmetic Problem This problem shares the same problem definition for different problem resolution cases package org jcp jsr33l tests import javax constraints import junit framework import junit textui TestRunner public class TestSolutions extends TestCase public static void main String args TestRunner run new TestSuite TestSolutions class public Problem defineCsp Problem problem ProblemFactory newProblem Test Define variables Var x problem variable X 0 10 Var y problem variable Y 0 10 Var z problem variable Z 0 10 Define constraints problem post x lt y problem post y 5 problem post x plus y 2 z
49. name int min int max This method creates a new Var with the name name and a domain CP min max It also adds a newly created variable to the problem so later on solver you may find this variable by name using the Problem s method getVar name There is a similar method without name public Var variable String name int domain This method creates a new Var with the name name and a given Common domain an array of regular integers It also adds a newly created or CP variable to the problem There is a similar method without name solver 170 JSR 331 Constraint Programming API public Var variableArray String name int min int max Common int size This method creates an array of constrained integer variable with the name like name il and a domain min max The total number of variables in the array is equal to size It also adds this array to the problem so later on a user may find this array by name using the Problem s method getVarArray name public Var variable String name int min int max DomainType type This method creates a new Var with the name name and a domain min max The domain type of this variable is defined by the parameter type see below It also adds a newly created variable to the problem public void setDomainType DomainType type Common This method sets a domain type DOMAIN SMALL DOMAIN MIN MAX DOMAIN SPARSE or DOMAIN OTHER that w
50. ndard installation includes open source Apache Logging jar files If you use them do not forget to add the proper log4j properties file to your classpath 99 JSR 331 Constraint Programming API CONSTRAINT SATISFACTION PROBLEM CSP Many real life problems that deal with multiple alternatives can be presented as constraint satisfaction problems CSP and can be successfully solved by applying different Constraint Programming tools Formal Definition Formally a Constraint Satisfaction Problem is defined by a set of variables V1 V2 Vn and a set of constraints C1 C2 Cm Each variable Vi has a non empty domain Di of possible values Each constraint Cj involves some subset of the variables and specifies the allowable combinations of values for that subset A state of the problem is defined by an assignment of values to some or all of the variables A solution to a CSP is an assignment that satisfies all the constraints If a CSP requires a solution that maximizes or minimizes an objective function it is called constraint optimization problem We will use an abbreviation CSP for both types of problems The main CSP search technique interleaves various forms of search with constraint propagation in which infeasible values are removed from the domains of the variables through reasoning about the constraints Major JSR 331 Concepts JSR 331 defines all necessary Java concepts to allow a user to represent and solve diffe
51. ons and will react according to its own logic e g continue to explore alternatives Depending on implementation constraints may throw or not runtime exceptions during posting In this case a user may put all constraint postings into a try catch block to catch contradictory constraints see below However constraint posting by itself does not guarantee that all conflicts will be caught and it may require a search to find a solution or prove that all posted constraints actually cannot be satisfied 5 To express the fact that three variables x y and z are subject to this constraint if x gt y then z lt 5 a user may write Constraint cl p linear x gt y Constraint c2 p linear z lt 5 p postIfThen cl c2 Please note that contrary to Constraint cl post x gt y method linear only creates a constraint but does not post it Common Interface Constraint The interface Constraint defines common methods for all types of constraints Here is a summary of these methods Method of the interface Comment Impl Constraint Level void setName String name Defines the name of this constraint Common String getName Returns the name of this constraint Common void setImpl Object impl This method defines a concrete Common implementation of this constraint provided by a specific CP solver Object getImpl This method returns a concrete Common implementation of this constraint p
52. onstraint satisfaction or optimization problem that allows a user to create and access major problem objects A problem serves as a factory for creation of constrained variables and constraints Every variable and every constraint belongs to one and only one problem For example the code snippet Problem p ProblemFactory newProblem Test Var x p variable X 1 10 creates an instance p of the interface javax constraints Problem The class ProblemFactory is a factory that has only one method newProblem for creation of new problems The actual implementation class javax constraints impl Problem is defined by a particular JSR 331 implementation Then the problem p creates a new constrained integer variable x with the domain 1 10 known under the name X Here the domain 1 10 is a set of integers from 1 to 10 without omissions The variable x is automatically added to the problem The JSR 331 uses the Problem interface as a factory to standardize the signatures of the main methods that allow an end user to create constrained variables and constraints Creating Variables All factory methods for constrained variables start with the word variable and newly created variables are always added to the problem It means that you always may find the added variable using the method like p getVar X and this variable will be automatically added to the default decision variables and future solutions if any To create an in
53. onstraints Var import javax constraints VarBool import javax constraints impl AbstractConstraint public class ConstraintNotAllEqual extends AbstractConstraint Constraint constraint public ConstraintNotAllEqual Var vars super vars 0 getProblem Problem p getProblem int n vars length 1 VarBool equalities for int i 0 i lt n equalities i constraint public ConstraintNotAllEqual Var vars p linear equalities new VarBool n i p linear vars i vars i 1 asBool MEM n int values super vars 0 getProblem Problem p getProblem if values length vars length throw new Runtime Exception ConstraintNotAllEqual int n vars length VarBool equalities for int i 0 i lt m requires arrays of the same length new VarBool n i equalities i p linear vars i values i 1 asBool constraint public void post constraint post p linear equalities ge n Example SEND MORE MONEY The following example demonstrates how to represent and solve a simple puzzle using JSR 331 Assuming that different letters represent different digits you need to solve the following puzzle Here is the solution import javax constraints public class SendMoreMoney 35 JSR 331 Constraint Programming API Problem p ProblemFactory newProbl
54. osting conditional constraints you want to be able to create constraints but do not post them Here is a sample code red bin contains at most 1 wood component Constraint cl linear type red Constraint c2 linear counts wood lt 1 postlIfThen cl c2 The lists of the main Problem s methods for constraint creation are presented in the section Defining Constraints 140 JSR 331 Constraint Programming API Common Methods The Problem interface also specifies general methods for logging versioning creating a solver and additional convenience methods see the JSR 331 javadoc Here are some of such methods Methods of the interface Problem Impl Level public String getAPIVersion Common This method returns the current version of the JSR 331 API public String getImplVersion CP This method returns the current version of the concrete JSR 331 solver implementation public Solver getSolver Common This method returns an instance of a Solver associated with this problem and that will be used to solve the problem If a Solver s instance is not defined yet this method creates a new Solver lazy instantiation and associates it with the problem public void log String text CP This method logs displays the text to the default log as defined by a solver selected implementation public void log Var vars CP This method logs displays all variables from the array v
55. post var min to set the minimal value for the current domain p post var max to set the maximal value for the current domain p post var value toinstantiate the variable var with the value p post var value toremove a value from the variable domain Arithmetic Operations with Integer Variables If a user wants to impose the constraint x y 10 s he can do it by posting this linear constraint p post x plus y lt 10 Below is the list of the arithmetic operations defined by the interface Var that create new constrained variables Methods of the interface Var Impl Level public Var plus int value this value CP This method creates a new Var constrained to be the sum of this variable solver and the given value public Var plus Var var this var CP This method creates a new Var constrained to be the sum of this variable solver 209 JSR 331 Constraint Programming API and the given variable var public Var minus int value this value Common This method creates a new Var constrained to be the difference between this variable and the given value public Var minus Var var this var Common This method creates a new Var constrained to be the difference between this variable and the given variable var public Var multiply int value this value CP This method creates a new Var constraine
56. provides a constraint for a maximum of an array of constrained variables e ConstraintMin provides a constraint for a minimum of an array of constrained variables e ConstraintNotAllEqual provides a constraint that states that not all elements inside an array of constrained variables are the same or all equal to the values from a given array of integers More similar constraints will be added to the common JSR 331 implementation as the standard evolves User Defined Constraints A user can define problem specific constraints by combining the existing constraints using Constraint logical operations and or negation and implies defined in the interface Problem JSR 331 users also may create a subclass of the common predefined class javax constraints impl constraint AbstractConstraint to define their own constraints For example here is an example of the constraint ConstraintNotAllEqual that actually defines two constraints 1 not all elements inside an array of constrained variables are the same 2 not all elements inside an array of constrained variables are equal to the values from a given array of integers JAVA COMMUNITY PROCI Pe fi GS Re 31 Te Common Implementation package javax constraints impl constraint PI ca ca import javax constraints Constraint import javax constraints Oper 34 JSR 331 Constraint Programming API import javax c
57. r findSolution if solution null solution log else p log No Solutions In this simple case the default solver defined as an instance of the class javax constraints Solver is trying to find one solution using the default search strategy that enumerates all variables previously added to the problem The JSR 331 explicitly defines the interface SearchStrategy that can be adjusted by a user and used by the solver to find solutions of the problem Interface Solver The JSR 331 provides interface java constraints Solver and its common implementation java constraints impl search AbstractSolver that specifies different problem resolution concepts and methods It is possible to create multiple solvers for the same problem These solvers may produce different solutions pursuing different objectives During the execution of Solver s methods the state of the Problem can be changed The interface Solver provides the following enum to control a problem state after the solver execution public enum ProblemState RESTORE DO NOT RESTORE Another enum Objective provided by the interface Solver is public enum Objective MINIMIZE MAXIMIZE It allows a user to specify the optimization objective within the method findOptimalSolution Below is the list of the major methods from the interface Solver Method of the interface Solver 370 JSR 331 Constraint Programming API public Solution findSol
58. raint is not satisfied solver VarBool asBool This optional method returns a new CP constrained boolean variable that is solver equal 1 true if the constraint is satisfied and equals 0 false if it is violated optional The methods setObject and getObject provide an ability to associate and use any application objects with a constraint The method setImpl is used by an underlying JSR 331 implementation to associate an implementation object with an instance of a standard constraint It is used internally by JSR 331 implementations but also gives a user an ability to switch to an implementation level by using the method get 1mp1 While it violates a solver independence principle in certain situations a user still may want to take an advantage of a selected CP solver by casting implementation objects to solver specific constraint classes and using them directly with additional methods provided by this particular solver A user may create new constraints as combinations of the predefined constraints using 240 JSR 331 Constraint Programming API the logical operations and or implies and negation While constraints can be either satisfied or not they may be considered as constrained Boolean variables and the method asBool allows a user to treat it as such In particular constraints as boolean variables be used may be used to define relative measures for different constraint violations if any and try to minimize
59. rent Constraint Satisfaction Problems JSR 331 supports a clear demarcation between two different CSP parts 1 Problem Definition represented by the interface Problem 2 Problem Resolution represented by the interface Solver Correspondingly all major CP concepts belong to one of these two categories At the very high level a business user is presented with only 6 major concepts Problem Constrained Variable Constraint Solver Search Strate Solution While different CP solvers use different names and representations for these major 109 JSR 331 Constraint Programming API concepts semantically these 6 concepts are invariants for the most of them JSR 331 provides a unified naming convention and detailed specifications for these concepts The Problem Definition does not know anything about the Problem Resolution An instance of the class Problem may exists without any Solver being created Contrary an instance of the class Solver may be created only base on a particular problem During solution search a solver can change a problem state such as domains of constrained variables It is the responsibility of a particular solver to keep or not different problem states based on the selected search strategy it defines Introductory Example Let s consider a simple arithmetic problem There are four integer variables X Y Z and R that may take values 1 2 3 4 5 6 7 8 9 or 10 Considering that all variables should
60. roblem log Optimal Solution Solver solver problem getSolver Var costVar problem getVar Cost Solution solution solver findOptimalSolution Objective MAXIMIZE costVar if solution null problem log No Solutions else solution log problem log Cost solution getValue Cost assertTrue solution getValue Cost 23 Queens Problem The eight queens problem is a well known problem that involves placing eight queens on a chess board in such a way that none of them can capture any other using the conventional moves allowed to a queen package org jcp jsr331 samples import javax constraints public class Queens 54 JSR 331 Constraint Programming API Problem p ProblemFactory newProblem Queens int size Var x public Queens int size this size size public void define p log Queens size create 3 arrays of variables x p variableArray x 0 size 1 size Var xl new Var size Var x2 new Var size for inti 0 i lt size itt xl i x il plus i x2 i x i minus i post all different constraints p postAllDifferent x p postAllDifferent x1 p postAllDifferent x2 public void solve Problem Resolution Find a solution Solver solver p getSolver solver setTimeLimit 600000 milliseconds SearchStrategy strategy solver getSearchStrategy strategy setVars x
61. rovided by a specific CP solver void setObject This method is used to attach any Common 230 JSR 331 Constraint Programming API Object obj business object to this constraint Object getObject This methods returns a business Common object associated with this constraint void post This method is used to post the CP constraint If the posting was solver unsuccessful this method throws a runtime exception void This method is used to post the CP post ConsistencyLevel constraint and also specifies a solver consistencyLevel consistency level that controls the optional propagation strength of this constraint see below If the posting was unsuccessful this method throws a runtime exception Constraint This method creates a new CP and Constraint c constraint and that is satisfied only solver when this constraint and the parameter constraint c are both satisfied Constraint This method creates a new CP or Constraint c constraint and that is satisfied only solver when at least one of two constraints this or the parameter constraint c is satisfied Constraint This method creates a new CP implies Constraint c constraint that states solver if this constraint is satisfied then parameter constraint c should also be satisfied Constraint negation This method creates a new Common constraint that is satisfied if and or CP only if this const
62. rs for variables and values At least one decision strategy should be provided by any implementation to serve as the default strategy created in the implementation specific Solver constructor The common interface SearchStrategy defines the following methods Methods of the interface SearchStrategy apt Level public void setName String name Common public String getName Define a setter and a getter for the name of this strategy public Solver getSolver Common Returns a solver with which this strategy is associated public void setType SearchStrategyType type Common Sets a type for this strategy The specification currently defined two type SearchStrategyType DEFAULT and SearchStrategyType CUSTOM public Var getVars Common This method returns an array of integer variables that are used by the 42 JSR 331 Constraint Programming API strategy public void setVars Var vars Common This method sets an array of integer variables that will be used by the strategy public void setVarSelector VarSelector selector Common This method sets a variable selector that will be used by the strategy during the search public void setVarSelectorType VarSelectorType type Common This method sets a variable selector of the standard type specified as a parameter public void setValueSelector ValueSelector selector Common This method sets a value selector that will be used by
63. strained variables may have different domain types defined by the following enum public enum DomainType DOMAIN SMALL DOMAIN MIN MAX DOMAIN SPARSE DOMAIN OTHER This classification assumes the following domain types DOMAIN SMALL used for relatively small domains DOMAIN MIN MAX used for large domains that mainly keep track of minimal and maximal values inside domains DOMAIN SPARSE used for domains with a lot of missing values between minimal and maximal values DOMAIN OTHER used for domains that may have a special meaning in any particular implementation A user may specify a certain domain type when creating a variable as follows Var var p variable A 0 9 DomainType DOMAIN SMALL The common default domain type is DOMAIN SMALL but an implementation may use a different default A user may redefine a default domain type by using the following Problem s method public void setDomainType DomainType type For example if a user writes setDomainType DomainType DOMAIN SPARSE then all variables created after this statement by default will have the domain type DOMAIN SPARSE After creating a few sparse variables a user may switch to different domain type A user may also create constrained integers variables by listing all possible domain values like in this example int domain new int 1 2 4 7 9 Var var p variable A domain To create an array of 100 constrained integers variables with the domain
64. teger constrained variable with adding it to the problem is to use the method variable name min max of the interface Problem For example the code Var x p variable X 1 10 The list of the main Problem s methods for creation of constrained integer variables is 139 JSR 331 Constraint Programming API presented in the section Creating Constrained Variables Creating and Posting Constraints All factory methods for creating and posting constraints start with the word post Here is the current list of the method names used to create and post constraints e postLinear or simply post e postAllDiff e postElement e postCardinality e postGlobalCardinality e postIfThen e postMax e postMin Here are examples for creating and posting constraints for the problem p p post x y thesameas postLinear x lt y post x plus y 2Z postAllDifferent vars p p p postElement vars indexVar 5 p postCardinality vars 3 0 Thus for the most popular linear constraints the suffix Linear in the method name oostLinear may be omitted The linear constraint p post x plus y 2 z may also be created and posted as follows p postLinear x plus y z or p linear x plus y z post The interface Problem also includes convenience methods called linear that allow a user to create linear constraints without posting them For example when p
65. the strategy during the search public void setValueSelectorType ValueSelectorType type Common This method sets a value selector of the standard type specified as a parameter public VarReal getVarReals Common This method returns an array of real variables that are used by the strategy public void setVarReals VarReal vars Common This method sets an array of real variables that will be used by the strategy public VarSet getVarSets Common This method returns an array of set variables that are used by the strategy public void setVarSets VarSet vars Common This method sets an array of set variables that will be used by the strategy public void trace CP This method forces the strategy to trace itself during the execution solver All implementation specific search strategies should be implemented as subclasses of the common base class javax constraints impl search AbstractSeachStrategy The only requirement to all search strategies is the following when they are invoked by an implementation specific Solver method findSolution ProblemState state they are expected to either produce a solution of the problem within the current time limit or to report that a solution cannot be found How they do it and how the internal interaction between Solver method findSolution and its search strategy is organized remains a prerogative of a concrete JSR 331 implementation Strategy
66. the total violations see an example below Note Not all constraints have implementations for the method asBool Ifa user tries to access a non existing asBool method a runtime exception will be thrown Common Implementation Constraint The JSR 331 common implementation provides the class javax constraints impl constraint AbstractConstraint that already contains default implementations of some of the above methods Each JSR 331 implementation should create its own class javax constraints impl constraint Constraint inherited from this class and that should be considered as a base class for all other constraints defined on the CP solver level There are several generic methods for creating and accessing constraints defined by the standardized Problem interface Methods of the interface Problem Impl Level Constraint add Constraint constraint This method adds already created constraint to the problem making its Common available for the for the proper method getConstraint name Constraint getConstraint String name Common This method returns a Constraint that previously was added to the problem under the name name Constraint getConstraints Common This method returns all constraints that were previously added to the problem Constraint post String name String symbolicExpression Common This optional method creates a new constraint based on the or CP symbolicExpression such as x y
67. timalSolution If the difference between newly found solution and a previous one 1s less or equal to the tolerance then the last solution is considered to be the optimal one By default the optimization tolerance is 0 public int getOptimizationTolerance Common This method returns a tolerance that was set by the method setOptimizationTolerance public void setTimeLimit int milliseconds Common This method specifies a time limit in milliseconds for the total execution of different find methods By default there is no time limit public int getTimeLimit Common This method returns a time limit in milliseconds for the total execution of different find methods By default it returns 1 that means there is no time limit public void logStats Common This method logs the solver execution statistics such as a number of choice or CP points number of failures used memory etc This method is expected to solver be specific for different implementations By default only time information optional will be logged out The Solver interface also defines several other convenience methods such as tracing methods trace Var var trace Var vars traceFailures boolean yesno traceExecution boolean yesno 40 JSR 331 Constraint Programming API Example of Constraint Relaxation Problem The following example demonstrates how to deal with real world situations when some constraints should be relaxed to make t
68. tion Solution solution wh findSolution wh printSolution solution long finishMS System currentTimeMillis System out println Runtime finishMS startMS Millis A JSR 331 test implementation produced the following results Solution 24 supplier 0 4 supplier 1 1 supplier 2 4 supplier 3 0 supplier 4 4 supplier 5 1 supplier 6 1 supplier 7 2 supplier 8 1 supplier 9 2 open O 1 open 1 1 open 2 1 open 3 0 open 4 1 TotalCost 383 Runtime 1553 Millis 570 JSR 331 Constraint Programming API 58
69. tion rci 51 More Implementation Examples 5 5 n erre terrre tenero Eae yao ken roa rao baeo aas 53 Simple Arithmetic Problem ssesesssssseseseeeees eee enne nenne nennen enne nennen enne 53 Queens Problem utente rr ater oct haer oe o a Tes ado ISO s oci cba A eee a eed vt oan ve seen cs 54 JSR 331 Constraint Programming API Warehouse Construction Problem nitor epar it otia Eo aya oso oa ERE e ERE e Rave esposa eo Pere pa osse a voee ios 56 INTRODUCTION Constraint Programming CP is a programming paradigm which provides useful tools to model and efficiently solve constraint satisfaction and optimization problems Today CP is a proven optimization technique and many CP solvers empower real world business applications in such areas as scheduling planning configuration resource allocation and real time decision support The JSR 331 Constraint Programming API is a Java Specification Request being developed under the Java Community Process rules www jcp org It specifies a Java runtime API for Constraint Programming JSR 331 was approved by JCP Executive Committee on March 2012 This document is a user manual that explains how to install and use JSR 331 with different compliant CP solvers The document is aimed at business application developers who will use the CP API to develop real world decision support application using the standard vendor neutral Java
70. traint Programming API In this case every time when the default search strategy finds a solution the StrategyLogVariables will show the state of all problem variables until an optimal solution will be found Here is the implementation code from the file StrategyLogVariables java package javax constraints impl search import javax constraints Solver import javax constraints Var public class StrategyLogVariables extends AbstractSearchStrategy Var vars public StrategyLogVariables Var vars super vars 0 getProblem getSolver this vars vars setType SearchStrategyType CUSTOM public StrategyLogVariables Solver solver super solver vars getProblem getVars setType SearchStrategyType CUSTOM public boolean run getProblem log StrategyLogVariables getProblem log vars return true A user may write in a similar way his her own non search strategy for displaying or saving intermediate search results including application specific objects It is important to define a strategy type as SearchStrategyType CUSTOM Variable Selectors The JSR 331 specifies a set of standard variable selectors that can be used by an end user to customize the standard search strategy These variable selectors are defined by the standard interface VariableSelector using the following enum static public enum VarSelectorType f k selection of variables in order of definition y IN
71. trategy The optimization process can be controlled by Optimization Tolerance that is a difference between solution objectives during two consecutive process iterations see the method setOptimizationTolerance MaxNumberOfSolutions that is the total number of considered solutions may be limited by the method setMaxNumberOfSolutions TimeLimit that is the total number of milliseconds allocated for the entire optimization process as it can be set by the method setTimeLimit The problem state after the execution of this method is always restored The produced optimal solution if any will contain found values for all variables that were added to the problem including the objectiveVar public Solution findOptimalSolution Var objectiveVar This method is an equivalent of findOptimalSolution Objective MINIMIZE objectiveVar Common CP solver Common or CP solver Common 38 JSR 331 Constraint Programming API public Solution findAllSolutions This method attempts to find all solutions for the Problem It uses the default search strategy or the strategy defined by the latest method setSearchStrategy It returns an array of found solutions or null if there are no solutions user has to be careful not to overload the available memory because the number of found solutions could be huge The process of finding all solutions can be also controlled by Optimization Tolerance t
72. ts A 28 All Different Constraint spcrn raan sis ERR ER CER EFE FEIRN E KEEPER R ge Pee UP LEERE 29 Element Constraints E 30 Cardinality Constr Antee C oie tereti fami ttti td debate te e Eds 31 Global Cardinality Constraints eene nee entree 32 Min Max Constraints D e iiras 33 More Constraints user enre r E E EAE A ER REO TENi 33 User Defined Constraints dice Er Eri Ede e AERE ERE R EE SPERO ERR Perside erbe RN EEE 34 Example SEND MORE MONBY iiie e taret ene ainai 35 Problem Resolution Concepts nee entere nnns en nenr nnne nennen nnns 36 Intertace DOIVE airite iiaee aT X reo eo Mesi oer eset eee unie re Meet freer esI Menard 37 Example of Constraint Relaxation Problem 0 cccccccsccccccessessseceeececeesesssaeceeeeeceesertssseeeees 41 Interface Search Strategy Leod ec er IP rr VU o VE roO ORAE esce rr a Perder os 42 irate sy Execution Listons an N oletec nita ene ceti tec hti tree aul oiseau dodo 43 Adding Non Se arch S6rateses erectio tee eerte Pete eter dove A e tere boni 44 VarapbleSelectoES 3 00915005 caf cheese GROUP TENE STIR E te tutes ya TUE Pe ees seas RENE EE cede tine eiue ease te 45 Value S Cle C6OIS xe tas cases 47 Moreeasch Dibdtebie8 soar pide c ERA Ere E inc a a rte sec Ennio cer aran e ai 49 Tutertaee Solution soiminen i ar Ea Y oua e E FERNER ORGPIFIENU Cete NA PYEERENOR PO PPS EREDE 49 Solu
73. ution This method attempts to find a solution of the problem for which the solver was defined It uses the default search strategy or the strategy defined by the latest method setSearchStrategy It returns the found solution if any or null If a solution is found all decision variables will remain instantiated with the solution values after the execution of this method If a solution was not found the problem state will be restored public Solution findSolution ProblemState restoreOrNot This method attempts to find a feasible solution of the problem for which the solver was defined It uses the default search strategy or the strategy defined by the latest method setSearchStrategy It returns the found solution if any or null If a solution is not found the problem state is restored If a solution is found the problem state will be restored only if the parameter restoreOrNot is RESTORE If the parameter restoreOrNot is DO_NOT_RESTORE after a solution is found all decision variables will be instantiated with the solution values public Solution findOptimalSolution Objectiv objective Var objectiveVar This method attempts to find the solution that minimizes maximizes the objective variable objectiveVar The first parameter could have one of two values Objective MINIMIZE or Objective MAXIMIZE To find solutions this method uses the default search strategy or the strategy defined by the latest method setSearchS
74. ution findAllSolutions and by solution iterators public SearchStrategy newSearchStrategy This method returns a new instance of the search strategy that is set by an implementation as the default search strategy A user may adjust this search strategy by changing its default decision variables its variable selector and or its value selector This new strategy may be added to the strategy execution list using the Solver s method addStrategy public void addSearchStrategy SearchStrategy strategy This method adds the strategy to the end of the strategy execution list public void addStrategyLogVariables This method adds the strategy that logs all constrained integer variables Common or CP solver Common or CP solver Common Common CP solver CP solver Common 39 JSR 331 Constraint Programming API public void setMaxNumberOfSolutions int number Common This method sets a limit for a number of solutions that can be found by the method indAllSolutions orcan be considered during execution of the method findOptimalSolution The default value is 1 that means there are no limits for a number of considered solutions public int getMaxNumberOfSolutions Common This method returns a number that was set by the method setMaxNumberOfSolutions public void setOptimizationTolerance int tolerance Common This method specifies a tolerance for the method findOp
75. y 2 z X Y 2 p postAllDifferent vars inti coefl 3 4 7 2 p post coefl vars 0 3x 4y 7z 2r gt 0 catch Exception e p log Error posting constraint e System exit 1 The standard allows a user to control the propagation strength of different constraints using an additional posting parameter in this method void post ConsistencyLevel consistencyLevel Here the ConsistencyLevel is defined as the following standard enum public enum ConsistencyLevel BOUND bound consistency DOMAIN domain consistency VALUE value consistency OTHER implementation specific consistency The JSR 331 does not enforce any particular consistency level leaving this decision to implementers of different constraints Note that the common implementation simply ignores the consistency level resulting in this method being equivalent to the regular post Example of a Problem with Various Constraints Usually application developers incorporate constrained variables in their own business objects and post constraints between them to express business relationships between yet unknown entities Let s consider a popular problem given a supply of different components and bins of given types determine all assignments of components to bins 26 JSR 331 Constraint Programming API satisfying specified assignment constraints subject to an optimization criterion Here is a fragment of the business obj
76. z lt 3 r It is assumed that all solver variables 1n the expression were previously created under names used optional within this expression The method adds this constraint to the problem and returns the newly added Constraint This method throws a RuntimeException if there is either an error inside the symbolicExpression or there is no implementation for this method The Problem methods that create concrete constraints such as Linear Element AllDifferent Cardinality and GlobalCardinality are described below 250 JSR 331 Constraint Programming API Posting Constraints A constraint has no effect until it is posted The constraint posting is implementation specific but usually it executes the following actions 1 Initial constraint propagation if any as defined by the common or solver specific implementation 2 Associating constraints or their propagators listeners observers different implementations use different terms with the involved constrained variables and events When such events occur the proper propagators will be woke up and executed to remove inconsistent values from the variable domains The actual posting logic depends on an underlying CP solver If the posting was unsuccessful the method post throws a runtime exception So it should be a regular practice to put constraint posting into a try catch block e g try p post x y Jf 3 XY p post x plus

JSR-331 User Manual

Contents

Download Pdf Manuals

Related Search

Related Contents