# Tag Info

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 ... 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 ... 4 I don't know what class this is for, and how much linear programming you are learning in it, so I don't really know what you need. One way to do it: assuming a_i + b_i + c_i = 1, \ \forall i, use the linear program:$$ \max x$$such that$$\eqalign{ \sum_i a_i \lambda_i &= a,\\ \sum_i b_i \lambda_i &= b,\\ \sum_i c_i \lambda_i &= c, \\ \...

4

We can encode satisfiability of a SAT instance as the feasibility of a 0-1 integer linear program. For feasibility, the objective function doesn't matter, so you can impose whatever constraint you wish on it. For an example of how to express boolean or, boolean and, and boolean negation in a 0-1 integer linear program, see Express boolean logic operations ...

4

I have a method for you that will help you find valid solutions (matrices) for many possible values of $m,n$. However, it is not a complete answer to your question. It can try to find a matrix for a particular value of $m,n$, but it might fail, and if it fails, you've learned nothing; my method cannot prove that no such matrix exists. The method is based ...

4

Answering your first question, whether you can tighten the analysis depends on the function $T$. If $T$ is constant, for example, then the analysis is tight; if $T$ is a polynomial, then the analysis is not tight, and in fact you can remove the logarithmic factor: the answer is simply $O(T(N))$. Answering your second question, the best known time complexity ...

4

A linear program consists of a finite collection of inequalities of the form $\sum_i a_ix_i \leq b_i$. Each such inequality defines a closed convex set, and so their intersection defines a closed convex set. Any domain which is not closed and convex thus cannot be represented using linear programming constraints.

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