In [1] an intriguing problem is posted:

There are 8 soldiers, gathering and lining up every morning for their military service. The commander at the head of these soldiers demands that the morning lineup of these soldiers be arranged differently for every next day according to the following rule:

Any three soldiers cannot be lined up next to each other in the same order for others days.

For example; If ABCDEFGH is the first arrangement for day 1, on the other days, ABC,BCD, CDE, DEF, EFG and FGH cannot be lined up next to each other in the same order any more, but ACB arrangement is okay for other days until used once since they are not in the same order.What is the maximum number of days can this happen?

Let's first make the problem a bit smaller. Say we have just 4 soldiers. This gives us \(4!=24\) permutations or line-ups. Let's have a look at the following sets:

- \(p\) is the set of permutations
- \(t\) is the set of substrings of length 3 that we can form from \(p\)
- \(\color{darkblue}pt(p,t)\) is the mapping between \(p\) and \(t\)

---- 53 SETppermutations or line upsABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, DCBA ---- 53 SETtsubstrings of length 3ABC, BCD, ABD, BDC, ACB, CBD, ACD, CDB, ADB, DBC, ADC, DCB, BAC, BAD, BCA CAD, CDA, BDA, DAC, DCA, CAB, CBA, DAB, DBA ---- 55 SETptmapping (computed in Python)ABCD.ABC, ABCD.BCD, ABDC.ABD, ABDC.BDC, ACBD.ACB, ACBD.CBD, ACDB.ACD ACDB.CDB, ADBC.ADB, ADBC.DBC, ADCB.ADC, ADCB.DCB, BACD.ACD, BACD.BAC BADC.ADC, BADC.BAD, BCAD.BCA, BCAD.CAD, BCDA.BCD, BCDA.CDA, BDAC.BDA BDAC.DAC, BDCA.BDC, BDCA.DCA, CABD.ABD, CABD.CAB, CADB.ADB, CADB.CAD CBAD.BAD, CBAD.CBA, CBDA.CBD, CBDA.BDA, CDAB.CDA, CDAB.DAB, CDBA.CDB CDBA.DBA, DABC.ABC, DABC.DAB, DACB.ACB, DACB.DAC, DBAC.BAC, DBAC.DBA DBCA.DBC, DBCA.BCA, DCAB.DCA, DCAB.CAB, DCBA.DCB, DCBA.CBA ---- 66 PARAMETERnp= 24card(p)PARAMETERnt= 24card(t)PARAMETERnpt= 48card(pt)

Model A |
---|

\[\begin{align}\max\> & \color{darkred}z = \sum_p \color{darkred}x_p \\ &\sum_{p|\color{darkblue}{pt}(p,t)} \color{darkred}x_p \le 1&& \forall t \\ & \color{darkred}x_p \in \{0,1\}\end{align} \] |

---- 90 VARIABLEx.Luse a lineupABCD 1, ABDC 1, BACD 1, BADC 1, CADB 1, CBDA 1, CDAB 1, CDBA 1, DACB 1, DBCA 1, DCAB 1 DCBA 1 ---- 90 VARIABLEz.L = 12number of lineups

---- 103 PARAMETERnpairs= 24number of pairs to forbid---- 104 SETpairspairs we need to forbidABCD.BCDA, ABCD.DABC, ABDC.BDCA, ABDC.CABD, ACBD.CBDA, ACBD.DACB, ACDB.BACD ACDB.CDBA, ADBC.CADB, ADBC.DBCA, ADCB.BADC, ADCB.DCBA, BACD.DBAC, BADC.CBAD BCAD.CADB, BCAD.DBCA, BCDA.CDAB, BDAC.CBDA, BDAC.DACB, BDCA.DCAB, CABD.DCAB CBAD.DCBA, CDAB.DABC, CDBA.DBAC

Model B |
---|

