# Tag Info

Accepted

### Does linear programming admit a strongly polynomial-time algorithm?

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.

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

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

### Finding all solutions to an integer linear programming (ILP) problem

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

### Some Questions related to Linear programming

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

### Project to nearest point in convex polytope

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

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

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

### Cast to boolean, for integer linear programming

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

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

Here is a 2d region where rounding the optimal continuous solution (top right) will always give an invalid integer solution: Here is a 2d region where rounding the optimal continuous solution (green ...
Accepted

### Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?

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

### Given 2 sets of n points: minimize sum of traveled distances

As mentioned in the problem statement, this is the Assignment Problem (minimum weight bipartite matching) where it is known that the weights are the Euclidean distances. There have been several ...
Accepted

### Linear programming restricted to rational coefficients

In order to consider the computational complexity of linear programming, we need a way of encoding an instance of linear programming as a string. In particular, we need to fix an encoding of the ...

### Max flow with priorities

First, build an algorithm to solve the following problem: Given a threshold $t$ and a flow graph $G$, find the solution that maximizes $N_2$, subject to the requirement that $N_1 \ge t$. That ...
Accepted

### Expressing conditional in linear program

If you know the maximum value of $B$ then you can easily express all comparisons as described here: https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ In your case you need the following: \$0 \le -B ...
Accepted

### How do you proceed if your milp is not solvable

It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following: Precision Typical solvers report solutions as "optimal" using gap parameters ...
Accepted

### Maximum matching using linear programming

This approach is described by Grötschel, Lovász and Schrijver in their paper The ellipsoid method and its consequences in combinatorial optimization, as well as in their book Geometric algorithms and ...
Accepted

### Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?

Consider this example: Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of ...