Other brand and product names are trademarks of their respective companies. Contents



Constraint Programming

The correct bibliographic citation for this manual is as follows: SAS Institute Inc. 2004. SAS/OR 9.1 User’s Guide: Constraint Programming. Cary, NC: SAS Institute Inc.

SAS/OR 9.1 User’s Guide: Constraint Programming

Copyright © 2004, SAS Institute Inc., Cary, NC, USA ISBN 1-59047-258-6

All rights reserved. Produced in the United States of America. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, or otherwise, without the prior written permission of the publisher, SAS Institute Inc.

U.S. Government Restricted Rights Notice: Use, duplication, or disclosure of this software and related

documentation by the U.S. government is subject to the Agreement with SAS Institute and the restrictions set forth in FAR 52.227-19, Commercial Computer Software-Restricted Rights (June 1987).

SAS Institute Inc., SAS Campus Drive, Cary, North Carolina 27513.

1st printing, January 2004

SAS Publishing provides a complete selection of books and electronic products to help customers use SAS software to its fullest potential. For more information about our e-books, e-learning products, CDs, and hard-copy books, visit the SAS Publishing Web site at support.sas.com/pubs or call 1-800-727-3228.

®

SASand all other SAS Institute Inc. product or service names are registered trademarks or trademarks of SAS Institute Inc. in the USA and other countries. ® indicates USA registration.

Other brand and product names are trademarks of their respective companies.

Contents

What’sNewinSAS/OR9and9.1.............................Chapter1.TheCLPProcedure..............................

15

SubjectIndex........................................31SyntaxIndex........................................33

iv

Credits

Documentation

WritingEditing

DocumentationSupportTechnicalReview

GehanA.CoreaVirginiaClark

TimArnold,MichelleOpp

EdwardP.Hughes,RadhikaV.Kulkarni,RobPratt

Software

PROCCLP

GehanA.Corea

SupportGroups

SoftwareTestingTechnicalSupport

RobPrattTonyaChapman

vi

󰀁

Credits

What’sNewinSAS/OR9and9.1

Overview

SAS/ORsoftwarecontainsseveralnewandenhancedfeaturessinceSAS8.2.Briefdescriptionsofthenewfeaturesappearinthefollowingsections.Formoreinforma-tion,refertotheSAS/ORdocumentation,whichisnowavailableinthefollowingsixvolumes:

•SAS/ORUser’sGuide:BillsofMaterialProcessing•SAS/ORUser’sGuide:ConstraintProgramming•SAS/ORUser’sGuide:LocalSearchOptimization•SAS/ORUser’sGuide:MathematicalProgramming•SAS/ORUser’sGuide:ProjectManagement•SAS/ORUser’sGuide:TheQSIMApplication

Theonlinehelpcanalsobefoundunderthecorrespondingclassification.

TheBOMProcedure

TheBOMprocedureinSAS/ORUser’sGuide:BillsofMaterialProcessingwasin-troducedinVersion8.2oftheSASSystemtoperformbillofmaterialprocessing.Severalnewfeatureshavebeenaddedtotheprocedure,enablingittoreadallproductstructurerecordsfromaproductstructuredatafileandallpart“master”recordsfromapartmasterfile,andcomposethecombinedinformationintoindentedbillsofmate-rial.Thisdatastructuremirrorsthemostcommonmethodforstoringbill-of-materialdatainenterprisesettings;thepartmasterfilecontainsdataoneachpartwhiletheproductstructurefileholdsdatadescribingthevariouspart-componentrelationshipsrepresentedinbillsofmaterial.

ThePMDATA=optiononthePROCBOMstatementenablesyoutospecifythenameofthePartMasterdataset.Ifyoudonotspecifythisoption,PROCBOMusestheProductStructuredataset(asspecifiedintheDATA=option)asthePartMasterdataset.TheBOMprocedurenowlooksupthePart,LeadTime,Requirement,QtyOnHand,andIDvariablesinthePartMasterdataset.Ontheotherhand,theComponentandQuantityvariablesremainintheProductStructuredataset.YoucanusetheNRELATIONSHIPS=(orNRELTS=)optiontospecifythenumberofparent-componentrelationshipsintheProductStructuredataset.YouhavegreatercontroloverthehandlingofredundantrelationshipsintheProductStructuredatasetusingtheDUPLICATE=option.

2

󰀁

What’sNewinSAS/OR9and9.1

SeveraloptionshavebeenaddedtotheSTRUCTUREstatementenablingyoutospec-ifyinformationrelatedtotheparent-componentrelationships.Inparticular,thevari-ablespecifiedwiththePARENT=optionidentifiestheparentitem,whilethevari-ableslistedintheLTOFFSET=optionspecifylead-timeoffsetinformation.Youcanalsospecifyvariablesidentifyingscrapfactorinformationforallparent-componentrelationshipsusingtheSFACTOR=option.TheRID=optionidentifiesallvariablesintheProductStructuredatasetthataretobeincludedintheIndentedBOMoutputdataset.

TheCLPProcedure(Experimental)

9.1

ThenewCLPprocedureinSAS/ORUser’sGuide:ConstraintProgrammingisanexperimentalfinitedomainconstraintprogrammingsolverforsolvingconstraintsat-isfactionproblems(CSPs)withlinear,logical,global,andschedulingconstraints.InadditiontohavinganexpressivesyntaxforrepresentingCSPs,thesolverfea-turespowerfulbuilt-inconsistencyroutinesandconstraintpropagationalgorithms,achoiceofnondeterministicsearchstrategies,andcontrolsforguidingthesearchmechanismthatenableyoutosolveadiversearrayofcombinatorialproblems.

TheCPMProcedure

TheCPMprocedureinSAS/ORUser’sGuide:ProjectManagementaddsmoreop-tionsfordescribingresourceconsumptionbyactivities,enhancingitsapplicabilitytoproductionschedulingmodels.

Anewkeyword,RESUSAGE,hasbeenaddedtothelistofvaluesfortheOBSTYPEvariableintheResourcedataset.Thiskeywordenablesyoutospecifywhetheraresourceisconsumedatthebeginningorattheendofagivenactivity.

TheMILESTONERESOURCEoptionenablesyoutospecifyanonzerousageofconsumableresourcesformilestoneactivities.Forexample,thisoptionisusefulifyouwishtodesignatespecificmilestonestobethepointsofpaymentforasubcon-tractor.TheMILESTONENORESOURCEoptionisthecurrentdefaultbehavioroftheCPMprocedure,whichindicatesthatallresourcerequirementsaretobeignoredformilestoneactivities.

TheGAProcedure(Experimental)

9.1

ThenewGAprocedureinSAS/ORUser’sGuide:LocalSearchOptimizationfa-cilitatestheapplicationofgeneticalgorithmstogeneraloptimization.Genetical-gorithmsadaptthebiologicalprocessesofnaturalselectionandevolutiontosearchforoptimalsolutions.Theprocedurecanbeappliedtooptimizeproblemsinvolv-inginteger,continuous,binary,orcombinatorialvariables.TheGAprocedureisespeciallyusefulforfindingoptimaforproblemswheretheobjectivefunctionmayhavediscontinuitiesormaynototherwisebesuitableforoptimizationbytraditionalcalculus-basedmethods.

What’sNewinSAS/OR9and9.1

󰀁

3

TheGANTTProcedure

TheGANTTprocedureinSAS/ORUser’sGuide:ProjectManagementincludesanewoptionforcontrollingthewidthoftheGanttchart.TheCHARTWIDTH=optionspecifiesthewidthoftheaxisareaasapercentageofthetotalGanttchartwidth.ThisoptionenablesyoutogenerateGanttchartsthatareconsistentinappearance,independentofthetotaltimespannedbytheproject.

TheLPProcedure

TheperformancesofprimalanddualsimplexalgorithmsintheLPprocedure(SAS/ORUser’sGuide:MathematicalProgramming)havebeensignificantlyim-provedonlargescalelinearormixedintegerprogrammingproblems.

ThePMProcedure

ThenewoptionsaddedtotheCPMprocedurearealsoavailablewithPROCPM.

TheQPProcedure(Experimental)

ThenewQPprocedureinSAS/ORUser’sGuide:MathematicalProgrammingim-plementsaprimal-dualpredictor-correctorinterior-pointalgorithmforlargesparsequadraticprograms.DependingonthedistributionoftheeigenvaluesoftheHessianmatrix,H,twomainclassesofquadraticprogramsaredistinguished(assumingmin-imization):

•convex:Hispositivesemi-definite

•nonconvex:Hhasatleastonenegativeeigenvalue

DiagonalandnonseparableHessianmatricesarerecognizedandhandledautomati-cally.

9.1

BillofMaterialPostProcessingMacros

