# Looking for fast LP solver algorithm for my Special case

I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly appreciated and I would appreciate you providing me with relevant papers as well.

Context: I am trying to give an algorithm related to graph theory. Unfortunately, my knowledge of LP is very limited that is why I need your guidance. In the following algorithm $$2k$$ is the degree of the investigated vertex. Ideally, I am looking for $$O(k)$$ or $$O(k \log k)$$ solution, or in total $$O(n)/O(n\log n)$$ when this applies to all the vertices. Note that $$|E|= O(n)$$. However, any fast algorithm would be appreciated.

Modification and Clarifications (Edit):
There was a mistake as pointed out by @D.W. I changed the program. Beside $$t_i$$'s which I need to be distinct positive integers between $$1$$ to $$2k$$, there are variables $$x_i$$'s and $$T$$. Originally, I want $$T$$ to be an integer and $$x_i$$ to be $$0$$ or $$1$$; however, it is not important. If we find an optimal solution in which $$T$$ and $$x_i$$'s are real values I have a $$O(k)$$ mechanism to find the solution I want based on it. Do we have a polynomial solution to this program? (based on $$n$$, number of vertices.) (Any other LP comes to mind such that it forces $$t_i$$ condition but does not make it Integer Program?)

Minimize: $$T$$
Subject to:
$$\forall i \in [2k] \qquad t_i \in \mathbb{N},\ \ 1 \le t_i \le 2k$$
$$\forall i, j \in [2k], i \neq j \qquad t_i \neq t_j$$

$$\forall i \in [2k],\ i \text{ is an odd number} \qquad t_i \le t_{i+1}$$

$$\forall i \in [k] \qquad 0 \le x_i \le 1$$
$$\forall i \in [k] \qquad \text{A linear constraint}\ F(x_i,\ t_{2i},\ t_{2i-1},\ T)$$
Comment: If it helps, $$F(x_i,\ t_{2i},\ t_{2i-1},\ T)$$ is $$(1-x_i)(T-t_{2i-1}+1\ +\ T-t_{2i}+1)\ +\ (x_i)(T-t_{2i-1}+1) \ge |C_i| - 1$$, Where $$|C_i|$$ is a constant I know.

• It is unclear exactly what you are trying to solve and how the problem is defined. For example, what is $T$? Basically, your problems is going to be one of the followings: a network flow problem, a linear program with only continuous variables, or an integer linear program. Each of them can be solved with a specialized solver – Gabriel Gouvine Jun 15 at 19:20
• Do you require that any/all of the $t_i,x_i,T$'s be integers? What is $F$? – D.W. Jun 15 at 19:56
• Your constraints are contradictory. Your comment says $|t_i-t_j| \ge 1$, but your inequalities have inequality go the other direction. – D.W. Jun 15 at 19:57
• As stated, your constraint is quadratic, not linear – Gabriel Gouvine Jun 15 at 22:44
• It's also not a linear program; it's an integer linear program (which also tends to be much harder than a linear program). – D.W. Jun 15 at 23:21