This is a preliminary set of examples to offer some starting points for experimenting with AMPL’s “logic” and constraint programming interfaces. We welcome comments for improvements or other examples.
Integer program for assignment of people of groups so that each group is “balanced” by various criteria.
# ------------------------------------------------ # ANTI-ASSIGNMENT PROBLEM: # Assign people to groups # so that groups are as heterogeneous as possible # ------------------------------------------------ # Version 2: Minimize "sum of deviations" # ------------------------------------------------ # To make this problem harder, # decrease sample and/or increase numberGrps. set ALL_PEOPLE ordered; param sample integer > 0; param selection integer >= 0, < sample; set PEOPLE := {i in ALL_PEOPLE: ord(i) mod sample = selection}; set CATEG; param type {ALL_PEOPLE,CATEG} symbolic; param typeWt {CATEG} >= 0; param numberGrps integer > 0; set TYPES {k in CATEG} := setof {i in PEOPLE} type[i,k]; var Assign {i in PEOPLE, j in 1..numberGrps} binary; var MinInGrp <= floor (card(PEOPLE)/numberGrps); var MaxInGrp >= ceil (card(PEOPLE)/numberGrps); var MinType {k in CATEG, t in TYPES[k]} <= floor (card {i in PEOPLE: type[i,k] = t} / numberGrps); var MaxType {k in CATEG, t in TYPES[k]} >= ceil (card {i in PEOPLE: type[i,k] = t} / numberGrps); minimize Variation: (MaxInGrp - MinInGrp) + sum {k in CATEG, t in TYPES[k]} typeWt[k] * (MaxType[k,t] - MinType[k,t]); subj to AssignAll {i in PEOPLE}: sum {j in 1..numberGrps} Assign[i,j] = 1; subj to MinInGrpDefn {j in 1..numberGrps}: MinInGrp <= sum {i in PEOPLE} Assign[i,j]; subj to MaxInGrpDefn {j in 1..numberGrps}: MaxInGrp >= sum {i in PEOPLE} Assign[i,j]; subj to MinTypeDefn {j in 1..numberGrps, k in CATEG, t in TYPES[k]}: MinType[k,t] <= sum {i in PEOPLE: type[i,k] = t} Assign[i,j]; subj to MaxTypeDefn {j in 1..numberGrps, k in CATEG, t in TYPES[k]}: MaxType[k,t] >= sum {i in PEOPLE: type[i,k] = t} Assign[i,j];
# ------------------------------------------------ # TEST DATA for balassign0.mod # All names and types are fictional # ------------------------------------------------ param sample := 4; param selection := 0; param numberGrps := 7; set ALL_PEOPLE := BIW AJH FWI IGN KWR KKI HMN SML RSR TBR KRS CAE MPO CAR PSL BCG DJA AJT JPY HWG TLR MRL JDS JAE TEN MKA NMA PAS DLD SCG VAA FTR GCY OGZ SME KKA MMY API ASA JLN JRT SJO WMS RLN WLB SGA MRE SDN HAN JSG AMR DHY JMS AGI RHE BLE SMA BAN JAP EHR MES DHE SWS ACI RJY TWD MMA JJR MFR LHS JAD CWU PMY CAH SJH EGR JMQ GGH MMH JWR MJR EAZ WAD LVN DHR ABE LSR MBT AJU SAS JRS RFS TAR DLT HJO SCR CMY GDE MSL CGS HCN JWS RPR RCR RLS DSF MNA MSR PSY MET DAN RVY PWS CTS KLN RDN ANV LMN FSM KWN CWT PMO EJD AJS SBK JWB SNN PST PSZ AWN DCN RGR CPR NHI HKA VMA DMN KRA CSN HRR SWR LLR AVI RHA KWY MLE FJL ESO TJY WHF TBG FEE MTH RMN WFS CEH SOL ASO MDI RGE LVO ADS CGH RHD MBM MRH RGF PSA TTI HMG ECA CFS MKN SBM RCG JMA EGL UJT ETN GWZ MAI DBN HFE PSO APT JMT RJE MRZ MRK XYF JCO PSN SCS RDL TMN CGY GMR SER RMS JEN DWO REN DGR DET FJT RJZ MBY RSN REZ BLW ; param: CATEG: typeWt := dept 1 loc 1 rate 1 title 1 ; param type: dept loc rate title := BIW NNE Peoria A Assistant KRS WSW Springfield B Assistant TLR NNW Peoria B Adjunct VAA NNW Peoria A Deputy JRT NNE Springfield A Deputy AMR SSE Peoria A Deputy MES NNE Peoria A Consultant JAD NNE Peoria A Adjunct MJR NNE Springfield A Assistant JRS NNE Springfield A Assistant HCN SSE Peoria A Deputy DAN NNE Springfield A Adjunct CWT NNE Springfield A Adjunct DCN NNE Peoria A Adjunct SWR WSW Peoria A Adjunct TBG NNE Springfield A Assistant LVO NNE Peoria A Assistant ECA NNE Springfield A Assistant MAI NNE Peoria B Adjunct JCO SSE Macomb A Adjunct DWO SSE Peoria A Adjunct AJH NNE Peoria A Adjunct CAE SSE Peoria A Adjunct MRL WSW Peoria A Assistant FTR NNE Peoria A Adjunct SJO NNE Peoria A Adjunct DHY NNE Urbana A Adjunct DHE NNE Peoria A Adjunct CWU NNW Peoria A Assistant EAZ NNE Peoria A Assistant RFS NNE Peoria A Deputy JWS WSW Peoria A Adjunct RVY NNE Peoria A Adjunct PMO SSE Peoria A Assistant RGR NNE Peoria A Assistant LLR NNE Peoria A Assistant FEE NNW Springfield A Adjunct ADS NNE Peoria A Adjunct CFS NNW Joliet A Assistant DBN SSE Peoria A Adjunct PSN NNE Peoria A Adjunct REN NNE Peoria B Adjunct FWI NNW Peoria A Assistant MPO SSE Peoria A Assistant JDS NNW Peoria A Adjunct GCY NNE Peoria A Adjunct WMS NNE Springfield A Deputy JMS NNE Springfield A Adjunct SWS NNW Springfield A Assistant PMY NNE Peoria A Deputy WAD NNE Springfield A Adjunct TAR NNE Peoria A Assistant RPR NNE Peoria A Adjunct PWS NNE Peoria A Consultant EJD WSW Peoria B Adjunct CPR NNE Peoria A Deputy AVI NNE Springfield B Adjunct MTH NNE Joliet A Assistant CGH NNE Springfield A Adjunct MKN WSW Peoria A Assistant HFE NNW Carbondale A Adjunct SCS NNE Peoria A Adjunct DGR NNE Springfield A Assistant IGN NNE Springfield A Assistant CAR NNW Peoria A Assistant JAE NNE Springfield A Assistant OGZ NNE Peoria A Consultant RLN SSE Peoria A Adjunct AGI SSE Peoria A Assistant ACI NNE Peoria B Assistant CAH SSE Peoria B Adjunct LVN NNE Springfield B Assistant DLT SSE Peoria B Adjunct RCR NNE Peoria A Adjunct CTS NNE Peoria A Deputy AJS SSE Peoria A Assistant NHI NNE Carbondale A Assistant RHA NNW Carbondale A Assistant RMN NNE Springfield A Deputy RHD SSE Peoria A Assistant SBM NNW Peoria A Assistant PSO NNE Peoria A Adjunct RDL NNW Joliet A Adjunct DET NNE Springfield A Assistant KWR NNE Peoria A Assistant PSL SSE Peoria B Assistant TEN NNW Springfield A Adjunct SME NNE Springfield A Consultant WLB NNE Peoria A Adjunct RHE NNE Peoria A Assistant RJY SSE Springfield A Deputy SJH NNE Cairo A Adjunct DHR SSE Peoria A Assistant HJO NNE Carbondale A Assistant RLS NNE Peoria A Adjunct KLN WSW Peoria A Adjunct SBK NNE Cairo A Adjunct HKA NNE Carbondale A Adjunct KWY NNE Peoria A Deputy WFS NNW Peoria A Adjunct MBM SSE Peoria A Assistant RCG SSE Peoria A Adjunct APT NNE Peoria A Adjunct TMN NNE Peoria A Assistant FJT WSW Peoria A Assistant KKI NNE Carbondale A Adjunct BCG NNE Urbana A Adjunct MKA NNE Carbondale A Assistant KKA NNE Peoria A Assistant SGA NNW Springfield B Assistant BLE NNE Peoria A Assistant TWD SSE Peoria A Assistant EGR NNE Peoria B Adjunct ABE NNW Peoria A Adjunct SCR NNE Peoria A Adjunct DSF NNW Springfield A Adjunct RDN NNE Peoria A Adjunct JWB NNW Peoria B Deputy VMA SSE Peoria A Adjunct MLE NNE Macomb A Adjunct CEH NNE Springfield A Assistant MRH NNE Peoria A Deputy JMA NNE Carbondale A Deputy JMT NNE Peoria B Assistant CGY NNE Springfield A Adjunct RJZ NNW Peoria A Adjunct HMN WSW Springfield B Assistant DJA NNE Peoria A Adjunct NMA NNE Carbondale B Assistant MMY NNE Peoria A Assistant MRE NNE Peoria A Assistant SMA NNE Joliet A Adjunct MMA NNE Carbondale A Deputy JMQ NNE Carbondale B Assistant LSR NNW Peoria A Adjunct CMY NNE Peoria A Adjunct MNA NNE Carbondale A Adjunct ANV SSE Peoria A Assistant SNN NNE Macomb B Deputy DMN NNW Peoria A Adjunct FJL NNE Springfield A Assistant SOL NNE Evansville A Assistant RGF NNE Springfield A Adjunct EGL NNE Peoria A Adjunct RJE NNE Macomb A Adjunct GMR NNE Peoria A Assistant MBY NNE Peoria B Assistant SML NNE Springfield A Assistant AJT NNE Peoria A Assistant PAS NNE Peoria A Assistant API NNE Springfield A Adjunct SDN NNE Peoria A Deputy BAN NNE Peoria A Assistant JJR SSE Springfield A Adjunct GGH NNW Peoria A Adjunct MBT NNE Peoria A Adjunct GDE NNE Peoria A Deputy MSR SSE Peoria A Assistant LMN NNW Peoria B Assistant PST NNE Springfield A Assistant KRA NNE Peoria A Adjunct ESO NNE Springfield A Adjunct ASO NNE Carbondale B Assistant PSA NNE Springfield A Assistant UJT NNE Springfield A Assistant MRZ WSW Peoria B Assistant SER NNW Peoria A Assistant RSN NNE Joliet A Assistant RSR NNW Peoria A Adjunct JPY NNE Peoria A Adjunct DLD NNE Urbana B Assistant ASA SSE Peoria A Consultant HAN SSE Peoria A Deputy JAP SSE Peoria A Adjunct MFR NNE Springfield A Adjunct MMH NNE Joliet A Adjunct AJU SSE Springfield A Assistant MSL NNW Springfield A Adjunct PSY NNE Springfield A Assistant FSM NNE Springfield A Assistant PSZ SSE Peoria A Assistant CSN NNE Joliet A Assistant TJY WSW Springfield A Adjunct MDI NNE Peoria A Consultant TTI NNE Carbondale A Assistant ETN NNE Peoria A Assistant MRK NNE Peoria A Adjunct RMS NNE Peoria A Adjunct REZ NNE Evansville A Adjunct TBR NNE Peoria A Deputy HWG NNE Peoria A Assistant SCG NNW Joliet A Adjunct JLN NNE Peoria B Assistant JSG NNE Peoria A Deputy EHR NNE Peoria A Assistant LHS NNE Peoria A Adjunct JWR NNE Springfield A Assistant SAS NNE Peoria B Adjunct CGS NNE Springfield A Assistant MET NNE Peoria B Assistant KWN WSW Springfield A Assistant AWN NNE Springfield A Adjunct HRR NNE Macomb A Adjunct WHF NNE Peoria A Assistant RGE SSE Springfield A Adjunct HMG NNE Joliet B Assistant GWZ NNE Joliet A Assistant XYF NNE Peoria A Assistant JEN NNE Peoria A Deputy BLW NNE Peoria A Deputy ;
Constraint program for balanced assignment of people to groups, using the numberof
operator.
# ------------------------------------------------ # ANTI-ASSIGNMENT PROBLEM: # Assign people to groups # so that groups are as heterogeneous as possible # ------------------------------------------------ # Version 2: Minimize "sum of deviations" # ------------------------------------------------ # To make this problem harder, # decrease sample and/or increase numberGrps. set ALL_PEOPLE ordered; param sample integer > 0; param selection integer >= 0, < sample; set PEOPLE := {i in ALL_PEOPLE: ord(i) mod sample = selection}; set CATEG; param type {ALL_PEOPLE,CATEG} symbolic; param typeWt {CATEG} >= 0; param numberGrps integer > 0; set TYPES {k in CATEG} := setof {i in PEOPLE} type[i,k]; var Assign {i in PEOPLE} integer >= 1, <= numberGrps; var MinInGrp integer <= floor (card(PEOPLE)/numberGrps); var MaxInGrp integer >= ceil (card(PEOPLE)/numberGrps); var MinType {k in CATEG, t in TYPES[k]} integer <= floor (card {i in PEOPLE: type[i,k] = t} / numberGrps); var MaxType {k in CATEG, t in TYPES[k]} integer >= ceil (card {i in PEOPLE: type[i,k] = t} / numberGrps); minimize Variation: (MaxInGrp - MinInGrp) + sum {k in CATEG, t in TYPES[k]} typeWt[k] * (MaxType[k,t] - MinType[k,t]); subj to MinInGrpDefn {j in 1..numberGrps}: MinInGrp <= numberof j in ({i in PEOPLE} Assign[i]); subj to MaxInGrpDefn {j in 1..numberGrps}: MaxInGrp >= numberof j in ({i in PEOPLE} Assign[i]); subj to MinTypeDefn {j in 1..numberGrps, k in CATEG, t in TYPES[k]}: MinType[k,t] <= numberof j in ({i in PEOPLE: type[i,k] = t} Assign[i]); subj to MaxTypeDefn {j in 1..numberGrps, k in CATEG, t in TYPES[k]}: MaxType[k,t] >= numberof j in ({i in PEOPLE: type[i,k] = t} Assign[i]);
# ------------------------------------------------ # TEST DATA for balassign1.mod # All names and types are fictional # ------------------------------------------------ param sample := 4; param selection := 0; param numberGrps := 7; set ALL_PEOPLE := BIW AJH FWI IGN KWR KKI HMN SML RSR TBR KRS CAE MPO CAR PSL BCG DJA AJT JPY HWG TLR MRL JDS JAE TEN MKA NMA PAS DLD SCG VAA FTR GCY OGZ SME KKA MMY API ASA JLN JRT SJO WMS RLN WLB SGA MRE SDN HAN JSG AMR DHY JMS AGI RHE BLE SMA BAN JAP EHR MES DHE SWS ACI RJY TWD MMA JJR MFR LHS JAD CWU PMY CAH SJH EGR JMQ GGH MMH JWR MJR EAZ WAD LVN DHR ABE LSR MBT AJU SAS JRS RFS TAR DLT HJO SCR CMY GDE MSL CGS HCN JWS RPR RCR RLS DSF MNA MSR PSY MET DAN RVY PWS CTS KLN RDN ANV LMN FSM KWN CWT PMO EJD AJS SBK JWB SNN PST PSZ AWN DCN RGR CPR NHI HKA VMA DMN KRA CSN HRR SWR LLR AVI RHA KWY MLE FJL ESO TJY WHF TBG FEE MTH RMN WFS CEH SOL ASO MDI RGE LVO ADS CGH RHD MBM MRH RGF PSA TTI HMG ECA CFS MKN SBM RCG JMA EGL UJT ETN GWZ MAI DBN HFE PSO APT JMT RJE MRZ MRK XYF JCO PSN SCS RDL TMN CGY GMR SER RMS JEN DWO REN DGR DET FJT RJZ MBY RSN REZ BLW ; param: CATEG: typeWt := dept 1 loc 1 rate 1 title 1 ; param type: dept loc rate title := BIW NNE Peoria A Assistant KRS WSW Springfield B Assistant TLR NNW Peoria B Adjunct VAA NNW Peoria A Deputy JRT NNE Springfield A Deputy AMR SSE Peoria A Deputy MES NNE Peoria A Consultant JAD NNE Peoria A Adjunct MJR NNE Springfield A Assistant JRS NNE Springfield A Assistant HCN SSE Peoria A Deputy DAN NNE Springfield A Adjunct CWT NNE Springfield A Adjunct DCN NNE Peoria A Adjunct SWR WSW Peoria A Adjunct TBG NNE Springfield A Assistant LVO NNE Peoria A Assistant ECA NNE Springfield A Assistant MAI NNE Peoria B Adjunct JCO SSE Macomb A Adjunct DWO SSE Peoria A Adjunct AJH NNE Peoria A Adjunct CAE SSE Peoria A Adjunct MRL WSW Peoria A Assistant FTR NNE Peoria A Adjunct SJO NNE Peoria A Adjunct DHY NNE Urbana A Adjunct DHE NNE Peoria A Adjunct CWU NNW Peoria A Assistant EAZ NNE Peoria A Assistant RFS NNE Peoria A Deputy JWS WSW Peoria A Adjunct RVY NNE Peoria A Adjunct PMO SSE Peoria A Assistant RGR NNE Peoria A Assistant LLR NNE Peoria A Assistant FEE NNW Springfield A Adjunct ADS NNE Peoria A Adjunct CFS NNW Joliet A Assistant DBN SSE Peoria A Adjunct PSN NNE Peoria A Adjunct REN NNE Peoria B Adjunct FWI NNW Peoria A Assistant MPO SSE Peoria A Assistant JDS NNW Peoria A Adjunct GCY NNE Peoria A Adjunct WMS NNE Springfield A Deputy JMS NNE Springfield A Adjunct SWS NNW Springfield A Assistant PMY NNE Peoria A Deputy WAD NNE Springfield A Adjunct TAR NNE Peoria A Assistant RPR NNE Peoria A Adjunct PWS NNE Peoria A Consultant EJD WSW Peoria B Adjunct CPR NNE Peoria A Deputy AVI NNE Springfield B Adjunct MTH NNE Joliet A Assistant CGH NNE Springfield A Adjunct MKN WSW Peoria A Assistant HFE NNW Carbondale A Adjunct SCS NNE Peoria A Adjunct DGR NNE Springfield A Assistant IGN NNE Springfield A Assistant CAR NNW Peoria A Assistant JAE NNE Springfield A Assistant OGZ NNE Peoria A Consultant RLN SSE Peoria A Adjunct AGI SSE Peoria A Assistant ACI NNE Peoria B Assistant CAH SSE Peoria B Adjunct LVN NNE Springfield B Assistant DLT SSE Peoria B Adjunct RCR NNE Peoria A Adjunct CTS NNE Peoria A Deputy AJS SSE Peoria A Assistant NHI NNE Carbondale A Assistant RHA NNW Carbondale A Assistant RMN NNE Springfield A Deputy RHD SSE Peoria A Assistant SBM NNW Peoria A Assistant PSO NNE Peoria A Adjunct RDL NNW Joliet A Adjunct DET NNE Springfield A Assistant KWR NNE Peoria A Assistant PSL SSE Peoria B Assistant TEN NNW Springfield A Adjunct SME NNE Springfield A Consultant WLB NNE Peoria A Adjunct RHE NNE Peoria A Assistant RJY SSE Springfield A Deputy SJH NNE Cairo A Adjunct DHR SSE Peoria A Assistant HJO NNE Carbondale A Assistant RLS NNE Peoria A Adjunct KLN WSW Peoria A Adjunct SBK NNE Cairo A Adjunct HKA NNE Carbondale A Adjunct KWY NNE Peoria A Deputy WFS NNW Peoria A Adjunct MBM SSE Peoria A Assistant RCG SSE Peoria A Adjunct APT NNE Peoria A Adjunct TMN NNE Peoria A Assistant FJT WSW Peoria A Assistant KKI NNE Carbondale A Adjunct BCG NNE Urbana A Adjunct MKA NNE Carbondale A Assistant KKA NNE Peoria A Assistant SGA NNW Springfield B Assistant BLE NNE Peoria A Assistant TWD SSE Peoria A Assistant EGR NNE Peoria B Adjunct ABE NNW Peoria A Adjunct SCR NNE Peoria A Adjunct DSF NNW Springfield A Adjunct RDN NNE Peoria A Adjunct JWB NNW Peoria B Deputy VMA SSE Peoria A Adjunct MLE NNE Macomb A Adjunct CEH NNE Springfield A Assistant MRH NNE Peoria A Deputy JMA NNE Carbondale A Deputy JMT NNE Peoria B Assistant CGY NNE Springfield A Adjunct RJZ NNW Peoria A Adjunct HMN WSW Springfield B Assistant DJA NNE Peoria A Adjunct NMA NNE Carbondale B Assistant MMY NNE Peoria A Assistant MRE NNE Peoria A Assistant SMA NNE Joliet A Adjunct MMA NNE Carbondale A Deputy JMQ NNE Carbondale B Assistant LSR NNW Peoria A Adjunct CMY NNE Peoria A Adjunct MNA NNE Carbondale A Adjunct ANV SSE Peoria A Assistant SNN NNE Macomb B Deputy DMN NNW Peoria A Adjunct FJL NNE Springfield A Assistant SOL NNE Evansville A Assistant RGF NNE Springfield A Adjunct EGL NNE Peoria A Adjunct RJE NNE Macomb A Adjunct GMR NNE Peoria A Assistant MBY NNE Peoria B Assistant SML NNE Springfield A Assistant AJT NNE Peoria A Assistant PAS NNE Peoria A Assistant API NNE Springfield A Adjunct SDN NNE Peoria A Deputy BAN NNE Peoria A Assistant JJR SSE Springfield A Adjunct GGH NNW Peoria A Adjunct MBT NNE Peoria A Adjunct GDE NNE Peoria A Deputy MSR SSE Peoria A Assistant LMN NNW Peoria B Assistant PST NNE Springfield A Assistant KRA NNE Peoria A Adjunct ESO NNE Springfield A Adjunct ASO NNE Carbondale B Assistant PSA NNE Springfield A Assistant UJT NNE Springfield A Assistant MRZ WSW Peoria B Assistant SER NNW Peoria A Assistant RSN NNE Joliet A Assistant RSR NNW Peoria A Adjunct JPY NNE Peoria A Adjunct DLD NNE Urbana B Assistant ASA SSE Peoria A Consultant HAN SSE Peoria A Deputy JAP SSE Peoria A Adjunct MFR NNE Springfield A Adjunct MMH NNE Joliet A Adjunct AJU SSE Springfield A Assistant MSL NNW Springfield A Adjunct PSY NNE Springfield A Assistant FSM NNE Springfield A Assistant PSZ SSE Peoria A Assistant CSN NNE Joliet A Assistant TJY WSW Springfield A Adjunct MDI NNE Peoria A Consultant TTI NNE Carbondale A Assistant ETN NNE Peoria A Assistant MRK NNE Peoria A Adjunct RMS NNE Peoria A Adjunct REZ NNE Evansville A Adjunct TBR NNE Peoria A Deputy HWG NNE Peoria A Assistant SCG NNW Joliet A Adjunct JLN NNE Peoria B Assistant JSG NNE Peoria A Deputy EHR NNE Peoria A Assistant LHS NNE Peoria A Adjunct JWR NNE Springfield A Assistant SAS NNE Peoria B Adjunct CGS NNE Springfield A Assistant MET NNE Peoria B Assistant KWN WSW Springfield A Assistant AWN NNE Springfield A Adjunct HRR NNE Macomb A Adjunct WHF NNE Peoria A Assistant RGE SSE Springfield A Adjunct HMG NNE Joliet B Assistant GWZ NNE Joliet A Assistant XYF NNE Peoria A Assistant JEN NNE Peoria A Deputy BLW NNE Peoria A Deputy ;
Model for map coloring using not-equals constraint.
param NumColors; set Countries; set Neighbors within Countries cross Countries; var color{Countries} integer >= 1 <= NumColors; s.t. different_colors{(c1, c2) in Neighbors}: color[c1] != color[c2]; data; param NumColors := 4; set Countries := Belgium Denmark France Germany Luxembourg Netherlands; set Neighbors := Belgium France Belgium Germany Belgium Netherlands Belgium Luxembourg Denmark Germany France Germany France Luxembourg Germany Luxembourg Germany Netherlands;
Integer program for the n queens problem: put n queens on an n-by-n chessboard so that no queen is attacking any other queen.
param n; set ROWS := {1..n}; set COLUMNS := {1..n}; var X{ROWS, COLUMNS} binary; # X[i,j] is one if there is a queen at (i,j); else zero #maximize max_queens: sum {i in ROWS, j in COLUMNS} X[i,j]; subject to column_attacks {j in COLUMNS}: sum {i in ROWS} X[i,j] = 1; subject to row_attacks {i in ROWS}: sum {j in COLUMNS} X[i,j] = 1; subject to diagonal1_attacks {k in 2..2*n}: sum {i in ROWS, j in COLUMNS: i+j=k} X[i,j] <= 1; subject to diagonal2_attacks {k in -(n-1)..(n-1)}: sum {i in ROWS, j in COLUMNS: i-j=k} X[i,j] <= 1;
Constraint program for the n queens problem, using the alldiff operator.
param n integer > 0; var Row {1..n} integer >= 1 <= n; subj to c1: alldiff ({j in 1..n} Row[j]); subj to c2: alldiff ({j in 1..n} Row[j]+j); subj to c3: alldiff ({j in 1..n} Row[j]-j);
Open-shop scheduling model using disjunctive constraints to avoid job and machine conflicts.
# Adapted from: # www.g12.csse.unimelb.edu.au/minizinc/downloads/examples-latest/oss.mzn param endTime integer > 0; param nMach integer > 0; param nJobs integer > 0; param duration {1..nMach, 1..nJobs}; var Start {1..nMach, 1..nJobs} integer >= 0, <= endTime; var Makespan integer >= 0, <= endTime; minimize Objective: Makespan; subject to NoJobConflicts {m in 1..nMach, j1 in 1..nJobs, j2 in j1+1..nJobs}: Start[m,j1] + duration[m,j1] <= Start[m,j2] or Start[m,j2] + duration[m,j2] <= Start[m,j1]; subject to NoMachineConflicts {m1 in 1..nMach, m2 in m1+1..nMach, j in 1..nJobs}: Start[m1,j] + duration[m1,j] <= Start[m2,j] or Start[m2,j] + duration[m2,j] <= Start[m1,j]; subj to MakespanDefn {m in 1..nMach, j in 1..nJobs}: Start[m,j] + duration[m,j] <= Makespan;
param endTime := 2809 ; param nMach := 4 ; param nJobs := 3 ; param duration: 1 2 3 := 1 121 661 6 2 333 168 489 3 343 621 212 4 171 505 324 ;
Line up a group of people to maximize the number of adjacency preferences satisfied, modeling with alldiff, equivalence (<==>), and strict inequality (<)
# A group of people wants to take a group photo. Each person can give # preferences next to whom he or she wants to be placed on the # photo. The problem to be solved is to find a placement that # satisfies as many preferences as possible. # Adapted from # www.g12.csse.unimelb.edu.au/minizinc/downloads/examples-latest/photo.mzn param nPeople integer > 0; set PREFS within {i1 in 1..nPeople, i2 in 1..nPeople: i1 <> i2}; var Sat {PREFS} binary; var Pos {1..nPeople} integer >= 1, <= nPeople; maximize NumSat: sum {(i1,i2) in PREFS} Sat[i1,i2]; subject to OnePersonPerPosition: alldiff {i in 1..nPeople} Pos[i]; subject to SatDefn {(i1,i2) in PREFS}: Sat[i1,i2] = 1 <==> Pos[i1]-Pos[i2] = 1 or Pos[i2]-Pos[i1] = 1; subject to SymmBreaking: Pos[1] < Pos[2];
param nPeople := 9; set PREFS := 1 3 1 5 1 8 2 5 2 9 3 4 3 5 4 1 4 5 5 6 5 1 6 1 6 9 7 3 7 8 8 9 8 7 ;
param nPeople := 11; set PREFS := 1 3 1 5 1 8 2 5 2 9 3 4 3 5 4 1 4 5 4 10 5 6 5 1 6 1 6 9 7 3 7 8 8 9 8 7 9 10 10 11 ;
Hoist scheduling model using disjunctive constraints
# Robert Rodosek and Mark Wallace # A Generic Model and Hybrid Algorithm for Hoist Scheduling Problems # in Michael J. Maher and Jean-Francois Puget eds. # Principles and Practice of Constraint Programming - CP98, # Springer, Lecture Notes in Computer Science, volume 1520, 1998. # Adapted from # www.g12.csse.unimelb.edu.au/minizinc/downloads/examples-latest/singHoist2.mzn param numTanks integer > 0; param numJobs integer > 0; param empty {0..numTanks, 0..numTanks}; param full {0..numTanks}; param minTime {1..numTanks}; param maxTime {1..numTanks}; param perMax = sum {i in 1..numTanks} maxTime[i]; var Entry {0..numTanks} integer >= 0, <= numJobs * perMax; var Removal {0..numTanks} integer >= 0, <= numJobs * perMax; var Period integer >= 0, <= perMax; minimize Objective: Period; subj to Balance {t in 0..numTanks}: Removal[t] + full[t] = Entry[(t+1) mod (numTanks+1)]; subj to EntRem {t in 1..numTanks}: Entry[t] + minTime[t] <= Removal[t] and Entry[t] + maxTime[t] >= Removal[t]; subj to Disjoint {t1 in 0..numTanks-1, t2 in t1+1..numTanks, k in 1..numJobs-1}: Entry[(t1+1) mod (numTanks+1)] + empty[(t1+1) mod (numTanks+1),t2] <= Removal[t2] - k * Period or Entry[(t2+1) mod (numTanks+1)] + empty[(t2+1) mod (numTanks+1),t1] <= Removal[t1] + k * Period; subj to RemovalInit: Removal[0] = 0; subj to RemovalLImit: Removal[numTanks] + full[numTanks] <= numJobs * Period;
param numTanks := 3; param numJobs := 3; param empty: 0 1 2 3 := 0 0 2 3 3 1 2 0 2 3 2 3 2 0 2 3 3 3 2 0 ; param full := 0 4 1 4 2 4 3 5 ; param minTime := 1 10 2 25 3 10 ; param maxTime := 1 10 2 25 3 10 ;
param numTanks := 4; param numJobs := 4; param empty: 0 1 2 3 4 := 0 0 2 3 3 3 1 2 0 2 3 2 2 3 2 0 2 2 3 3 3 2 0 0 4 2 3 1 4 2 ; param full := 0 4 1 4 2 4 3 5 4 2 ; param minTime := 1 10 2 25 3 10 4 40 ; param maxTime := 1 10 2 25 3 10 4 40 ;
Model to solve instances of the 3 x 3 Sudoku problem, using the alldiff operator
param given {1..9, 1..9} integer, in 0..9; # given[i,j] > 0 is the value given for row i, col j # given[i,j] = 0 means no value given var X {1..9, 1..9} integer, in 1..9; # x[i,j] = the number assigned to the cell in row i, col j subj to AssignGiven {i in 1..9, j in 1..9: given[i,j] > 0}: X[i,j] = given[i,j]; # assign given values subj to Rows {i in 1..9}: alldiff {j in 1..9} X[i,j]; # cells in the same row must be assigned distinct numbers subj to Cols {j in 1..9}: alldiff {i in 1..9} X[i,j]; # cells in the same column must be assigned distinct numbers subj to Regions {I in 1..9 by 3, J in 1..9 by 3}: alldiff {i in I..I+2, j in J..J+2} X[i,j]; # cells in the same region must be assigned distinct numbers
param given default 0: 1 2 3 4 5 6 7 8 9 := 1 . . 1 . 8 . 3 . . 2 4 5 . . 6 . . 2 . 3 . . 9 . . 3 7 6 . 4 . . . 8 9 . . 3 7 5 . 1 7 5 . 2 6 9 . 6 3 9 . . 4 7 . . . 7 . 4 5 9 . . 8 . . 8 . 2 . . 5 . . 1 6 9 . . 6 . 7 . 4 . . ;
param given default 0: 1 2 3 4 5 6 7 8 9 := 1 2 . 4 . . . . 5 . 2 . 9 . . . 8 . . . 3 8 . . 1 . . . 2 . 4 . . 7 3 6 . . 8 . 5 . . 8 . . . 2 . . 6 . 3 . . 2 1 7 . . 7 . 8 . . . 3 . . 4 8 . . . 5 . . . 6 . 9 . 4 . . . . 8 . 5 ;