SeveralmacrosenableuserstogeneratemiscellaneousreportsusingtheIndentedBOMoutputdatasetfromtheBOMprocedureinSAS/ORUser’sGuide:BillsofMaterialProcessing.Othertransactionalmacrosperformspecializedtransactionsformaintainingandupdatingthebillsofmaterialforaproduct,productline,plant,orcompany.

4

󰀁

What’sNewinSAS/OR9and9.1

Chapter1

TheCLPProcedure(Experimental)

ChapterContents

OVERVIEW..............TheConstraintSatisfactionProblemTechniquesforSolvingCSPs....TheCLPProcedure.........

....................................................................................

7789

INTRODUCTORYEXAMPLES........................11SendMoreMoney...............................11EightQueens..................................11SYNTAX.........FunctionalSummary..PROCCLPStatement.ACTIVITYStatement.ALLDIFFStatement..ARRAYStatement...FOREACHStatement.LINCONStatement..REIFYStatement...REQUIRESStatement.RESOURCEStatementSCHEDULEStatementVARStatement....DETAILS.......ModesofOperationActivityDataSet..ScheduleDataSet.ConstraintDataSetSolutionDataSet.

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................13141517181919192021212223242424262728

REFERENCES..................................29

6

󰀁

Chapter1.TheCLPProcedure(Experimental)

Chapter1

TheCLPProcedure(Experimental)

Overview

TheCLPprocedureisafinitedomainconstraintprogrammingsolverforconstraintsatisfactionproblems(CSPs)withlinear,logical,global,andschedulingconstraints.InadditiontohavinganexpressivesyntaxforrepresentingCSPs,thesolverfea-turespowerfulbuilt-inconsistencyroutinesandconstraintpropagationalgorithms,achoiceofnondeterministicsearchstrategies,andcontrolsforguidingthesearchmechanismthatenableyoutosolveadiversearrayofcombinatorialproblems.Forthemostrecentupdatestothedocumentationforthisexperimentalpro-cedure,seetheStatisticsandOperationsResearchDocumentationpageathttp://support.sas.com/rnd/app/doc.html.

TheConstraintSatisfactionProblem

ManyimportantproblemsinareassuchasArtificialIntelligence(AI)andOperationsResearch(OR)canbeformulatedasconstraintsatisfactionproblems.ACSPisde-finedbyafinitesetofvariablestakingvaluesfromfinitedomainsandafinitesetofconstraintsrestrictingthevaluesthevariablescansimultaneouslytake.Moreformally,aCSPcanbedefinedasatriple󰀌X,D,C󰀍where

•X={x1,...,xn}isafinitesetofvariables.

•D={D1,...,Dn}isafinitesetofdomains,whereDiisafinitesetofpossi-blevaluesthatthevariablexicantake.Diisknownasthedomainofvariablexi.•C={c1,...,cm}isafinitesetofconstraintsrestrictingthevaluesthatthevariablescansimultaneouslytake.Notethatthedomainsneednotrepresentconsecutiveintegers.Forexample,thedomainofavariablecouldbethesetofallevennumbersintheinterval[0,100].Adomaindoesnotevenneedtobetotallynumeric.Infact,inaschedulingproblemwithresources,thevaluesaretypicallymultidimensional.Forexample,anactivitycanbeconsideredasavariableandeachelementofthedomainwouldbeann-tuplethatrepresentsastarttimefortheactivityaswellastheresource(s)thatmustbeassignedtotheactivitycorrespondingtothestarttime.

AsolutiontoaCSPisanassignmentofvaluestothevariablesinordertosatisfyalltheconstraints,andtheproblemamountstofindingsolution(s),orpossiblydetermin-ingthatasolutiondoesnotexist.

8

󰀁

Chapter1.TheCLPProcedure(Experimental)

TheCLPprocedurecanbeusedtofindoneormore(andinsomeinstances,all)so-lutionstoaCSPwithlinear,logical,global,andschedulingconstraints.Thenumericcomponentsofallvariabledomainsareassumedtobeintegers.

TechniquesforSolvingCSPs

SeveraltechniquesforsolvingCSPsareavailable.Kumar(1992)andTsang(1993)presentagoodoverviewofthesetechniques.

ItshouldbenotedthattheSatisfiabilityproblem(SAT)(GareyandJohnson1979)canberegardedasaCSP.Consequently,mostproblemsinthisclassareNP-completeproblems,andabacktrackingsearchisanimportanttechniqueforsolvingthem(Floyd1967).However,abacktrackingapproachisnotveryefficientduetothelatedetectionofconflicts;thatis,itisorientedtowardrecoveringfromfailuresandnotavoidingthemtobeginwith.Thesearchspaceisreducedonlyafterdetectionofafailure,andtheperformanceofthistechniquedrasticallyreduceswithincreasingproblemsize.

ConstraintPropagation

Amoreefficienttechniqueisthatofconstraintpropagation,whichusesconsistencytechniquestoeffectivelyprunethedomainsofvariables.Consistencytechniquesarealsoknownasrelaxationalgorithms(Tsang1993)andtheprocessisalsoreferredtoasproblemreduction,domainfiltering,orpruning.TheresearchonconsistencytechniquesoriginatedwiththeWaltzfilteringalgorithm(Waltz1975).Constraintpropagationischaracterizedbytheextentofpropagation(alsoreferredtoasthelevelofconsistency)andthedomainpruningschemethatisfollowed—domainprop-agationorintervalpropagation.Inpractice,intervalpropagationispreferredoverdomainpropagationduetoitslowercomputationalcosts.Thismechanismisdis-cussedindetailinVanHentenryck(1989).However,constraintpropagationisnotacompletesolutiontechniqueandneedstobecomplementedbyasearchtechniquetoensuresuccess(Kumar1992).

FiniteDomainConstraintProgramming

Finitedomainconstraintprogrammingisaneffectiveandcompletesolutiontech-niquethatembedsincompleteconstraintpropagationtechniquesintoanondetermin-isticbacktrackingsearchmechanism,implementedasfollows.Wheneveranodeisvisited,constraintpropagationiscarriedouttoattainadesiredlevelofconsistency.Ifthedomainofeachvariablereducestoasingletonset,thenoderepresentsasolutiontotheCSP.Ifthedomainofavariablebecomesempty,thenodeispruned.Otherwiseavariableisselected,itsdomaindistributed,andanewsetofCSPsgenerated,eachofwhichisachildnodeofthecurrentnode.Severalfactorsplayaroleindetermin-ingtheoutcomeofthismechanism,suchastheextentofpropagation(orlevelofconsistencyenforced),thevariableselectionstrategy,andthevariableassignmentordomaindistributionstrategy.

Forexample,thelackofanypropagationreducesthistechniquetoasimplegener-ateandtest,whereasperformingconsistencyonvariablesalreadyselectedreducesthistochronologicalbacktracking,oneofthesystematicsearchtechniques.These

TheCLPProcedure

arealsoknownaslook-backschemasastheysharethedisadvantageoflateconflictdetection.Look-aheadschemas,ontheotherhand,worktopreventfutureconflicts.Somepopularexamplesoflook-aheadstrategiesinincreasingdegreeofconsistencylevelareForwardChecking(FC),PartialLookAhead(PLA),andFullLookAhead(LA)(Kumar1992).ForwardCheckingenforcesconsistencybetweenthecurrentvariableandfuturevariables;PLAandLAextendthisevenfurthertopairsofnotyetinstantiatedvariables.

Twoimportantconsequencesofthistechniquearethatinconsistenciesarediscoveredearlyonandthatthecurrentsetofalternativescoherentwiththeexistingpartialsolutionisdynamicallymaintained.Theseconsequencesarepowerfulenoughtoprunelargepartsofthesearchtree,therebyreducingthe“combinatorialexplosion”ofthesearchprocess.However,althoughconstraintpropagationateachnoderesultsinfewernodesinthesearchtree,theprocessingateachnodeismoreexpensive.Theidealscenarioistostrikeabalancebetweentheextentofpropagationandthesubsequentcomputationcost.

Variableselectionisanotherstrategythatcanaffectthesolutionprocess.Theorderinwhichvariablesarechosenforinstantiationcanhavesubstantialimpactonthecom-plexityofthebacktracksearch.Severalheuristicshavebeendevelopedandanalyzedforselectingvariableordering.Oneofthemorecommononesisadynamicheuristicbasedonthefailfirstprinciple(HaralickandElliot1980),whichselectsthevari-ablewhosedomainhasminimalsize.Subsequentanalysisofthisheuristicbyseveralresearchershasvalidatedthistechniqueasprovidingsubstantialimprovementforasignificantclassofproblems.Anotherpopulartechniqueistoinstantiatethemostconstrainedvariablefirst.Boththesestrategiesarebasedontheprincipleofselectingthevariablemostlikelytofailandtodetectsuchfailuresasearlyaspossible.Thedomaindistributionstrategyforaselectedvariableisyetanotherareathatcaninfluencetheperformanceofabacktrackingsearch.However,goodvalueorderingheuristicsareexpectedtobeveryproblem-specific(Kumar1992).

