# Covering a graph with M cliques maximizing total edges weight

I am working on a problem that involves distributing a set of N supplements across a predefined number of meals (M) in a way that maximizes the total number of positive interactions and minimizes negative interactions between the supplements. Each interaction between the supplements is known beforehand (positive, neutral or negative: see the image below).

I'm seeking advice on the mathematical formulation of this problem and potential algorithms or tools that could be used to solve it. Here's what I came up with:

• We can build a graph G from table of compatibility, with edges 1/0/-1 for positive, neutral and negative interactions correspondingly
• Then we can remove -1 edges completely
• Now we have modified graph G' with 0/1 edges only (see the image below)

• And we want to cover it with M cliques (bc clique in this graph will guarantee no 'bad' connections), finding a coverage with maximum number of +1 green edges

This method is not very good because:

• it doesn't consider using -1 red edges at all while building meals
• it has a very big time complexity (hours or days for 1 calculation on ~20 supplements)

I'm open for any suggestions. Maybe there are existing algorithms for solving this problem, or tools (like solvers)? Or is there a name for this problem I could search algorithms for?

One approach is to solve this with tools from operations research and combinatorial optimization, and specifically, to view this as an instance of ILP or SAT.

Let $$x_{c,i}$$ be a variable that will be true (i.e., 1) if supplement $$i$$ is assigned to meal $$c$$, or false (0) otherwise. Let $$y_{c,i,j} = x_{c,i} \land x_{c,j}$$. Let $$r_{i,j}$$ be the reward if supplements $$i,j$$ are used in the same meal ($$+1$$ if they interact positively, $$0$$ if there is no interaction, $$-1$$ if they interact negatively). Then your goal is to maximize $$\sum r_{i,j} y_{c,i,j}$$, subject to constraints that require $$x$$ to be a valid solution.

These constraints can be expressed in SAT or ILP pretty easily:

• Exactly one of $$x_{c,i}$$ is true, for each $$i$$. (In ILP: $$\sum_c x_{c,i} = 1$$. In SAT, this is a 1-out-of-M constraint.)

• $$y_{c,i,j} = x_{c,i} \land x_{c,j}$$. (In ILP: see Express boolean logic operations in zero-one integer linear programming (ILP). In SAT, this is $$(x_{c,i} \lor \neg y_{c,i,j}) \land (x_{c,j} \lor \neg y_{c,i,j}) \land (\neg x_{c,i} \lor \neg x_{c,j} \lor x_{c,i,j})$$.)

Then you can use a SAT solver that supports pseudo-boolean constraints (e.g., Z3) or an ILP solver (e.g., Cplex, Gurobi) to solve this system. If you use a SAT solver, you might want to use binary search over the target value of the objective function, using the SAT solver to search for a solution that achieves that target.

(Optionally, you can add some additional constraints for symmetry breaking, e.g., WLOG you can force $$x_{1,1}$$ to be true, force $$x_{1,2} \lor x_{2,2}$$ to be true, etc.)

If $$N,M$$ are big enough, this won't work, but it might be a simple to implement approach if $$N,M$$ aren't too big.

• Thank you very much for your answer! I'll try to solve this problem using Cplex and Pyomo. If you don't mind, I will not close this topic for 2-3 days, maybe someone will suggest any known algorithms for solving this problem, because it is very similar to clique, set cover. Feb 9 at 17:58
• Unfortunately, I can't vote for your reply because I have <15 reputation. I will do so as soon as I get the ability to do so. Feb 9 at 18:01
• @essacult, waiting for other answers sounds like an excellent idea. I hope someone else will have a better suggestion.
– D.W.
Feb 9 at 20:46