Integer programing is one of the most narutal optimization tools.

As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.

$x_{1}x_{2}x_{3}+$ $x_{3}x_{4}x_{5}+x_{1}x_{7}x_{9}=8,x_{i}\in \{0,1\}$

This constraint is not a linear one. However, every variables in any monomial has at most degree $1$.Call constraints of this kind $multi$-$lienar$ constraints.

We consider the following example as a instance of Multi-linear Integer($0$-$1$) programming, which is a system of multi-linear constraints.




$x_{i} \in \{0,1\} $ Where all coefficients of each monomial is integer and polynomial order $n^{O(1)}$($n$ is the number of variables)

Solving Multi-linear 0-1 programming is deciding whether there exists an $0$-$1$ assingment which satisfies all of given multilinear constraints.

Ofcourse $0-1$ programming is a $NP$-complete problem in one of the 21 problems which R.Karp showed their completeness. More over Exponential Time Hypothesis seems to get rid of our hope to construct better sub-exponential time algorithms.

My question is :


Are there any $slightly$ better exponential algorithm for Multi-linear 0-1 programming such as $2^{n-C\log n}$ time, $2^{n-C\log ^{2} n}$ times, or $2^{n-Cn^{0.001}}$ ?($C$ is a constant) ,and are there text-books or papers contains algorithms for integer programming of this type ?

  • 3
    $\begingroup$ It's sort of a funny question, in that "multi-linear 0-1 programming" reduces in linear time to regular (linear) 0-1 programming. E.g. $x_1x_2$ can be represented as $x_{12}$ with the additional constraints $x_{12} \ge x_1 +x_2 - 1$, $x_{12}\le x_2$, $x_{12} \le x_1$. So your question is very specific to the representation of the problem, in particular the number of variables. Also, do you intend all your constraints to be equalities? (Even with equalities one can model inequalities using slack variables, but this changes the number of variables.) $\endgroup$
    – Neal Young
    Mar 19 '13 at 16:48
  • 3
    $\begingroup$ This paper says that this paper suggests that there is no $2^{\delta n}$-time algorithm for CNF-SAT for $\delta < 1$. I think CNF-SAT reduces to your problem (with inequalities) without increasing the number of variables. This is evidence that there is no $2^{\delta n}$-time algorithm for your problem as well. I realize that's a weaker result than you are asking for (you are asking about $2^{n-o(n)}$-time algorithms), but it's a start. $\endgroup$
    – Neal Young
    Mar 19 '13 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.