󰀁

9

TheCLPProcedure

TheCLPprocedureisafinitedomainconstraintprogrammingsolverforCSPs.InthecontextoftheCLPprocedure,CSPscanbeclassifiedintotwotypes:standardCSPsandschedulingCSPs.AstandardCSPischaracterizedbyintegervariables,linearconstraints,arraytypeconstraints,globalconstraints,andreifiedconstraints.Inotherwords,Xisafinitesetofintegervariables,andCcancontainlinear,ar-ray,global,orlogicalconstraints.AschedulingCSPischaracterizedbyactivities,temporalconstraints,andresourcerequirementconstraints.Inotherwords,Xisafinitesetofactivities,andCisasetoftemporalconstraintsandresourcerequirementconstraints.TheCSPtypeisindicatedbyspecifyingeithertheOUT=optionortheSCHEDDATA=optioninthePROCCLPstatement.

SpecificationoftheOUT=optioninthePROCCLPstatementindicatestotheCLPprocedurethattheCSPisastandardtype.Assuch,theprocedurewillexpectVAR,LINCON,REIFY,ALLDIFF,ARRAY,andFOREACHstatements.YoucanalsospecifyaProblemdatasetusingtheDATA=optioninthePROCCLPstatementinlieuof,orincombinationwith,VARandLINCONstatements.

10

󰀁

Chapter1.TheCLPProcedure(Experimental)

SpecificationoftheSCHEDDATA=optioninthePROCCLPstatementindicatestotheCLPprocedurethattheCSPisaschedulingtype.Assuch,theprocedurewillexpectACTIVITY,RESOURCE,REQUIRES,andSCHEDULEstatements.YoucanalsospecifyanActivitydatasetusingtheACTDATA=optioninthePROCCLPstatementinlieuof,orincombinationwith,theACTIVITYandLINCONstatements.PrecedencerelationshipsbetweenactivitiesmustbedefinedusingtheACTDATA=dataset.ResourcerequirementsofactivitiesmustbedefinedusingtheRESOURCEandREQUIRESstatements.

TheoutputdatasetcontainsanysolutionsdeterminedbytheCLPprocedure.Formoreinformationontheformatandlayout,seethe“Details”sectiononpage24.

ConsistencyTechniques

TheCLPprocedurefeaturesaFullLook-AheadalgorithmforstandardCSPsthatfollowsastrategyofmaintainingaversionofGeneralizedArcConsistencythatisbasedontheAC-3Consistencyroutine(Mackworth1977).Thisstrategymain-tainsconsistencybetweentheselectedvariableandtheunassignedvariablesandalsomaintainsconsistencybetweenunassignedvariables.FortheschedulingCSPs,theCLPprocedureusesaForwardCheckingalgorithm,anarc-consistencyroutineformaintainingconsistencybetweenunassignedactivities,andenergetic-basedreason-ingmethodsforresource-constrainedschedulingthatfeaturetheEdgeFinderalgo-rithm(ApplegateandCook1991).Youcanelecttoturnoffsomeoftheseconsistencytechniquesintheinterestofperformance.

SelectionStrategy

AsearchalgorithmforCSPssearchessystematicallythroughthepossibleassign-mentsofvaluestovariables.Theorderinwhichavariableisselectedcanbebasedonastaticordering,whichisdeterminedbeforethesearchbegins,oronadynamicordering,inwhichthechoiceofthenextvariabledependsonthecurrentstateofthesearch.TheVARSELECT=optioninthePROCCLPstatementdefinesthevariableselectionstrategyforastandardCSP.ThedefaultstrategyisthedynamicMINRstrat-egy,whichselectsthevariablewiththesmallestrange.TheACTSELECT=optionintheSCHEDULEstatementdefinestheactivityselectionstrategyforaschedulingCSP.ThedefaultstrategyistheRANDstrategy,whichselectsanactivityatrandomfromthesetofactivitiesthatbeginpriortotheearliestearlyfinishtime.ThisstrategywasproposedbyNuijten(1994).

AssignmentStrategy

Onceavariableoranactivityhasbeenselected,theassignmentstrategydictatesthevaluethatisassignedtoit.Forvariables,theassignmentstrategyisspecifiedwiththeVARASSIGN=optioninthePROCCLPstatement.Thedefaultassignmentstrategyselectstheminimumvaluefromthedomainoftheselectedvariable.Foractivities,theassignmentstrategyisspecifiedwiththeACTASSIGN=optionintheSCHEDULEstatement.ThedefaultstrategyofRANDassignsthetimetotheearlieststarttime,andtheresourcesarechosenrandomlyfromthesetofresourceassignmentsthatsupporttheselectedstarttime.

EightQueens

󰀁

11

IntroductoryExamples

Thefollowingexamplesillustratetheformulationandsolutionoftwowell-knownlogicalpuzzlesintheconstraintprogrammingcommunityusingtheCLPprocedure.

SendMoreMoney

TheSendMoreMoneyproblemconsistsoffindinguniquedigitsforthelettersD,E,M,N,O,R,S,andYsuchthatSandMaredifferentfromzero(noleadingzeros)andtheequation

SEND+MORE=MONEY

issatisfied.Theuniquesolutionoftheproblemis9567+1085=10652.UsingPROCCLP,wecansolvethisproblemasfollows:

procclpdom=[0,9]/*Definethedefaultdomain*/

out=out;/*Nametheoutputdataset*/varSENDMOREMONEY;/*Declarethevariables*/lincon/*Linearconstraints*/

/*SEND+MORE=MONEY*/

1000*S+100*E+10*N+D+1000*M+100*O+10*R+E=

10000*M+1000*O+100*N+10*E+Y,S<>0,/*Noleadingzeros*/M<>0;alldiff();/*Allvariableshavepairwisedistinctvalues*/run;

Obs1S9E5N6D7M1O0R8Y2Figure1.1.SolutiontoSEND+MORE=MONEY

EightQueens

TheEightQueensproblemisaspecialinstanceoftheN-QueensproblemwheretheobjectiveistopositionNqueensonanN×Nchessboardsuchthatnotwoqueensattackeachother.TheCLPprocedureprovidesanexpressiveconstraintforvariablearraysthatcanbeusedforsolvingthisproblemveryefficiently.

Sinceeachqueenmustoccupyadistinctrow,wecanmodelthisusingavariablearrayAofdimensionN,whereA[i]istherownumberofthequeenincolumni.Sincenotwoqueenscanbeonthesamerow,itfollowsthatalltheA[i]’smustbepairwisedistinct.

12

󰀁

Chapter1.TheCLPProcedure(Experimental)

Inordertoensurethatnotwoqueenscanbeonthesamediagonal,wemusthavethefollowingforalliandj:

A[j]−A[i]<>j−iand

A[j]−A[i]<>i−jInotherwords,

A[i]−i<>A[j]−jand

A[i]+i<>A[j]+j

Hence,the(A[i]+i)’sarepairwisedistinct,andthe(A[i]−i)’sarepairwisedistinct.TheCLPprocedurecanbeusedtofindasolutiontothisproblem,asfollows:

procclpout=out

varselect=fifo;/*VariableSelectionStrategy

arrayA[8](A1-A8);/*DefinethearrayAvar(A1-A8)=[1,8];/*Defineeachofthevariablesinthearray

/*Initializedomains

/*A[i]istherownumberofthequeenincolumni*/

foreach(A,DIFF,0);/*A[i]’sarepairwisedistinct*/

foreach(A,DIFF,-1);/*A[i]-i’sarepairwisedistinct*/foreach(A,DIFF,1);/*A[i]+i’sarepairwisedistinct*/run;

*/*/*/*/

Obs1A11A25A38A46A53A67A72A84Figure1.2.ASolutiontotheEightQueensProblem

Syntax

󰀁

13

Figure1.3.ASolutiontotheEightQueensProblem

Syntax

ThefollowingstatementsareusedinPROCCLP:

PROCCLPoptions;

ACTIVITYactivityspecifications;ALLDIFFalldiffconstraints;ARRAYarrayspecifications;FOREACHforeachconstraints;LINCONlinearconstraints;REIFYreifiedconstraints;

REQUIRESresourcerequirementconstraints;RESOURCEresourcespecifications;SCHEDULEscheduleoptions;VARvariablespecifications;

14

󰀁

Chapter1.TheCLPProcedure(Experimental)

FunctionalSummary

ThefollowingtablesoutlinetheoptionsavailablefortheCLPprocedureclassifiedbyfunction.

Table1.1.AssignmentStrategyOptions

Description

activityassignmentstrategyvariableassignmentstrategy

