Discrete lizard
  • Member for 2 years, 7 months
  • Last seen this week
  • At location (3,4) in a spacious terrarium (somewhere in the Netherlands)
Dichotomic search for biobjective linear program, max flow problem for hospital patients
1 votes

The first thing that comes to mind, is, to try to model the process in something like (timed?) colored Petri nets. Then, perhaps do some process mining and network partitioning and shortest path tree ...

View answer
Linear functions in Lenstra's algorithm
2 votes

As a partial answer, Equation 16 is a condition that leads to convergence. The replacement follows from maximization by a method that seems similar to LP rounding. I have not ran the numbers, but a ...

View answer
Christofides algorithm, transform from Eulerian tour to Hamiltonian cycle
Accepted answer
4 votes

The weight sum of all edges in the Eulerian tour created in Christofides algorithm is already at most $3/2$ times the weight sum of a TSP tour. While there are multiple ways of shortcutting the ...

View answer
Does the problem of P vs NP come under the category of Operational Research?
6 votes

While other answers have focused on the question whether "P vs. NP" can be considered to be in OR, I will instead look at the parts about this topic that I think are most relevant to study in the ...

View answer
How to interpret the random solution pick by Lévy flight on cuckoo search
Accepted answer
3 votes

The paper in which Yang and Deb introduce Cuckoo Search presents their method as a way to maximise the value of an objective function $f: C\rightarrow \mathbb{R}$, where $C$ is some continuous space (...

View answer
Finding an optimal set without forbidden subsets
Accepted answer
9 votes

Your problem is equivalent to finding a maximum weighted independent set in a hypergraph, where each item is a vertex and every forbidden set is an hyperedge over the elements in the set. This is a ...

View answer
Are there any efficient algorithms to solve the longest path problem in networks with cycles?
8 votes

As other answers have already noted, this problem is NP-hard. That, however, is not the end of the story. The longest path problem has some positive algorithmic results in the context of parametrized ...

View answer
Modeling floor function exactly
Accepted answer
19 votes

It is not possible to model the floor function as a constraint without modeling strict inequality. To prove this, I will show how the floor function can be used to model strict inequalities. Thanks ...

View answer
How to minimize an absolute value in the objective of an LP?
9 votes

This is possible by introducing 2 new variables, $t_1,t_2$, and adding a few constraints: $\begin{align} \min t_1+t_2 \quad \text{s.t.} \quad t_1-t_2 &= c\cdot x\\ t_1&\geq 0 \\ t_2&\geq ...

View answer