65

Logical AND: Use the linear constraints $y_1 \ge x_1 + x_2 - 1$, $y_1 \le x_1$, $y_1 \le x_2$, $0 \le y_1 \le 1$, where $y_1$ is constrained to be an integer. This enforces the desired relationship. (Pretty neat that you can do it with just linear inequalities, huh?) Logical OR: Use the linear constraints $y_2 \le x_1 + x_2$, $y_2 \ge x_1$, $y_2 \ge x_2$, ...


23

The following answer is basically equivalent to the one you already know, but may seem a bit less "magical". On the other hand, it's more technical, but I believe the general technique "write your problem as an optimization on permutation matrices and invoke Birkhoff-von Neumann" is a great one to know. For a permutation $\sigma$ of $\{1, \ldots, n\}$ ...


19

The logical AND relation can be modeled in one range constraint instead of three constraints (as in the other solution). So instead of the three constraints $$y_1\geq x_1+x2−1,\qquad y_1\leq x_1,\qquad y_1\leq x_2\,,$$ it can be written using the single range constraint $$0 \leq x_1 + x_2-2y_1 \leq 1\,.$$ Similarly, for logical OR: $$0 \leq 2y_1 - x_1 - x_2 ≤...


16

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard. It is perfectly possible for other specific classes of instances to be solvable in polynomial time. Consider for example the problem of finding a 3-coloration of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted ...


12

No, special cases can be easier. Consider this IP, for example: $\qquad\displaystyle \min \sum_{i=1}^n x_ia_i$ s.t. $\quad\displaystyle\sum_{i=1}^n x_i \geq 1$ and $\ \displaystyle x_i \in \mathbb{N}$ for $i \in [1..n]$. It finds the minimum among $a_1, \dots, a_n$ which is clearly polynomial.


11

This problem is still open. See for example Wikipedia, which while not a dependable source in general, will probably be updated if a strongly polynomial time algorithm is ever found.


10

For asymptotic bounds, Fiorini, Massar, Pokutta, Tiwari, and de Wolf recently showed exponential lower bounds on the number of facets of any polytope that projects to the TSP polytope (the TSP polytope, being the convex hull of feasible TSP solutions). This is stronger than what you ask for, and implies that even adding extra variables will not make the TSP ...


8