Table1.2.DataSetOptions

StatementSCHEDULEPROCCLPOption

ACTASSIGN=VARASSIGN=

Descriptionactivityinputdatasetprobleminputdatasetsolutionoutputdatasetscheduleoutputdataset

Table1.3.GeneralOptions

StatementPROCCLPPROCCLPPROCCLPPROCCLPOptionACTDATA=DATA=OUT=

SCHEDDATA=

Descriptionsuppresspreprocessing

Table1.4.OutputControlOptions

StatementPROCCLPOptionNOPREPROCESS

Description

findallpossiblesolutionsindicateprogressinlognumberofsolutions

Table1.5.SchedulingCSPStatements

StatementPROCCLPPROCCLPPROCCLPOption

FINDALLSOLNSSHOWPROGRESSSOLNS=

DescriptionactivityspecificationsresourcerequirementspecificationsresourcespecificationsscheduleoptionsStatementACTIVITYREQUIRESRESOURCESCHEDULE

OptionTable1.6.SchedulingTemporalConstraintsOptions

DescriptionactivitydurationactivitystartlowerboundactivitystartupperboundactivityfinishlowerboundactivityfinishupperboundscheduledurationschedulestartschedulefinishStatementACTIVITYACTIVITYACTIVITYACTIVITYACTIVITYSCHEDULESCHEDULESCHEDULEOptionDURATION=SGE=SLE=FGE=FLE=

DURATION=START=FINISH=

PROCCLPStatement

Table1.7.SchedulingSearchControlOptions

󰀁

15

Descriptiondeadendmultipliernumberofallowabledeadendsperrestartnumberofsearchrestarts

edgefinderconsistencyroutine

Table1.8.SelectionStrategyOptions

StatementPROCCLPPROCCLPPROCCLPSCHEDULEOptionDEM=DEPR=

RESTARTS=EF

Descriptionactivityselectionstrategyvariableselectionstrategy

Table1.9.StandardCSPStatements

StatementSCHEDULEPROCCLPOptionACTSELECT=VARSELECT=

DescriptionalldifferentconstraintsarrayspecificationsforeachconstraintslinearconstraintsreifiedconstraintsvariablespecificationsStatementALLDIFFARRAYFOREACHLINCONREIFYVAR

OptionPROCCLPStatement

PROCCLPoptions;

ThefollowingoptionscanappearinthePROCCLPstatement.

ACTDATA=SAS-data-setACTIVITY=SAS-data-set

identifiestheinputdatasetthatdefinestheactivitiesandtemporalconstraints.Thetemporalconstraintsconsistoftimealignmenttypeconstraintsandprecedencetypeconstraints.TheformatoftheACTDATA=datasetissimilartotheActivitydatasetusedbytheCPMprocedureinSAS/ORsoftware.TheactivitiesandtimealignmentconstraintscanalsobedirectlyspecifiedusingtheACTIVITYstatementwithouttheneedforadataset.TheCLPprocedureenablesyoutodefineactivitiesusingacombinationofthetwospecifications.

DATA=SAS-data-set

identifiestheinputdatasetthatdefinesthelinearconstraints.TheformatoftheDATA=datasetissimilartothatusedbytheLPprocedureinSAS/ORsoftware.ThelinearconstraintscanalsobespecifiedinlineusingtheLINCONstatement.TheCLPprocedureenablesyoutodefinelinearconstraintsusingacombinationofthetwospecifications.Whendefininglinearconstraints,youmustdefinethestructuralvariablesusingaVARstatement.

DEM=d

specifiesthedeadendmultiplierfortheCSP.Thedeadendmultiplierisusedtodeter-minethenumberofdeadendsthatarepermittedbeforetriggeringacompleterestart

16

󰀁

Chapter1.TheCLPProcedure(Experimental)

ofthesearchtechniqueinaschedulingenvironment.Thenumberofdeadendsistheproductofthedeadendmultiplierandthenumberofunassignedactivities.Thedefaultvalueis0.15.ThisoptionisvalidonlywiththeSCHEDDATA=option.

DEPR=n

specifiesthenumberofdeadendsthatarepermittedbeforePROCCLPrestartsorterminatesthesearch,dependingonwhetherornotarandomizedsearchstrategyisused.Inthecaseofanonrandomizedstrategy,nisanupperboundonthenumberofallowabledeadendsbeforeterminating.Inthecaseofarandomizedstrategy,nisanupperboundonthenumberofallowabledeadendsbeforerestartingthesearch.TheDEPR=optionhaspriorityovertheDEM=option.ThedefaultvalueoftheDEPR=optionis∞.

DOMAIN=[lb,ub]DOM=[lb,ub]

specifiestheglobaldomainofallvariablestobetheclosedinterval[lb,ub].YoucanoverridetheglobaldomainforavariablewithaVARstatementortheDATA=dataset.

FINDALLSOLNSALLSOLNSFAS

FINDALL

attemptstofindallpossiblesolutionstotheCSP.Whenarandomizedsearchstrat-egyisused,itispossibletorediscoverthesamesolutionandendupwithmultipleinstancesofthesamesolution.Thisiscurrentlythecasewhensolvingscheduling-relatedproblems.Therefore,thisoptionisignoredwhensolvingascheduling-relatedproblem.

NOPREPROCESS

suppressesanypreprocessingthatwouldtypicallybeperformedfortheproblem.

OUT=SAS-data-set

identifiestheoutputdatasetthatcontainsthesolution(s)totheCSP,ifanyexist.EachobservationintheOUT=datasetcorrespondstoasolutionoftheCSP.ThenumberofsolutionsgeneratedcanbecontrolledusingtheSOLNS=optioninthePROCCLPstatement.

RESTARTS=n

specifiesthenumberofrestartsoftherandomizedsearchtechniquebeforeterminat-ingtheprocedure.Thedefaultvalueis3.

SCHEDDATA=SAS-data-setSCHEDULE=SAS-data-set

identifiestheoutputdatasetthatcontainsthescheduling-relatedsolutiontotheCSP,ifoneexists.EachobservationintheSCHEDDATA=datasetcorrespondstoanactivity.Theformatofthescheduledatasetissimilartothescheduledatasetgener-atedbytheCPMandPMproceduresinSAS/ORsoftware.ThenumberofsolutionsgeneratedcanbecontrolledusingtheSOLNS=optioninthePROCCLPstatement.

ACTIVITYStatement

SHOWPROGRESS

󰀁

17

printsamessagetothelogwheneverasolutionhasbeenfound.Whenarandomizedstrategyisused,thenumberofrestartsanddeadendsthatwererequiredarealsoprintedtothelog.

SOLNS=n

specifiesthenumberofsolutionattemptstobegeneratedfortheCSP.Thedefaultvalueis1.Itisimportanttonote,especiallyinthecontextofrandomizedstrategies,thatanattemptcouldresultinnosolution,giventhecurrentcontrolsonthesearchmechanism,suchasthenumberofrestartsandthenumberofdeadendspermitted.Asaresult,thetotalnumberofsolutionsfoundmaynotmatchtheSOLNS=parameter.

VARASSIGN=keywordVALSELECT=keyword

specifiesthevalueselectionstrategy.Currentlythereisonlyonevalueselectionstrat-egy.TheMINstrategyselectstheminimumvaluefromthedomainoftheselectedvariable.Toassignactivities,usetheACTASSIGN=optionintheSCHEDULEstate-ment.

VARSELECT=keyword

specifiesthevariableselectionstrategy.Bothstaticanddynamicstrategiesareavail-able.Possiblevaluesareasfollows.Staticstrategies:

•FIFO:UsestheFirst-In-First-Outorderingofthevariablesasencounteredbytheprocedure.

•MAXCS:Selectsthevariablewiththemaximumnumberofconstraints.Dynamicstrategies:

•MINR:Selectsthevariablewiththesmallestrange(thatis,theminimumvalueofupperboundminuslowerbound).•MAXC:Selectsthevariablewiththelargestnumberofactiveconstraints.•MINRMAXC:Selectsthevariablewiththesmallestrange,breakingtiesbyselectingtheonewiththelargestnumberofactiveconstraints.Thedynamicstrategiesembodythe“FailFirstPrinciple”(FFP)ofHaralickandElliot(1980),whichsuggeststhat“Tosucceed,tryfirstwhereyouaremostlikelytofail.”ThedefaultstrategyisMINR.Toselectactivities,usetheACTSELECT=optionintheSCHEDULEstatement.

ACTIVITYStatement

ACTIVITYactivity<=(dur[altype=aldate...])>;

ACTIVITY(activity–list)<=(dur[altype=aldate...])>;

whereduristheactivitydurationandaltypeisakeywordspecifyinganalignmenttypeconstraintontheactivity(oractivities)withrespecttothedategivenbyaldate.

