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.

Filter by
Sorted by
Tagged with
23 votes
1 answer
346 views

Polynomially solvable problems with exponential extension complexity

The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the ...
Rolf van Lieshout's user avatar
19 votes
2 answers
857 views

How do we decide/plan an SLA for an NP-hard optimization process running in production?

How do you decide or plan an SLA (Service Level Agreement) for an application that depends on an optimization process when the problems you deal with are NP-hard? That is, if you are developing an ...
Skander H.'s user avatar
  • 2,139
18 votes
3 answers
6k views

Can an integer optimization problem be convex?

I'm trying to wrap my head around an apparent paradox that I've come across while trying to learn more about optimization algorithms: On one hand several sources state that convex optimization is ...
Skander H.'s user avatar
  • 2,139
16 votes
6 answers
3k views

Does the problem of P vs NP come under the category of Operational Research?

I am enrolled in an Operational Research program. I am also interested in Algorithms, and I wish to know whether "P vs NP" is a common point in both of the fields, so that the effort put in ...
Vikranth Inti's user avatar
15 votes
2 answers
2k views

State-of-the-art algorithms for solving linear programs

Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
rasul's user avatar
  • 2,140
13 votes
3 answers
3k views

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

I have a directed social network and as a preprocessing step I need to calculate the longest path lengths for each node. Longest path problem is NP-hard as far as I know but I've seen dynamic ...
Evren Guney's user avatar
13 votes
1 answer
159 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^...
Martim Joyce-Moniz's user avatar
12 votes
2 answers
4k views

MILP: is it NP-complete or NP-hard?

The pieces of information I get online are sometimes confusing. Someone says MILP problems are NP-hard, and somewhere else I found the claim that MILP problems are NP-complete. Can someone please ...
KGM's user avatar
  • 2,211
12 votes
1 answer
595 views

Complexity of verifying optimality in (mixed) integer programming

I looked around for a while, but I couldn't find a precise answer to the following question. If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of ...
Tobia Marcucci's user avatar
12 votes
1 answer
439 views

When is the original BFGS algorithm still better than the Limited-Memory version?

I have been going through Andrew NG's original data science course on Coursera. I learned the BFGS algorithm at some point in my OR education, but not the Limited Memory version that Andrew NG focuses ...
Zohar Strinka's user avatar
12 votes
1 answer
162 views

Computational complexity to compute an IIS

How hard is it to compute an irreducible infeasible subset (IIS) for a linear program? What about an integer program (e.g., removing the integrality constraint on a single variable may be enough to ...
David M.'s user avatar
  • 2,077
11 votes
2 answers
296 views

Generalized Assignment Problem as the sub-problem

I was wondering what is the state-of-the-art for solving the Generalized Assignment Problem (GAP) and if there are special cases that are polynomially solvable? Moreover, is there any usage of this ...
Junior MIP's user avatar
11 votes
2 answers
206 views

Is deciding the presence of mixed-integer points in the relative interior of a polyhedron in NP?

Given $P = \{x\in\mathbb R^n: Ax \leq b\}$, I want to decide if $(\mathbb Z^\ell \times \mathbb R^{n-\ell}) \cap \operatorname{relint}(P)$ is non-empty. Is this problem in NP? One idea is to check ...
Sriram Sankaranarayanan's user avatar
11 votes
2 answers
293 views

Can SOCPs approximate better than LPs?

Are there any classes of NP-hard combinatorial optimization problems where Second order cone programs (SOCP) gives a better approximation than linear programs (LP)? I am looking for results in the ...
Sriram Sankaranarayanan's user avatar
9 votes
2 answers
4k views

Complexity of LP and MILP Problems?

My original problem is an MILP. I make it an LP by relaxing the integer variables. Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general? Is ...
KGM's user avatar
  • 2,211
9 votes
1 answer
185 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 \...
OR Junior's user avatar
  • 521
9 votes
1 answer
671 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 ...
KGM's user avatar
  • 2,211
9 votes
0 answers
176 views

Modelling resource dependency in the assignment problem

The assignment problem is well-studied and has a nice polynomial time algorithm. I'm interested in an extension of this problem where all edges are in a certain group and taking multiple edges from ...
Discrete lizard's user avatar
8 votes
1 answer
1k views

Why is the Ellipsoid Method of polynomial complexity?

We know that the ellipsoid method is proven to be of polynomial complexity. However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no ...
Nikos Kazazakis's user avatar
8 votes
2 answers
201 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 ...
superhulk's user avatar
  • 183
7 votes
2 answers
550 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 ...
dkent's user avatar
  • 217
7 votes
2 answers
616 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 ...
Erel Segal-Halevi's user avatar
7 votes
1 answer
707 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 ...
Jonn's user avatar
  • 333
7 votes
1 answer
343 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 ...
PeterBe's user avatar
  • 1,632
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$...
C Marius's user avatar
  • 507
7 votes
1 answer
300 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 ...
Ram's user avatar
  • 137
7 votes
2 answers
331 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}\...
Max's user avatar
  • 534
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 ...
LighTofHeaveN's user avatar
6 votes
1 answer
355 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 ...
maxmitz's user avatar
  • 659
6 votes
1 answer
103 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 ...
batwing's user avatar
  • 1,458
6 votes
0 answers
92 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). $$...
Keith's user avatar
  • 155
5 votes
1 answer
384 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 ...
Mostafa's user avatar
  • 2,104
5 votes
2 answers
307 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 \...
dgamboz's user avatar
  • 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.
dgamboz's user avatar
  • 135
5 votes
2 answers
359 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?
Daniele Cuomo's user avatar
5 votes
3 answers
747 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 ...
fathese's user avatar
  • 423
5 votes
1 answer
477 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 ...
Joffrey L.'s user avatar
5 votes
1 answer
242 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 \\ &\...
Pete S's user avatar
  • 123
5 votes
1 answer
88 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?
Mostafa's user avatar
  • 2,104
5 votes
1 answer
850 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 ...
graphtheory123's user avatar
5 votes
0 answers
124 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?
Omar Shehab's user avatar
5 votes
0 answers
112 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 ...
Samuel Bismuth's user avatar
5 votes
1 answer
140 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 ...
gmn's user avatar
  • 632
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 ...
batwing's user avatar
  • 1,458
5 votes
0 answers
110 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 ...
G Oliveira's user avatar
5 votes
0 answers
124 views

Maximum eigenvalue across subsamples

I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$. Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of ...
Lorenzo Trapani's user avatar
4 votes
2 answers
302 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 ...
GuglielmoSanchini's user avatar
4 votes
1 answer
362 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?
MathEnthusiast's user avatar
4 votes
1 answer
95 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?
Fabio Furini's user avatar
4 votes
1 answer
267 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 ...
fathese's user avatar
  • 423