All constraints in a linear program are convex (if $x,y$ satisfy the constraints, then $tx+(1-t)y$ also does for all $0 \leq t \leq 1$). The constraint $|a|+b > 3$ is not convex, since $(4,0)$ and $(-4,0)$ are both solutions while $(0,0)$ is not. It is also not closed, which is another reason why you cannot use it in a linear program (change $>$ to $\...


7

What you describe is a linear program. You can use the following formulation: Let $x_i$ be the $i$th element. The variables are $d_1,\ldots, d_{n-1}$, where $d_i$ denotes difference between $x_{i+1}$ and $x_i$. You require $d_i\ge 0$. If two elements $x_i,x_j$ should be at least within some distance $\ell^-_{ij}$, then you set $$ d_i+d_{i+1}+\cdots +d_{j-1}...


7

Reduction from 3SAT to the two-vector version: given a formula, let $i$ index variables, $j \in \{0,1\}$, and $k$ index clauses. Let $a_{i,j,k}$ be the number of times variable $i$ appears positively (if $j = 0$) or negatively (if $j = 1$) in clause $k$. OPT is less than $3$ iff the formula is satisfiable (the bijection is obvious). How I would attack this ...


7

We cannot discuss the complexity of a problem when the problem size is fixed to a constant, because (most part of) the complexity theory deals with the asymptotic behavior of the complexity of the problem as the problem size tends to infinity. Here, I consider both the number of rows and the dimention of the vectors as variables. Then the problem is NP-...


7

"Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope. This problem has a polynomial-time algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok &...


6

This can be formulated as an instance of min-cost (or in this case, max-profit) flow. Set up a network as follows. There will be four layers. The first layer is a single node we call the source. The next layer consists of a node for each agent. The next layer has a node for each task. The final layer is one node we call the sink. For each edge, we give a ...


6

Of course, if you round, you have to verify that rounding preserves feasibility. Let us for example consider the relaxed VERTEX-COVER LP formulation. $$ \begin{array}{lll} \text{min} & \sum_{v\in V}c(v)x_v & \\ \text{s.t.} &x_u+x_v\ge1, & \quad (u,v)\in E \\ &x_v\ge 0. & \quad v\in V \end{array} $$ It is known that the solution to ...


6

Restating the problem. As far as I can tell, your system is equivalent to the following: $$c_1 x_1 + \dots + c_n x_n = N$$ subject to the constraints $$0 \le x_1, \dots, x_n \le 1.$$ Solving this problem. This is a linear program, so certainly we can tell in polynomial time whether it has any feasible solution, as a result of the fact that there are ...


6

Here is an example of this anomaly in linear programs: $$ \begin{align*} & \max x & & \min \infty y \\ s.t.\; & x \leq \infty & s.t.\; & y \geq 1 \\ & x \geq 0 & & y \geq 0 \end{align*} $$ The solution to both programs is $\infty$. What goes wrong? The duality theorem only works when all coefficients are finite. If you ...


6

I've found out a very interesting document that answers my question: http://lpsolve.sourceforge.net/5.5/absolute.htm It's about integer programming and it covers all possible cases I think. See section >= minimum to handle abs(X) >= minimum. Here is another one with more tricks: http://orinanobworld.blogspot.de/2012/07/modeling-absolute-values.html There ...


6

There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l_i=u_i$ then the problem is to determine if there is a subset of the $u_i$ that sums to $C$ (which is the Subset Sum problem). If your problem did not allow $l_i=u_i$, if you were to require that $l_i<x_i<...


6

In $\mathbb R$, one can simply round down or round up to obtain an element of $\mathbb Z$. Only two choices! However, in $\mathbb R^n$, one has $2^n$ ways of rounding to obtain an element of the integer lattice $\mathbb Z^n$. For example, if $n=100$, one has $2^{100} \approx 10^{30}$ possible ways of rounding. Of course, one can round all entries of an $n$...


6

What Fiorini et al. show is the following: The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete graph on $n$ vertices). (That is, it is the convex hull of the indicator vectors of all Hamiltonian cycles.) Suppose that $X_n$ is a polytope whose ...


6

First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a class of problem instances. It makes no sense to speak of polynomial time for a single problem as any single problem can be solved in $O(1)$! That said, there is a notable class of ILP's that is known to be polynomial time solvable. This ...


5

According to your description: Each node in the network can relay a certain amount of traffic per time unit. Each link has a certain capacity. In order to convert your problem to an instance of network flow problem, one can do the following transformation. In the underlying graph of network, $G = (V,E)$, for any vertex $u \in V$ that has an outgoing edge $(...


5

This answer is mostly a recap of the comments on the question above. If a problem is NP-complete, it can indeed be reduced to ILP, by using Karp's reductions (― Joe, andy). Claims of "polynomial sized formulations" from one problem to another, are likely meant as more direct formulations, as opposed to multiple reductions through SAT (― Kaveh).


5

Sure, of course you can create random linear programming problems. Why not? Yes, in general, you can usually verify the solution to a linear programming problem faster than you can find the solution. Verifying the solution just involves plugging into the equations and checking that all equations hold. Finding the solution requires a bit more work (e.g., ...


5

The running time of algorithms for linear programming depends not only on the number of variables but also, unsurprisingly, on the number of constraints. This is hidden in the parameter $L$ which is the input size; clearly $L$ is at least the number of constraints. If there are exponentially many constraints, then any generic algorithms must take exponential ...


5

If there are only constraints that place a lower bound on the number of trucks, but no constraints that place an upper limit on the number of trucks, then of course you can round up. That will still give you a solution. However, there are multiple caveats: First, this isn't always possible. Sometimes there are both constraints that place lower limits and ...


5

A quadratic program is an optimization problem where the goal is to minimize $y^T Q y + c^T y$ subject to $A y \leq b$. If $Q$ is positive definite, then this is a convex quadratic program and we can solve this problem in polynomial time using several methods, one being the ellipsoid method (originally due to Kozlov, Tarasov and Khachiyan [1]). We can ...


Only top voted, non community-wiki answers of a minimum length are eligible