18

󰀁

Chapter1.TheCLPProcedure(Experimental)

TheACTIVITYstatementdefinesoneormoreactivitiesandtheattributesofeachactivity,suchasthedurationandanytemporalconstraintsofthetimealignmenttype.Thedefaultdurationis1.

Validvaluesforthealtypekeywordareasfollows:

•SGE:Startgreaterthanorequaltoaldate•SLE:Startlessthanorequaltoaldate•FGE:Finishgreaterthanorequaltoaldate•FLE:Finishlessthanorequaltoaldate

Youcanspecifyanycombinationoftheabovekeywords.Forexample,todefineanactivityAwithduration3andtosetthestarttimeofactivityAequalto10,youwouldspecifythefollowing:

activityA=(dur=3sge=10sle=10);

YoucanalternativelyusetheACTDATA=datasettodefinetheactivities,durations,andtemporalconstraints.Infact,youcanspecifybothanACTIVITYstatementandanACTDATA=dataset.YoumustuseanACTDATA=datasettodefineprecedence-relatedtemporalconstraints.TheSCHEDDATA=optionmustbespecifiedwhentheACTIVITYstatementisused.

ALLDIFFStatement

ALLDIFF(variables)...;

ALLDIFFERENT(variables)...;

TheALLDIFFstatementcanhavemultiplespecifications.Eachspecificationdefinesauniqueglobalconstraintonasetofvariablesrequiringallofthemtobedifferentfromeachother.Aglobalconstraintisequivalenttoaconjunctionofelementaryconstraints.

Forexample,thestatements

var(X1-X3)AB;

alldiff(X1-X3)(AB);

areequivalentto

X1=X2X2=X3X1=X3A=B

LINCONStatement

󰀁

19

ARRAYStatement

ARRAYarrayspec[,arrayspec...];

wherearrayspec:=arrayname[dimensions](variables);

TheARRAYstatementisusedtoassociateanamewithalistofvariables.EachofthevariablesinthevariablelistmustbedefinedusingaVARstatement.TheARRAYstatementisrequiredwhenspecifyingaFOREACHtypeconstraint.

FOREACHStatement

FOREACH(array,type,>);

wherearraymustbedefinedusinganARRAYstatement,typeisakeywordthatdeterminesthetypeoftheconstraint,andoffsetandconstantareintegers.

TheFOREACHstatementiterativelyappliesaconstraintoveranarrayofvariables.Thetypeoftheconstraintisdeterminedbytype.Theoptionaloffsetandconstantparametersareintegersandareinterpretedinthecontextoftheconstrainttype.Currently,theonlyvalidvaluefortypeisDIFF.

TheFOREACHstatementcorrespondingtotheDIFFkeyworditerativelyappliesthefollowingconstrainttoeachpairofvariablesinthearray:

A[i]+offset×i=A[j]+offset×j

∀i=j,i,j=1,...,m

Forexample,theconstraintthatall(A[i]−i)’sarepairwisedistinctforanarrayAisexpressedas

foreach(A,diff,-1);

LINCONStatement

LINCONl–con[,l–con...];LINEARl–con[,l–con...];

wherel–con:=linear–termoperatorlinear–term

linear–termisofthefollowingform:

((<+|−>variable|number<∗variable>)...)

operatorcanbeoneofthefollowing:

≤,<,=,==,≥,>,<>,LE,EQ,GE,LT,GT,NE

20

󰀁

Chapter1.TheCLPProcedure(Experimental)

TheLINCONstatementallowsforaverygeneralspecificationoflinearconstraints.Inparticular,itallowsforspecificationofthefollowingtypesofequalityorinequalityconstraints:

n󰀁j=1

aijxj{≤|<|=|≥|>|=}bi

fori=1,...,m

Forexample,theconstraint4x1−3x2=5isexpressedas

varx1x2;

lincon4*x1-3*x2=5;

andtheconstraints

10x1−x2≥10x1+5x2=15

areexpressedas

varx1x2;

lincon10<=10*x1-x2,

x1+5*x2<>15;

NotethatvariablescanbespecifiedoneithersideofanequalityorinequalityinaLINCONstatement.LinearconstraintscanalsobespecifiedusingtheDATA=dataset.WhenusingaLINCONstatement,youmustdefinethevariablesusingaVARstatement.

REIFYStatement

REIFYvariable:(l–con)...;

wherel–con:=linear–termoperatorlinear–term

linear–termisofthefollowingform:

((<+|−>variable|number<∗variable>)...)

operatorcanbeoneofthefollowing:

≤,<,=,==,≥,>,<>,LE,EQ,GE,LT,GT,NE

TheREIFYstatementassociatesabinaryvariablewithalinearconstraint.Thevalueofthebinaryvariableis1or0dependingonwhetherthelinearconstraintissatisfiedornot,respectively.Thelinearconstrainthasbeenreified,andthelogicalvariableisreferredtoasthecontrolvariable.Aswiththeothervariables,thecontrolvariablemustalsobedefinedinaVARstatementorintheDATA=dataset.

RESOURCEStatement

TheREIFYstatementprovidesaconvenientmechanismforexpressinglogicalcon-straints,suchasdisjunctiveandimplicativeconstraints.Forexample,thedisjunctiveconstraint

(3x+4y<20)∨(5x−2y>50)canbeexpressedwiththefollowingstatements:

varxypq;

reifyp:(3*x+4*y>20)q:(5*x-2*y)>50);linconp+q>=1;

󰀁

21

TheREIFYconstraintcanalsobeusedtoexpressaconstraintinvolvingtheabsolutevalueofavariable.Forexample,theconstraint

|X|=5

canbeexpressedwiththefollowingstatements:

varxpq;

reifyp:(x=5)q:(x=-5);linconp+q=1;

REQUIRESStatement

REQUIRESactivity–spec=(assignment–spec[,assignment–set–spec...]);REQactivity–spec=(assignment–spec[,assignment–set–spec...]);whereactivity–spec:=activityor(activity–list)

andassignment–spec:=resourceor(resource–list)

TheREQUIRESstatementdefinesthepotentialactivityassignmentswithrespecttothepoolofresources.Forexample,thefollowingstatementsspecifythatactivityArequiresresourcesR1andR2simultaneouslyorresourcesR3andR4simultaneously.

activityA;

resourceR1-R4;

requiresA=((R1R2),(R3R4));

RESOURCEStatement

RESOURCE(resource–spec)...;RES(resource–spec)...;

whereresource–specisresourceor(resourcelist)

TheRESOURCEstatementspecifiesthenamesofallresourcesthatareavailabletobeallocatedtotheactivities.TheREQUIRESstatementisnecessarytospecifytheresourcerequirementsofanactivity.Currentlyallresourcesareassumedtobeunaryresourcesinthattheircapacityisequalto1andtheymaynotbeassignedtomorethanoneactivityatanygiventime.

22

󰀁

Chapter1.TheCLPProcedure(Experimental)

SCHEDULEStatement

SCHEDULEoptions;

ThefollowingoptionscanappearintheSCHEDULEstatement.

ACTASSIGN=keyword

ACTVALSELECT=keyword

specifiestheactivityassignmentstrategy.Thepossibleactivityassignmentstrategiesareasfollows:

•RAND:Assigntheactivitytostartatitsearliestpossiblestarttime.Iftheactiv-ityhasanyresourcerequirements,thenrandomlyselectaresourcerequirementfromthesetofresourcerequirementsthatsupporttheselectedstarttimefortheactivity.Assigntheactivitytotheresourcesspecifiedinthisrequirement.•MAXLS:Assigntheactivitytostartatitsearliestpossiblestarttime.Iftheactivityhasanyresourcerequirements,thenselecttheresourcerequirementwiththelateststarttimefromthesetofresourcerequirementsthatsupporttheselectedstarttimefortheactivity.Assigntheactivitytotheresourcesspecifiedinthisrequirement.ThedefaultstrategyisRAND.Forassigningvariables,usetheVARASSIGN=optioninthePROCCLPstatement.

ACTSELECT=keyword

specifiestheactivityselectionstrategy.Theactivityselectionstrategycanberan-domizedordeterministic,asdescribedbelow.Thefollowingarerandomizedselectionstrategies:

•RAND:Selectsanactivityatrandomfromthesetofactivitiesthatbeginpriortotheearliestearlyfinishtime.ThisstrategywasproposedbyNuijten(1994).•MINA:Selectsanactivityatrandomfromthesubsetofactivitiesthatbeginpriortotheearliestearlyfinishtimethathavetheminimumnumberofresourceassignments.•MAXD:Selectsanactivityatrandomfromthesubsetofactivitiesthatbeginpriortotheearliestearlyfinishtimethathavemaximumduration.•MINLS:Selectsanactivityatrandomfromthesubsetofactivitiesthatbeginpriortotheearliestearlyfinishtimethathaveaminimumlatestartdate.Thefollowingaredeterministicselectionstrategies:

