<p>Integer programing is one of the most narutal optimization tools.</p>
<p>As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.</p>
<p><span class="math-container">$x_{1}x_{2}x_{3}+$</span> <span class="math-container">$x_{3}x_{4}x_{5}+x_{1}x_{7}x_{9}=8,x_{i}\in \{0,1\}$</span></p>
<p>This constraint is not a linear one. However, every variables in any monomial has at most degree <span class="math-container">$1$</span>.Call constraints of this kind <span class="math-container">$multi$</span>-<span class="math-container">$lienar$</span> constraints.</p>
<p>We consider the following example as a instance of Multi-linear Integer(<span class="math-container">$0$</span>-<span class="math-container">$1$</span>) programming, which is a system of multi-linear constraints.</p>
<p><span class="math-container">$5x_{1}x_{2}x_{3}+2x_{3}x_{4}x_{5}+x_{1}x_{7}x_{9}=8$</span></p>
<p><span class="math-container">$11x_{1}x_{3}+3x_{2}x_{4}x_{6}+23x_{3}x_{7}x_{8}+x_{10}=4$</span></p>
<p><span class="math-container">$x_{2}x_{6}+4x_{3}x_{4}x_{5}+5x_{5}x_{7}x_{9}=4$</span></p>
<p><span class="math-container">$x_{i} \in \{0,1\} $</span>
Where all coefficients of each monomial is integer and polynomial order <span class="math-container">$n^{O(1)}$</span>(<span class="math-container">$n$</span> is the number of variables)</p>
<p>Solving Multi-linear 0-1 programming is deciding whether there exists an <span class="math-container">$0$</span>-<span class="math-container">$1$</span> assingment which satisfies all of given multilinear constraints.</p>
<p>Ofcourse <span class="math-container">$0-1$</span> programming is a <span class="math-container">$NP$</span>-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.</p>
<p>My question is :</p>
<h1>Q</h1>
<p>Are there any <span class="math-container">$slightly$</span> better exponential algorithm for Multi-linear 0-1 programming such as <span class="math-container">$2^{n-C\log n}$</span> time, <span class="math-container">$2^{n-C\log ^{2} n}$</span> times, or <span class="math-container">$2^{n-Cn^{0.001}}$</span> ?(<span class="math-container">$C$</span> is a constant) ,and are there  text-books or papers contains algorithms for integer programming of this type ?</p>

CC BY-SA 3.0
2013-03-19T16:48:12.770Z
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.)
Neal Young
CC BY-SA 3.0
2013-03-19T17:13:10.303Z
[This paper](https://www.siam.org/proceedings/soda/2010/SODA10_086_patrascum.pdf) says that [this paper](http://scholar.google.com/scholar?cluster=4468909587780165320&hl=en&as_sdt=0,5) 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.
Neal Young
<reference-request><np-hardness><optimization><integer-programming><exp-time-algorithms>
Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables
echuly
# Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables

(Asked by: username_0 on 2013-03-19)

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.

$5x\_{1}x\_{2}x\_{3}+2x\_{3}x\_{4}x\_{5}+x\_{1}x\_{7}x\_{9}=8$

$11x\_{1}x\_{3}+3x\_{2}x\_{4}x\_{6}+23x\_{3}x\_{7}x\_{8}+x\_{10}=4$

$x\_{2}x\_{6}+4x\_{3}x\_{4}x\_{5}+5x\_{5}x\_{7}x\_{9}=4$

$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 :

# Q

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 ?

**Tags:** reference-request, np-hardness, optimization, integer-programming, exp-time-algorithms

> **Comments:**
> **username_1**: 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.)  
> **username_1**: [This paper](https://www.siam.org/proceedings/soda/2010/SODA10_086_patrascum.pdf) says that [this paper](http://scholar.google.com/scholar?cluster=4468909587780165320&hl=en&as_sdt=0,5) 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.  

---

## 0 answers

