11
$\begingroup$

Given $n$ items, I want to select a set items $S\subseteq\{1,2,\dots,n\}$ that maximize profit. The profit of item $i\in\{1,2,\dots,n\}$ is given by $p_i$ and may be assumed to be non-negative.

Additionally, I have a set $\mathscr{F}$ of forbidden subsets. That is, if $F \in \mathscr{F}$, then $S$ is not allowed to contain $F$ as a subset.

For example: if $n=3$, profits are given by $p_1=p_2=p_3=1$, and the forbidden subsets are given by $\mathscr{F} = \{\{1,2\},\{2,3\}\}$, then the optimum is given by $S=\{1,3\}$ with profit $2$.

My question is how to best approach this problem.

Currently, I am using a knapsack problem type formulation that I solve with CPLEX. This works relatively well, but I am interested if better approaches exist, especially because I do not have any side constraints.

$$\max \sum_{i=1}^n p_i x_i,$$ $$\sum_{i \in F} x_i \le \lvert F \rvert - 1, \forall F \in \mathscr{F},$$ $$x \in \{0,1\}^n.$$

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Is the size of your forbidden subsets bounded or small? If the size is at most $2$, then this seems to be an instance of the weighted independent set problem. If the size is larger, then I think this can be reformulated as some sort of weighted proper graph coloring problem, but I have no idea if that formulation would be easier to solve. $\endgroup$
    – Discrete lizard
    Jun 30, 2019 at 13:14
  • $\begingroup$ Good point: you indeed seem to get the independent set problem for $\lvert F \rvert = 2$. In my application I am interested in larger forbidden sets (often exceeding size $n$/2), but I will check if the independent set literature provides new insights. $\endgroup$
    – Kevin Dalmeijer
    Jun 30, 2019 at 13:48
  • 1
    $\begingroup$ High cardinality forbidden sets will jack up the density of the constraint matrix (slowing the solver) and, I think, weaken the LP relaxation. Not much you can do about that. What about the cardinality of $\mathscr{F}$? Do you tend to have lots of forbidden sets, or comparatively few? $\endgroup$
    – prubin ♦
    Jun 30, 2019 at 17:57
  • $\begingroup$ I also tend to have a relatively large number of forbidden sets, say exponential in n. $\endgroup$
    – Kevin Dalmeijer
    Jun 30, 2019 at 18:16

2 Answers 2

Reset to default
9
$\begingroup$

Your problem is equivalent to finding a maximum weighted independent set in a hypergraph, where each item is a vertex and every forbidden set is an hyperedge over the elements in the set.

This is a hard problem, not just NP-hard (since it is a generalisation of the NP-hard weighted independent set problem), but also NP-hard to approximate within a constant factor (Because independent set is also NP-hard to approximate1).

What this means is that unless your specific instances have some structure that can be exploited, heuristic solutions or MILP, SAT, etc. solvers are going to be the best you can do for this problem.

There is some literature on the (non-weighted) independent set problem in hypergraphs. Most of the results I see are about regular or uniform hypergraphs, where all hyperedges have the same size. So, in case your forbidden subsets have different cardinality, then there doesn't really seem to be much research about your problem.

All in all, I think this provides some evidence that there is not much better you can do than you already did. I'm happy to be proven wrong, of course, in which case the literature on hypergraphs may help.

1: It is known to be NP-hard to get a better approximation ratio than $n/2^{(\log n)^{3/4+\gamma}}$ for any $\gamma>0$, see Khot, S., & Ponnuswami, A. K. (2006, July). Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In International Colloquium on Automata, Languages, and Programming (pp. 226-237). Springer, Berlin, Heidelberg.

Improve this answer
$\endgroup$
7
$\begingroup$

Since this problem has exponentially many constraints, I suspect that most forbidden subset constraints (FSCs) will not be binding at optimality. Therefore, something which you could try is: (a) pick a promising set of FSCs to add apriori and (b) add the remaining forbidden constraints via lazy callbacks, where you add the "most violated" constraint at each iteration.

If you know that some of the FSCs imply other FSCs then you should also ignore the redundant constraints. In practise, this means that you should favour adding hidden subsets of small cardinality first.

Improve this answer
$\endgroup$
1
  • $\begingroup$ N.b. a minimal working example which uses lazy constraints with JuMP.jl version 0.18 and Gurobi is given here $\endgroup$
    – Ryan Cory-Wright
    Jun 30, 2019 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.