•DET:Selectsthefirstactivitythatbeginspriortotheearliestactivityfinishdate.•DMINLS:Selectstheactivitywiththeearliestlatestarttime.

VARStatement

ThedefaultstrategyisRAND.Forselectingvariables,usetheVARSELECT=optioninthePROCCLPstatement.

DURATION=durSCHEDDUR=durDUR=dur

󰀁

23

specifiesthedurationoftheschedule.TheDURATION=optionimposesaconstraintthatthedurationofthescheduledoesnotexceedthespecifiedvalue.

EF

EDGEFINDER

activatestheedgefinderconsistencyroutinesforschedulingproblems.Bydefault,theEFoptionisinactive.

FINISH=finishEND=finish

FINISHBEFORE=finish

specifiesthefinishtimefortheschedule.Theschedulefinishtimeisanupperboundonthefinishtimeofeachactivity(subjecttotime,precedence,andresourcecon-straints).Ifyouwishtoimposeatighterupperboundforanactivity,youcandosoeitherbyusingtheFLE=optioninanACTIVITYstatementorbyusingthe–ALIGNDATE–and–ALIGNTYPE–variablesintheACTDATA=dataset.

START=startBEGIN=start

STARTAFTER=start

specifiesthestarttimefortheschedule.Theschedulestarttimeisalowerboundonthestarttimeofeachactivity(subjecttotime,precedence,andresourceconstraints).Ifyouwishtoimposeatighterlowerboundforanactivity,youcandosoeitherbyusingtheSGE=optioninanACTIVITYstatementorbyusingthe–ALIGNDATE–and–ALIGNTYPE–variablesintheACTDATA=dataset.

VARStatement

VARSTATEMENTvarspec[,varspec...];wherevarspec:=variable<=>;orvarspec:=(variablelist)<=>;

TheVARstatementspecifiesallthevariablesandtheirdomainsthataretobecon-sideredintheCSP.AnyvariabledomainsspecifiedinaVARstatementoverridethedefaultvariabledomains.Iflbisspecifiedandubisomitted,thecorrespondingvari-able(s)areconsideredasbeingassignedtolb.

24

󰀁

Chapter1.TheCLPProcedure(Experimental)

Details

ThissectionprovidesadetailedoutlineoftheuseoftheCLPprocedure.Thematerialisorganizedinsubsectionsthatdescribedifferentaspectsoftheprocedure.

ModesofOperation

TheCLPprocedurecanbeinvokedinoneoftwomodes:standardmodeandschedulingmode.Thestandardmodegivesyouaccesstolinearconstraints,reifiedconstraints,alldiffconstraints,andarrayconstraints,whereastheschedulingmodegivesyouaccesstomorescheduling-specificconstraintssuchastemporalconstraints(precedenceandtime)andresourceconstraints.Instandardmode,thedecisionvari-ablesareone-dimensional;avariableisassignedanintegerinasolution.Inschedul-ingmode,thevariablesaretypicallymultidimensional;avariableisassignedastarttimeandpossiblyasetofresourcesinasolution.Inschedulingmode,thevariablesarereferredtoasactivitiesandthesolutionisreferredtoasaschedule.

SelectingtheModeofOperation

TheCLPprocedurerequiresthespecificationofanoutputdatasettostoretheso-lution(s)totheCSP.Therearetwopossibleoutputdatasets:theSolutiondataset(specifiedusingtheOUT=optioninthePROCCLPstatement),whichcorre-spondstothestandardmodeofoperation,andtheScheduledataset(specifiedusingtheSCHEDDATA=optioninthePROCCLPstatement),whichcorrespondstotheschedulingmodeofoperation.Themodeisdeterminedbywhichoutputdatasethasbeenspecified.Ifanoutputdatasetisnotspecified,theprocedureterminateswithanerrormessage.Ifbothoutputdatasetshavebeenspecified,theScheduledatasetisignored.

ActivityDataSet

YoucanuseanActivitydatasetinlieuof,orincombinationwith,anACTIVITYstatementtodefineactivitiesandconstraintsrelatingtotheactivities.TheActivitydatasetissimilartotheActivitydatasetinputtotheCPMprocedureinSAS/ORsoftwareandisspecifiedusingtheACTDATA=optioninthePROCCLPstatement.TheActivitydatasetenablesyoutodefineanactivity,itsdomain,andanytemporalconstraints.Thetemporalconstraintscouldbeeithertimealignmenttypeorprece-dencetypeconstraints.TheActivitydatasetrequires,attheminimum,twovariables:onetodeterminetheactivity,andanothertodetermineitsduration.Theprocedureterminatesifitcannotfindtherequiredvariables.Theactivityisdeterminedwiththe–ACTIVITY–variable,andthedurationisdeterminedwiththe–DURATION–vari-able.Inadditiontothemandatoryvariables,youcanalsospecifytemporalconstraintsrelatedtotheactivities.

ActivityDataSet

TimeAlignmentConstraints

The–ALIGNDATE–and–ALIGNTYPE–variablesenableyoutodefinetimealign-menttypeconstraints.The–ALIGNTYPE–variabledefinesthetypeofthealignmentconstraintfortheactivitynamedinthe–ACTIVITY–variablewithrespecttothe–ALIGNDATE–variable.Ifthe–ALIGNDATE–variableisnotpresentintheActivitydataset,the–ALIGNTYPE–variableisignored.Ifthe–ALIGNDATE–ispresentbutthe–ALIGNTYPE–variableismissing,thealignmenttypeisassumedtobeSGE.The–ALIGNTYPE–variablecantakethevaluesshowninTable1.10:

Table1.10.ValidValuesforthe–ALIGNTYPE–Variable

󰀁

25

ValueSEQSGESLEFEQFGEFLETypeofAlignmentStartequaltoStartgreaterthanorequaltoStartlessthanorequaltoFinishequalto

FinishgreaterthanorequaltoFinishlessthanorequalto

PrecedenceConstraints

The–SUCCESSOR–variableenablesyoutodefineprecedencetyperelationshipsbetweenactivitiesusingAON(Activity-On-Node)format.The–SUCCESSOR–variablemusthavethesametypeasthatofthe–ACTIVITY–variable.The–LAG–variabledefinesthelagtypeoftherelationship.Bydefault,allprecedencerelation-shipsareconsideredtobeFinish-to-Start(FS).AnFStypeofprecedencerelationshipisalsoreferredtoasastandardprecedenceconstraint.Allothertypesofprece-dencerelationshipsareconsideredtobenonstandardprecedenceconstraints.The–LAGDUR–variablespecifiesthelagduration.Bydefault,thelagdurationiszero.Foreach(activity,successor)pair,youcandefinealagtypeandalagduration.Considerthepairofactivities(A,B)withalagdurationgivenbylagdur.Thein-terpretationofeachofthedifferentlagtypesisgiveninTable1.11.

Table1.11.ValidValuesforthe–LAG–Variable

LagTypeFSSSFFSFFSESSEFFESFEInterpretationFinishA+lagdur≤StartBStartA+lagdur≤StartBFinishA+lagdur≤FinishBStartA+lagdur≤FinishBFinishA+lagdur=StartBStartA+lagdur=StartBFinishA+lagdur=FinishBStartA+lagdur=FinishB

26

󰀁

Chapter1.TheCLPProcedure(Experimental)

Thefirstfourlagtypes(FS,SS,FF,andSF)arealsoreferredtoasFinish-to-Start,Start-to-Start,Finish-to-Finish,andStart-to-Finish,respectively.Thenextfourtypes(FSE,SSE,FFE,andSFE)arestricterversionsofFS,SS,FF,andSF,respectively.Thefirstfourtypesimposealowerboundonthestart/finishtimesofB,whilethelastfourtypesforcethestart/finishtimestobesetequaltothelowerboundofthedomain.Thisenablesyoutoforceanactivitytobeginwhenitspredecessorisfinished.Itisrelativelyeasytogenerateinfeasiblescenarioswiththestricterversions,soyoushouldonlyusethestricterversionsiftheweakerversionsarenotadequateforyourproblem.

ResourceConstraints

TheActivitydatasetcannotbeusedtodefineresourcerequirementtypeconstraints.Todefineresourcerequirementtypeconstraints,youmustspecifyRESOURCEandREQUIRESstatements.

VariablesintheACTDATA=dataset

Table1.12listsallthevariablesassociatedwiththeActivitydatasetandtheirinter-pretationsbytheCLPprocedure.Thetablealsolistsforeachvariableitstype(Cforcharacter,Nfornumeric),thepossiblevaluesitcanassume,anditsdefaultvalue.

Table1.12.ActivityDataSetVariables