\[\begin{align}\max\> & \color{darkred}z = \sum_p \color{darkred}x_p \\ &\color{darkred}x_p+\color{darkred}x_{p'} \le 1&& \forall p,p'|\color{darkblue}{\mathit{pairs}}(p,p')\\ & \color{darkred}x_p \in \{0,1\}\end{align} \] |

This is essentially a disaggregated version of model A. The solution is:

---- 112 VARIABLEx.Luse a lineupABCD 1, ABDC 1, BACD 1, BADC 1, CADB 1, CBDA 1, CDAB 1, CDBA 1, DACB 1, DBCA 1, DCAB 1 DCBA 1 ---- 112 VARIABLE z.L = 12 number of lineups

---- 65 PARAMETERnp= 5040card(p)PARAMETERnt= 210card(t)PARAMETERnpt= 25200card(pt)---- 105-------------- Model A ------------------ 105 VARIABLEx.Luse a lineupABCDEFG 1, ACFDGBE 1, ADBFCGE 1, AEBCGDF 1, AGCBFED 1, AGEBDCF 1, AGFBEDC 1, BAEDGFC 1 BCFAGDE 1, BDGCFEA 1, BECDFGA 1, BEGCADF 1, BFAEGDC 1, BGEFDAC 1, CBDEGFA 1, CEFABGD 1 CFGDABE 1, CGAFDEB 1, DAFGBCE 1, DCEAGBF 1, DCGFEBA 1, DEABFGC 1, DFACEBG 1, DFECBAG 1 DGEAFBC 1, EACBGFD 1, EBFDCAG 1, ECFBDAG 1, EDFBACG 1, EFCDGAB 1, FADECGB 1, FBGCEDA 1 FCBEADG 1, FCEGBAD 1, FDBGAEC 1, FEGADCB 1, FGECABD 1, GACDBEF 1, GBDFCAE 1, GCDAEFB 1 GDBCAFE 1, GEDBAFC 1 ---- 105 VARIABLEz.L = 42number of lineups---- 105 PARAMETERreportresultsModel A Variables 5041.000 Equations 211.000 Objective 42.000 Time 67.969 Nodes 29299.000 Iterations 1470790.000 ---- 120 PARAMETERnpairs= 1239840number of pairs to forbid---- 133-------------- Model B ------------------ 133 VARIABLEx.Luse a lineupABCDEFG 1, ACDBFEG 1, AFCGDEB 1, AGFBCED 1, BAECDFG 1, BDGACFE 1, BEGCDAF 1, BFCEGDA 1 BGCFAED 1, CAFGEDB 1, CAGDFEB 1, CBAFEDG 1, CBGEFDA 1, CDGEAFB 1, CEBGAFD 1, CFBADEG 1 DACGBEF 1, DAEBCGF 1, DBAGECF 1, DCAEGBF 1, DFBECGA 1, DGFACBE 1, EABGFCD 1, EAGBCFD 1 EBDFAGC 1, EBFADGC 1, EDABFGC 1, EDCFGAB 1, EFCADBG 1, EGADFCB 1, EGFDBCA 1, FBGDCEA 1 FDCGEBA 1, FDGBACE 1, FECBDAG 1, FGBDECA 1, FGDBEAC 1, GAEFBDC 1, GCABEDF 1, GCBFDEA 1 GCEFABD 1, GFEADCB 1 ---- 133 VARIABLEz.L = 42number of lineups---- 133 PARAMETERreportresultsModel A Model B Variables 5041.000 5041.000 Equations 211.000 1239841.000 Objective 42.000 42.000 Time 67.969 263.516 Nodes 29299.000 180432.000 Iterations 1470790.000 8709140.000

#### References

- 8 soldiers lining up for the morning assembly, https://puzzling.stackexchange.com/questions/106030/8-soldiers-lining-up-for-the-morning-assembly/106047 Note the answer by Rob Pratt.
- Optimizing Gurobi model (PuLP) for a symmetric MIP with binary variables, https://stackoverflow.com/questions/65480166/optimizing-gurobi-model-pulp-for-a-symmetric-mip-with-binary-variables

#### Appendix: GAMS model

**itertools**, which has direct support for generating all permutations.

$ onEmbeddedCode Python:from itertools import permutationsM = 3 #
length of substring#S = "ABCDEFGH" # too difficultS = "ABCDEFG" # easier: use
7 soldierspt = [] for p in permutations(S):sp = ''.join(p) # convert tuple to stringfor k in range(len(S)-M+1):st = sp[k:k+M] # substring of
length Mpt.append((sp,st)) # store
element p.t in list ptgams.set("pt",pt) # convert to GAMS set$offEmbeddedCode pt
display$(card(p)<1000) p,t;option pt:0:0:7;display$(card(pt)<1000) pt;scalarsnp "card(p)"nt "card(t)"npt "card(pt)"; option
np:0,nt:0,npt:0;np = card(p);nt = card(t);npt = card(pt);display np,nt,npt;*-----------------------------------------------* Reporting macro*-----------------------------------------------parameter report(*,*) 'results';$macro results(m,name) \ report('Variables',name) = m.numvar; \ report('Equations',name) = m.numequ; \ report('Objective',name) = m.objval; \ report('Time',name) = m.resusd; \ report('Nodes',name) = m.nodusd; \ report('Iterations',name) = m.iterusd; *-----------------------------------------------* optimization model A*-----------------------------------------------binary variable x(p) 'use a lineup';variable z 'number of lineups';equationsobj 'objective'once 'use triples once'; obj.. z =e= sum(p,x(p));once(t).. sum(pt(p,t),x(p)) =l= 1;model m /all/;option
optcr=0,threads=4,reslim=9999;solve m maximizing
z using mip;results(m,"Model A") option x:0,z:0;display"-------------- Model A --------------", x.l,z.l,report; *-----------------------------------------------* optimization model B*-----------------------------------------------alias (p,pp);set pairs(p,pp) 'pairs we need to forbid';pairs(p,pp)$( ord(p)<ord(pp)) = sum(t$(pt(p,t) and pt(pp,t)),1);scalar npairs "number of pairs to
forbid";npairs = card(pairs);option
npairs:0,pairs:0:0:7;display npairs;display$(npairs<1000)
pairs;abort$(npairs>5e6)
"Too many constraints";equation
oneInPair(p,pp);oneInPair(pairs(p,pp)).. x(p) + x(pp) =l= 1; model m2 /obj,oneInPair/;solve m2
maximizing z using mip;results(m2,"Model B") display"-------------- Model B --------------", x.l,z.l,report; |

## No comments:

## Post a Comment