Questions tagged [computational-complexity]
For questions about the theoretical runtime needed for solving computational problems, often measured in the size of the input. This includes questions about whether polynomial time algorithms exist, NP-hardness, among others.
68
questions
2
votes
0
answers
121
views
Is OCN=DOCN decidable?
One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that
cannot decrease below zero and cannot be explicitly tested for zero.
An OCN $A$ over alphabet $\sum$ accepts a ...
- 21
5
votes
1
answer
554
views
How many variables and constraints can modern mixed integer programming solvers handle?
I originally asked a question here and they suggested that I crosspost it to the OR stack exchange, so that is what I am doing (hopefully correctly?). Here is the question I asked there:
"I know ...
- 153
1
vote
0
answers
65
views
Polynomial time separation and optimization for an LP with exponential columns and rows?
We know the fundamental theorem on the equivalence of separation and optimization: an optimization problem can be solved in a polynomial time if and only if there is a polynomial time separation ...
- 11
1
vote
1
answer
105
views
ILP program to find a centrosymmetric Hadamard matrix
A question in mathoverflow asks if there exists a centrosymmetric Hadamard matrix of order 36.
An $n \times n$ matrix $A = (a_{i,j})$ is centrosymmetric if:
$$a_{i,j} = a_{n-i+1, n-j+1}, \space i=1,\...
- 393
7
votes
1
answer
278
views
BIP for Sudoku naturally integral?
I was reading through the following notes regarding solving a 9x9 Sudoku via a binary integer program
https://vanderbei.princeton.edu/tex/talks/INFORMS_19/Sudoku.pdf
The formulation is straightforward ...
- 137
1
vote
1
answer
72
views
complexity Partitioning with negative numbers
I want to partition a set of numbers in two sets such that their sum is equal. Here in the original master set we can have positive as well as negative numbers. Can anyone tell me about the complexity ...
- 173
2
votes
1
answer
128
views
Np-hard sequencing or packing problems with total ordering between elements
I would like to know if anyone is aware of any Np-hard problems in scheduling or packing where there is total ordering between tasks or items to be packed together. The objective can be anything.
For ...
- 173
5
votes
0
answers
123
views
Scale of largest CPLEX/Gurobi execution
I am trying to understand the CO2 emission of large scale optimization using CPLEX or Gurobi. Is there a published literature which addresses the compute usage of large scale executions?
- 251
1
vote
1
answer
103
views
Verifying certificates versus solving problems
When we learn about P versus NP, we are taught that a certificate for a problem in NP can be verified (or invalidated) in polynomial time. But then the proof that $P \subseteq NP$ ignores the ...
- 359
6
votes
2
answers
266
views
Are "polynomial-time" algorithms for convex minimization actually pseudopolynomial time and/or FPTASes?
Motivating example
This question concerns continuous convex minimization. However, the motivating example is the classic binary knapsack problem
$$\text{maximize}\quad v^T x \qquad \text{subject to}\...
- 524
5
votes
0
answers
110
views
How many clues make Sudoku polynomial
Consider a $n^2 \times n^2$ grid sudoku.
Define a clue to be composed of a coordinate $x$ and $y$ of the grid and a value $z$.
The goal is given $n$ and a set of clues, to find one solution to the ...
- 173
3
votes
0
answers
43
views
Complexity of the ellipsoid method in general convex problems
The ellipsoid method is often mentioned in relation to the complexity of solving linear programs.
Is the method however polynomial in the general non-linear convex cases? Preferably I would like a ...
- 557
4
votes
2
answers
278
views
Reformulate CPLEX optimization model of Warehouse Product Allocation
I am trying to optimize the allocation of of products inside a fictive warehouse, having a predefined number of aisles (3 in the example code below) where products ...
2
votes
1
answer
112
views
Traveling Salesman Reference
Can anyone recommend a reference which shows the amount of time required for the Traveling Salesman Problem (TSP) to be solved using brute force as the number of cities increase?
I have informally ...
- 1,821
7
votes
2
answers
520
views
Optimization Solution Framework
I am working through Pascal Van Hentenryck's excellent discrete optimization course on Coursera.
While the course certainly touches on it in some ways, I am looking for more of a framework in terms of ...
- 117
9
votes
1
answer
184
views
A clustering problem with 0 or 1 distances for minimizing the summation of distances
I have a clustering problem with $\{0,1\}$ distances between a set of nodes, which can be stated as follows:
Given: Finite set $\mathbb{X}$, a distance $d(x, y) \in \{0,1\}$ for each pair $(x, y) \in \...
- 489
2
votes
1
answer
149
views
Is this integer optimization problem still NP?
I have the following integer optimization problem
\begin{align}\min&\quad\sum_ix_i\\
\text{s.t.}&\quad Ax \geq b\\
&\quad x \geq 0,\\
&\quad x \in \mathbb{Z}^n\end{align} where
$b$ is ...
- 129
0
votes
1
answer
89
views
How can we prove the solvability time of a linear program?
Given a linear program, by experimentation, I can see that the solver can solve large instances in a few seconds. How can I prove that my LP is in polynomial time, or can we say that it is just by ...
- 335
7
votes
1
answer
646
views
RAM requirement for optimization problems
I understand that RAM required for optimization problem is problem specific and some problems require much more memory. I am thinking how much RAM I need for my system and need to decide between ...
- 333
5
votes
2
answers
353
views
The importance of evaluating the number of constraints
If I introduce a problem, say as an ILP formulation, should I also discuss the number of introduced constraints? If yes, why?
- 561
0
votes
1
answer
116
views
Spatial complexity of optimization algorithm
How can I calculate the space complexity of an optimization algorithm?
Otherwise, what would happen if the complexity exceeds the machine capacity, and can I use the hardware instead of RAM? In this ...
- 65
3
votes
0
answers
91
views
Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case
Consider the following mixed-integer linear programming (MILP):
\begin{equation*}
\begin{array}{ll@{}ll}
\text{maximize} & 1 & \\
\text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\
...
- 173
2
votes
0
answers
111
views
Mathematical model complexity Vs Time Complexity of the model
As far as I know, when we talk about the term of complexity, it referred to the time complexity of the model in which how long does it take to solve a specific mathematical program by a specific ...
- 8,187
4
votes
1
answer
348
views
Complexity of navigation with google maps
I was wondering what complexity a simple start-destination task in a routing software would have. Knowing the shortest path problem, it should be in P. Is there anything I am missing?
6
votes
1
answer
286
views
In which time complexity operates the Savings algorithm for the TSP?
In which time complexity operates the Savings algorithm from Clarke and Wright for the TSP? I mean the parallel version of Savings. I think it is in $\mathcal O(|V|\log|V|)$ with V as vertex/node ...
- 659
-1
votes
1
answer
212
views
How to calculate the complexity order of an optimization model?
In some optimization problem it is stated that the complexity is ${\cal O}(n)$ or ${\cal O}(n^2)$. How is this calculated?
- 1,235
6
votes
0
answers
90
views
Sample Average Approximation vs. Numerical Integration
In the sense of the calculation of the expected value of objective functions, we have two choices to evaluate the value; 1. Sample Average Approximation (SAA):
$$
\frac{1}{N}\sum_{i=1}^N f(x,\xi^i).
$$...
- 155
7
votes
1
answer
328
views
Effect of 'unused' variables on the result and runtime of optimization algorithms
I have a general question about the effect of 'unused' variables on the result and runtime of optimization algorithms. I try to explain my question by giving an example. Let's say I have 2 type of ...
- 1,620
8
votes
2
answers
188
views
Reference for algorithms and complexity
What kind of background in algorithms and complexity theory is needed to fully understand the computational aspects of an OR paper. To be specific, I am not always sure when a paper says 'XYZ problem ...
- 183
7
votes
2
answers
597
views
Can a generic ILP solver find graph matchings as fast as a specialized algorithm?
Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms.
It can also be formulated as an integer linear program.
In ...
1
vote
1
answer
2k
views
complexity order of the interior point method
I was wondering why the complexity order of the interior point method is O()^3 or O()^3.5?
Much appreciate your time and consideration.
4
votes
1
answer
88
views
Does anybody know the complexity of finding a maximum clique in circulant graphs?
I would be interested in knowing if finding a maximum clique in circulant graphs is NP-hard? Does anybody have any pointers or papers to suggest?
- 49
2
votes
0
answers
42
views
Hardness Reduction for assigning Users to Servers
Suppose there are $x$ servers, and $y$ users. The $y$ users are to be assigned to the $x$ servers similar to classic scheduling problems. The cost of using servers is given by $c(|x|)$ which is an ...
- 897
5
votes
1
answer
227
views
NP-hardness of a special case of multiple choice knapsack problem
Let us consider the following problem:
\begin{align}
\max &\quad\sum_{i=1}^n\sum_{j=1}^m v_{i,j}\cdot x_{i,j} \\
\text{s.t.}&\quad \sum_{i=1}^n x_{i,j} =1 &\forall j =1,\dots,m \\
&\...
- 123
5
votes
3
answers
737
views
How to determine if this problem is NP-HARD or NP-COMPLETE?
Suppose that I have a pool with N nodes and I have to move the nodes one by one to another pool. For each move, consider a value on the edge linking the two pools. The goal is to find a order of nodes ...
- 413
2
votes
1
answer
88
views
confusing results of two models with different complexity
i have two models that address the same problem.
the first one is :
the second one is:
for different instances for the same size (n=30) i found the following results ( the first column on the left ...
- 413
4
votes
1
answer
262
views
How to determine the size of a model?
I want to know about the number of variables and constraints of this formulation (exp: $o(n)$ variables and constraints or $o(n^2)$ ....).
Is the number of variables $\mathcal O(n^3)$ because we have ...
- 413
6
votes
3
answers
1k
views
How to find all descendant vertices of all vertices in a big DAG (Directed acyclic graph)?
A simple algorithm may be traverse all vertices, and perform DFS for every vertex.
However, the computational complexity is $O(n(n+m))$, where $n$ and $m$ are the number of vertices and edges in the ...
4
votes
1
answer
173
views
Max flow problem with piece-wise costs
This question is a variant of a question I posted earlier and also fixes some typos in the earlier post (Complexity \ Reference request for variant of max flow problem). Some of the changes are ...
- 1,458
6
votes
1
answer
101
views
Complexity \ Reference request for variant of max flow problem
In the standard max cost flow problem with arc capacities, the cost of using an arc is proportional to the flow through the arc. For example, if $f_{uv}$ is the flow through the arc $(u,v)$, then the ...
- 1,458
5
votes
0
answers
63
views
Complexity of solving a certain commodity flow problem
Does anyone know the complexity of obtaining the optimal solution to the integral multi-commodity network flow problem with unit demands, integral capacities, but the cost of using an arc varies ...
- 1,458
5
votes
2
answers
293
views
Polynomial algorithm for a special ILP problem
Given the following problem:
\begin{align}
& z=\min \sum_{ij} x_{ij}\\
\text{s.t.} & \quad \sum_i d_{ij} x_{ij} \ge s_j, \quad \forall j \tag1 \\
& \quad \sum_j x_{ij} \le 1, \quad \...
- 135
5
votes
3
answers
1k
views
Fast algorithm for Transportation Problem in Python?
The Transportation Problem can be solved with a simplex algorithm, but it's time-consuming.
I'm wondering if there exists a specific Python-implemented algorithm with low complexity.
- 135
5
votes
1
answer
375
views
Polynomially solvable cases of zero-one programming
I am dealing with a problem having two types of variables: binary variables, and continuous variables.
In some cases, the continuous variables are not used, and so the problem contains those binary ...
- 2,086
5
votes
0
answers
108
views
Complexity of determining whether a LP or MIP is infeasible
What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
- 51
5
votes
1
answer
86
views
If a problem is inapproximable for $(2-\epsilon)$, can we conclude there exists no PTAS for it?
If we prove that:
The existance of a $(2-\epsilon)$-approximation algorithm for Problem P1 implies $P = NP$,
can we conclude:
There exists no PTAS for Problem P1, and so P1 is APX-hard?
- 2,086
7
votes
1
answer
127
views
Can this algorithm be considered polynomial?
Let us assume that an optimization algorithm requires $\mathcal{O}(n^{\log1/\epsilon})$ flops to find a solution $\bar{X}$ such that
$$\| \bar{X} - X^{\star}\| \leq \epsilon$$ where $\epsilon < 1$...
- 497
12
votes
1
answer
152
views
Re-calculating shortest path in slightly altered graph
I was wondering if someone has come across this before and/or has a smart idea for the following:
I have a directed graph $G$ with costs $c$ associated with the arcs, and I know the shortest path $P^...
9
votes
1
answer
602
views
Complexity comparision between purely BLP and MILP problems?
Could someone please comment and answer on the complexity of purely binary linear programming (BLP) and mixed-integer linear programming (MILP)?
In MILP, we have both binary and continuous variables ...
- 2,211
5
votes
1
answer
457
views
Solving a variant of multiple knapsack problem/ generalized assignment problem
Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...
- 943