Name–ACTIVITY––DURATION––SUCCESSOR––ALIGNDATE––ALIGNTYPE––LAG––LAGDUR–

TypeC/NNC/NNCCN

Descriptionactivitynameduration

successornamealignmentdatealignmenttypelagtypelagduration

AllowedValuesDefault0

sametypeas

–ACTIVITY–

SGE,SLE,SEQ,FGE,FLE,FEQFS,SS,FF,SF,

FSE,SSE,FFE,SFE

0SGEFS0

ScheduleDataSet

InordertosolveaschedulingtypeCSP,youneedtospecifyaScheduledatasetusingtheSCHEDDATA=optioninthePROCCLPstatement.TheScheduledatasetcontainsallthesolutionsthathavebeendeterminedbytheCLPprocedure.TheScheduledatasetalwayscontainsthefollowingfivevariables:SOLUTION,ACTIVITY,DUR,START,andFINISH.Ifanyresourceshavebeenspecified,thenthereisalsoavariablecorrespondingtoeachresourcewiththenameofthevariablebeingthenameoftheresource.TheSOLUTIONvariablegivesthesolutionnumberthateachobservationcorrespondsto.TheACTIVITYvariableidentifiestheactivity,theDURvariablegivesthedurationoftheactivity,andtheSTARTandFINISHvari-ablesgivethescheduledstartandfinishtimesfortheactivity.Ifthereareresourcespresent,thecorrespondingresourcevariableindicateswhetherornotitisbeinguti-lizedfortheactivity.

ConstraintDataSet

Foreverysolutionfoundandforeachactivity,theScheduledatasetcontainsanobservationthatliststheassignmentinformationforthatactivity.

IfanActivitydatasethasbeenspecified,thentheformatsandlabelsfortheACTIVITYandDURvariablescarryovertotheScheduledataset.

󰀁

27

ConstraintDataSet

TheConstraintdatasetdefineslinearconstraints,variabletypes,andboundsonvari-abledomains.YoucanuseaConstraintdatasetinlieuof,orincombinationwith,aLINCONand/oraVARstatementinordertodefinelinearconstraints,variabletypes,andvariablebounds.TheConstraintdatasetissimilartotheproblemdatasetinputtotheLPprocedureinSAS/ORsoftwareandisspecifiedusingtheDATA=optioninthePROCCLPstatement.

TheConstraintdatasetmustbeindenseinputformat.Inthedenseinputformat,amodel’scolumnsappearasvariablesintheinputdatasetandthedatasetmustcon-tainthe–TYPE–variable,the–RHS–variable,andatleastonenumericvariable.Intheabsenceoftheaboverequirement,theCLPprocedureterminates.The–TYPE–variableisacharactervariablewhichtellstheCLPprocedurehowtointerpreteachobservation.TheCLPprocedurerecognizesthefollowingkeywordsasvalidval-uesforthe–TYPE–variable:EQ,LE,GE,NE,LT,GT,LOWERBD,UPPERBD,BINARY,andFIXED.Anoptionalcharactervariable,–ID–,canbeusedtonameeachrowintheConstraintdataset.

LinearConstraints

Forthe–TYPE–valuesEQ,LE,GE,NE,LT,GT,thecorrespondingobservationisinterpretedasalinearconstraint.The–RHS–variableisanumericvariablethatcontainstheright-hand-sidecoefficientofthelinearconstraint.Anynumericvariableotherthan–RHS–isinterpretedasastructuralvariableforthelinearconstraint.

DomainBounds

ThevaluesLOWERBDandUPPERBDspecifyadditionallowerboundsandupperboundsonthevariabledomains.Inanobservationwherethe–TYPE–variableisequaltoLOWERBD,anonmissingvalueforadecisionvariableisconsideredalowerboundforthatvariable.Similarly,inanobservationwherethe–TYPE–variableisequaltoUPPERBD,anonmissingvaluesforadecisionvariableisconsideredanupperboundforthatvariable.Inboththeaboveinstances,itisimportanttonotethatanyspecifiedlowerorupperboundsonavariablemustbeconsistentwiththeexistingdomainofthevariable,ortheproblemisdeemedinfeasible.

VariableTypes

ThekeywordsBINARYandFIXEDareinterpretedasspecifyingnumerictypes.Ifthevalueof–TYPE–isBINARYforanobservation,thenanydecisionvariablewithanonmissingentryfortheobservationisinterpretedasbeingabinaryvariablewithdomain{0,1}.Ifthevalueof–TYPE–isFIXEDforanobservation,thenanydecisionvariablewithanonmissingentryfortheobservationisinterpretedasbeingassignedtothatnonmissingvalue.Inotherwords,ifthevalueofthevariableXiscinan

28

󰀁

Chapter1.TheCLPProcedure(Experimental)

observationforwhich–TYPE–isFIXED,thenthedomainofXisconsideredtobethesingleton{c}.ItisimportanttonotethatthevaluecshouldbelongtothedomainofX,ortheproblemisdeemedinfeasible.

Anynumericvariableotherthan–RHS–isimplicitlyconsideredasappearinginaVARstatementanddoesnotrequireaseparatedefinitioninaVARstatement.IntheeventthatanumericvariablehaspreviouslybeendefinedinaVARstatement,anyboundsthataredefinedintheConstraintdatasetareconsideredinadditiontoboundsthatmayhavebeendefinedusingtheVARstatement.

VariablesintheDATA=dataset

Table1.13listsallthevariablesassociatedwiththeConstraintdatasetandtheirinterpretationsbytheCLPprocedure.Thetablealsolistsforeachvariableitstype(Cforcharacter,Nfornumeric),thepossiblevaluesitcanassume,anditsdefaultvalue.

Table1.13.ConstraintDataSetVariablesName

–TYPE–

TypeCDescriptionobservationtype

AllowedValuesEQ,LE,GE,NE,LT,GT,LOWERBD,UPPERBD,BINARY,FIXED

Default

–RHS––ID–

NCN

Anynumericvariableotherthan–RHS–

right-hand-sidecoefficient

observationname(optional)

structuralvariable

0

SolutionDataSet

Inordertosolveastandard(nonscheduling)typeCSP,youneedtospecifyaSolutiondatasetusingtheOUT=optioninthePROCCLPstatement.TheSolutiondatasetcontainsallthesolutionsthathavebeendeterminedbytheCLPprocedure.TheSolutiondatasetcontainsasmanydecisionvariablesashavebeendefinedinthecalltoPROCCLP.EveryobservationintheSolutiondatasetcorrespondstoasolutiontotheCSP.IfaProblemdatasethasbeenspecified,thenanyvariableformatsandvariablelabelsfromtheProblemdatasetcarryovertotheSolutiondataset.

References

󰀁

29

References

Applegate,D.andCook,W.(1991),“AComputationalStudyoftheJobShopSchedulingProblem,”ORSAJournalonComputing,3,149–156.

Colmerauer,A.(1990),“AnIntroductiontoPROLOGIII,”CommunicationsoftheACM,33,70–90.

Floyd,R.W.(1967),“NondeterministicAlgorithms,”JournaloftheACM,14,636–644.

Garey,M.R.andJohnson,D.S.(1979),ComputersandIntractability:AGuidetotheTheoryofNP-Completeness,NewYork:W.H.Freeman&Co.

Haralick,R.M.andElliot,G.L.(1980),“IncreasingTreeSearchEfficiencyforConstraintSatisfactionProblems,”ArtificialIntelligence,14,263–313.

Jaffar,J.andLassez,J.(1987),“ConstraintLogicProgramming,”ConferenceRecordofthe14thAnnualACMSymposiuminPrinciplesofProgrammingLanguages,Munich,111–119.

Kumar,V.(1992),“AlgorithmsforConstraint-SatisfactionProblems:ASurvey,”AIMagazine,13,32–44.

Mackworth,A.K.(1977),“ConsistencyinNetworksofRelations,”ArtificialIntelligence,8,99–118.

Nemhauser,G.L.andWolsey,L.A.(1988),IntegerandCombinatorialOptimization,NewYork:JohnWiley.

Nuijten,W.(1994),TimeandResourceConstrainedScheduling,Ph.D.thesis,EindhovenInstituteofTechnology.

Smith,B.M.,Brailsford,S.C.,Hubbard,P.M.,andWilliams,H.P.(1996),“TheProgressivePartyProblem:IntegerLinearProgrammingandConstraintProgrammingCompared,”Constraints,1,119–138.

Tsang,E.(1993),FoundationsofConstraintSatisfaction,London:AcademicPress.VanHentenryck,P.(1989),ConstraintSatisfactioninLogicProgramming,Cambridge,MA:MITPress.

VanHentenryck,P.,Deville,Y.,andTeng,C.(1992),“AGenericArc-ConsistencyAlgorithmanditsSpecializations,”ArtificialIntelligence,57,291–321.

