integer linear programming on 3-partition of a special set

Question

background: Sis a set consisting of the following 7-length sequences s: (1) each digit of s is a, b, or c; (2) s has and only has one digit that is c.

T is a set consisting of the following 7-length sequences t: (1) each digit of t is a, b, or c; (2) t has two digits that are c.

Is there a 3-partition S=A0⋃A1⋃A2, Aj∩Ai=∅ with the following property: for any Aj and any t ∈ T, there is a s ∈ Aj such that exsits a n∈{1,2,3,4,5,6,7}, sn≠tn, tn=c and sm=tm for any m≠n, where sn (or tn) is the n-th digit of s (or t).

For example, t=ccaabca and s=acaabca where n=1.

I used integer linear programming to solve the problem via lingo. I do not know how to solve the original problem directly, but I'd like to have the A0 as small as possible via lingo first. Here is the code:

MODEL:
 SETS: 
Y/1..448/:C,X;
Z/1..672/;   
cooperation(Y,Z):A;
 ENDSETS 
 DATA:
 A=#the big incidence matrix#
 C=#1,1,1,... 448 times 1#
 ENDDATA;
   MIN=@SUM(Y:C*X);
  @FOR(Y:@BIN(X));
  @for(Z(j):@sum(Y(i):X(i)*A(i,j))>1);
  @for(Z(j):@sum(Y(i):X(i)*A(i,j))<2);
END

But the code run a long time without any answer. I appreciate any answers to original questions or suggestions for lingo code.

Answer 1

Seems like a coding theory problem, which tend to be very hard, especially with integer programming due to the symmetry (maybe you have access to a good solver with symmetry breaking, but I still tend to think that constraint programming will fare better). The smallest part of the partition must have at most ⌊448/3⌋ = 149 strings, yet a quick constraint solver setup (OR-Tools CP-SAT solver, below) couldn’t get there in the time that I ran it.

import itertools
import operator

from ortools.sat.python import cp_model

S = set()
T = set()

for s in itertools.product("abc", repeat=7):
    k = s.count("c")
    if k == 1:
        S.add("".join(s))
    elif k == 2:
        T.add("".join(s))


def hamming(s, t):
    return sum(map(operator.ne, s, t))


edges = [(s, t) for s in S for t in T if hamming(s, t) == 1]

model = cp_model.CpModel()
include = {s: model.NewBoolVar(s) for s in S}
for t in T:
    model.AddBoolOr([include[s] for s in S if hamming(s, t) == 1])
model.Minimize(sum(include.values()))
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
status = solver.Solve(model)
print({s for s in include if solver.Value(include[s])})