# Tag Info

Accepted

### Why can't we round results of linear programming to get integer programming?

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 ...
• 150k
Accepted

### Complexity of solving LP with a non-linear growth in variables/constraints

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 ...
• 273k
Accepted

### Unfeasible linear program becomes feasible if a variable is removed

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 ...
• 13.1k
Accepted

### How to check if a specific ILP problem can be solved in polynomial time or not?

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 ...
• 7,268
Accepted

### Are some Integer programming formulations completely useless for relaxation?

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 ...
• 273k

### Can you generate random linear programming problems?

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....
• 150k
Accepted

### Finding a minimal width strip which encloses a set of points in the plane

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

### Converting If-else condition to Linear Programming

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 ...
• 150k

### Why does this not prove $P\neq NP$?

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

### Fractional vertex cover number may not be feasible? Very confusing!

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 ...
• 273k
Accepted

### Reducing linear programming to positive linear programming

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 ...
• 2,144
Accepted

• 366