Waltz,D.L.(1975),“UnderstandingLineDrawingsofSceneswithShadows,”inP.H.Winston,ed.,“ThePsychologyofComputerVision,”19–91,NewYork:McGraw-Hill.

Williams,H.P.andWilson,J.M.(1998),“ConnectionsBetweenIntegerLinearProgrammingandConstraintLogicProgramming–AnOverviewandIntroductiontotheClusterofArticles,”INFORMSJournalofComputing,10,261–264.

30

󰀁

Chapter1.TheCLPProcedure(Experimental)

SubjectIndex

A

Activitydataset,10,24,26,27

–ACTIVITY–variable,24–26

–ALIGNDATE–variable,23,25,26–ALIGNTYPE–variable,23,25,26–DURATION–variable,24,26–LAG–variable,25,26

–LAGDUR–variable,25,26–SUCCESSOR–variable,25,26–ACTIVITYActivity–variable

dataset,24–26ACTIVITYvariable

Scheduledataset,26–ALIGNDATEActivitydata–variable

set,23,25,26alignmenttype

FEQ,25FGE,18,25FLE,18,25SEQ,25SGE,18,25SLE,18,25

–ALIGNTYPE–variable

Activitydataset,23,25,26arraydefinition,19assignmentstrategy,10

MAXLS,22options,14RAND,10,22

B

backtrackingsearch,8

C

CLPprocedure

Activitydataset,10,24,26,27assignmentstrategy,10,14consistencytechniques,10Constraintdataset,27datasetoptions,14details,24

generaloptions,14

introductoryexamples,11outputcontroloptions,14overview,7,9

Problemdataset,9

Scheduledataset,24,26,27schedulingCSPstatements,14

schedulingmode,24

schedulingsearchcontroloptions,15

schedulingtemporalconstraintsoptions,14selectionstrategy,10,15Solutiondataset,24,28standardCSPstatements,15standardmode,24syntax,13

consistencytechniques,10Constraintdataset,27,28

–IDRHS–variable,27,28––variable,27,28–TYPE–variable,27,28constraintprogramming

finitedomain,8constraintpropagation,8

constraintsatisfactionproblem(CSP),7

backtrackingsearch,8constraintpropagation,8definitionof,7

schedulingCSP,9,10standardCSP,9

techniquesforsolving,8

D

datasetoptions,14

deadendmultiplier,15,16domain,7,16

bounds,27

distributionstrategy,9DURvariable

Scheduledataset,26duration,23

–DURATION–variable

Activitydataset,24,26

E

edgefinderroutine,23examples,11

EightQueens,11

SendMoreMoney,11

F

finishtime,23FINISHvariable

Scheduledataset,26

finitedomainconstraintprogramming,8

32

󰀁

SubjectIndex

I

–ID–variable

Constraintdataset,27,28inputdataset,15,24,27

L

lagtype,25

FF,26FFE,26FS,26FSE,26SF,26SFE,26SS,26SSE,26–LAG–variable

Activitydataset,25,26–LAGDUR–variable

Activitydataset,25,26linearconstraints,27

specifying,15,19,27look-aheadschemas,9look-backschemas,9

M

modesofoperation,24

O

outputcontroloptions,14outputdataset,16,26

P

precedenceconstraints,25preprocessing,16Problemdataset,9

R

resourcerequirements,21,26restarts,16

–RHS–variable

Constraintdataset,27,28

S

satisfiabilityproblem(SAT),8schedule

duration,23finishtime,23starttime,23

Scheduledataset,24,26,27

ACTIVITYvariable,26DURvariable,26FINISHvariable,26SOLUTIONvariable,26STARTvariable,26schedulingCSP,9,10searchcontroloptions,15selectionstrategy,10,17

activity,22

DET,23DMINLS,23FIFO,17MAXC,17MAXCS,17MAXD,22MINA,22MINLS,22MINR,10,17MINRMAXC,17options,15RAND,10,22Solutiondataset,24,28SOLUTIONvariable

Scheduledataset,26standardCSP,9starttime,23STARTvariable

Scheduledataset,26–SUCCESSOR–variable

Activitydataset,25,26syntaxtables,13,14

assignmentstrategyoptions,14datasetoptions,14generaloptions,14

outputcontroloptions,14

schedulingCSPstatements,14

schedulingsearchcontroloptions,15

schedulingtemporalconstraintsoptions,14selectionstrategyoptions,15standardCSPstatements,15

T

–TYPEConstraint–variable

dataset,27,28

V

variableselection,9

SyntaxIndex

A

ACTASSIGN=option

SCHEDULEstatement,10,17,22ACTDATA=option

PROCCLPstatement,10,15,18,23,24,26ACTIVITYstatement,10,15,17,23,24ACTIVITY=option,

SeeACTDATA=optionACTSELECT=option

SCHEDULEstatement,10,17,22ACTVALSELECT=option,

SeeACTASSIGN=optionALLDIFFstatement,9,18ALLSOLNS,

SeeFINDALLSOLNSARRAYstatement,9,19

B

BEGIN=option,

SeeSTART=option

D

DATA=option

PROCCLPstatement,9,15,16,20,27,28DEM=option

PROCCLPstatement,15DEPR=option

PROCCLPstatement,16DETselectionstrategy,23DMINLSselectionstrategy,23DOM=option,

SeeDOMAIN=optionDOMAIN=option

PROCCLPstatement,16DUR=option,

SeeDURATION=optionDURATION=option

SCHEDULEstatement,23

E

EDGEFINDERoption,

SeeEFoptionEFoption

SCHEDULEstatement,23END=option,

SeeFINISH=option

F

FAS,

SeeFINDALLSOLNSFEQalignmenttype,25FFlagtype,26FFElagtype,26

FGEalignmenttype,18,25FIFOselectionstrategy,17FINDALL,

SeeFINDALLSOLNSFINDALLSOLNS

PROCCLPstatement,16FINISH=option

SCHEDULEstatement,23FINISHBEFORE=option,

SeeFINISH=optionFLEalignmenttype,18,25FOREACHstatement,9,19FSlagtype,26FSElagtype,26

L

LINCONstatement,9,10,15,19,27

M

MAXCselectionstrategy,17MAXCSselectionstrategy,17MAXDselectionstrategy,22MAXLSassignmentstrategy,22MINAselectionstrategy,22MINLSselectionstrategy,22MINRselectionstrategy,10,17MINRMAXCselectionstrategy,17

N

NOPREPROCESS

PROCCLPstatement,16

O

ORCP,1OUT=option

PROCCLPstatement,9,16,24,28

P

PROCCLPstatement,15

ACTDATA=option,10,15,18,23,24DATA=option,9,15,16,20,27,28DEM=option,15

34

󰀁

SyntaxIndex

DEPR=option,16DOMAIN=option,16FINDALLSOLNS,16NOPREPROCESS,16OUT=option,9,16,24,28RESTARTS=option,16

SCHEDDATA=option,9,10,16,18,24,26SHOWPROGRESSoption,17SOLNS=option,16,17

VARASSIGN=option,10,17,22VARSELECT=option,10,17,23

R

RANDassignmentstrategy,10,22RANDselectionstrategy,10,22REIFYstatement,9,20

REQUIRESstatement,10,21,26RESOURCEstatement,10,21,26RESTARTS=option

PROCCLPstatement,16

S

SCHEDDATA=option

PROCCLPstatement,9,10,16,18,24,26SCHEDDUR=option,

SeeDURATION=optionSCHEDULEstatement,10,22

ACTASSIGN=option,10,17,22ACTSELECT=option,10,17,22DURATION=option,23EFoption,23

FINISH=option,23START=option,23SCHEDULE=option,

SeeSCHEDDATA=optionSEQalignmenttype,25SFlagtype,26SFElagtype,26

SGEalignmenttype,18,25SHOWPROGRESSoption

PROCCLPstatement,17SLEalignmenttype,18,25SOLNS=option

PROCCLPstatement,16,17SSlagtype,26SSElagtype,26START=option

SCHEDULEstatement,23STARTAFTER=option,

SeeSTART=option

V

VALSELECT=option,

SeeVARASSIGN=option

VARstatement,9,15,19,20,23,27,28VARASSIGN=option

PROCCLPstatement,10,17,22VARSELECT=option

PROCCLPstatement,10,17,23

Your Turn

If you have comments or suggestions about SAS/OR 9.1 User’s Guide: Constraint Programming, please send them to us on a photocopy of this page or send us electronic mail.

For comments about this book, please return the photocopy to SAS Publishing SAS Campus Drive Cary, NC 27513

E-mail: yourturn@sas.com

For suggestions about the software, please return the photocopy to SAS Institute Inc.

Technical Support Division SAS Campus Drive Cary, NC 27513

E-mail: suggest@sas.com