76

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$, ...


22

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+x_2−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 ...


22

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 ...


14

No, special cases can be easier. Consider this IP, for example, given $a_i \geq 0$ for $i \in [1..n]$: $\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$ (that for which, inevitably, $x_i=1$ in an optimal ...


12

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.


9

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 $\...


9

Let me answer your questions one by one: The solution of the linear program $\max x$ is $\infty$. This is an example with not finite optimum solution. This is the same as just having no optimum solution. When adding slack variables, the optimum value remains unchanged. As an example, you change $x \geq y$ to the equivalent $x = y+z$, where $z \geq 0$. You ...


8

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 ...


8

"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 &...


7

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

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

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

I think I can do it with one extra binary variable $\delta \in \{0,1\}$: $$ -100y \le x \le 100 y $$ $$ 0.001y-100.001\delta \le x \le -0.001y+100.001 (1-\delta) $$ Update This assumes $x$ is a continuous variable. If we restrict $x$ to be integer valued, then the second constraint can be simplified to: $$ y-101\delta \le x \le -y+101 (1-\delta) $$


6

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 ...


6

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 ...


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 projection ...


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

The lower bounds on extended formulations (the one by Rothvoss for example) are lower bounds for a very specific way of using Linear Programming to solve a problem (matching in this case). In this model, given a graph you would like to write one linear program, changing whose objective function gives you the right matching corresponding to any weight ...


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

Yes, some IP formulations are less useful than others. The technique used to show that an LP relaxation can only be so good is showing integrality gaps. For a minimization problem, an integrality gap of $k$ in an instance in which the optimal integer solution has value $V$ but the LP has a solution of value at most $V/k$. This shows that any rounding ...


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

Take the convex hull of your set of points. Then use "rotating calipers" to find the optimal strip. What is needed here to make this work is a lemma that characterizes a potentially optimal solution: Could the optimum occur without one supporting line through two points ("flush" to the hull)? Added. Yes, that flush-lemma holds, because more-horizontal ...


5

This can be expressed with just the equation $X=Y$. Since $X,Y$ are zero-or-one variables, the only possible assignments that are consistent with your condition are $X=Y=0$ and $X=Y=1$. See Express boolean logic operations in zero-one integer linear programming (ILP) for many more boolean conditions and how to express them as linear inequalities.


5

What you're proposing isn't "a linear program for TSP", so it doesn't come into the scope of the proof. You've observed that, if $\mathrm{P=NP}$, then TSP can be reduced to polynomial-sized linear programs. You're using a polynomial-time Turing machine to perform a slightly more complicated version of the following reduction: if the input graph $G$ ...


5

The linear program defining the minimum fractional vertex cover always has an optimal solution. The fact that some linear programs are infeasible or unbounded doesn’t mean that every linear program is infeasible or unbounded. To give another example, sometimes you can’t divide by $x$. But if $x$ is a positive integer, then you can always divide by $x$. This ...


5

You can add a variable $y$ and a linear equality $y=c^Tx+c_0$ for some $c_0$. Then, the original problem is equivalent to maximizing $y$ in the new system. Except for the condition $y\geq 0$. That is where $c_0$ comes in. We need to make $c_0$ large enough that for some feasible $x$ (that is $Ax=b$ and $x\geq 0$ hold) we have $c^Tx+c_0\geq 0$. In that case ...


4

The textbook Bellman-Ford algorithm will indeed minimize the span of the variables: $max_i(x_i) - min_i(x_i)$. It involves adding a supernode and 0-weight edges from the supernode to every other nodes in the graph. This is probably what the op is referring to. To maximize $x_n - x_1$, as usual, convert the difference constraints to edges. However, we will ...


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