Skip to main content

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
1 vote
2 answers
141 views

My Professor couldn't complete the model for this optimization problem. how do i model this problem?

(Edit: there was a slight translation error, to be clear, we tried this since the start with Binary variables (IP), even then we couldn't crack it) I'm an undergraduate in Industrial Engineering and ...
Eduardo Gehrs's user avatar
2 votes
1 answer
863 views

Is 0-1 knapsack problem still NP-Hard (1) with an equality constraint and (2) when all the weights in the constraint are equal to one?

Is 0-1 knapsack problem still NP-Hard with an equality constraint? $$\begin{aligned} & \text { maximize } \sum_{i=1}^n v_i x_i \\ & \text { subject to } \sum_{i=1}^n w_i x_i = W \text { and } ...
Anson's user avatar
  • 23
1 vote
0 answers
40 views

Complexity of cardinality constrained maximum weight independent set problem

Given a graph with a set of nodes and edges, the goal of the maximum independent set problem is to find the maximum number of vertices where no two vertices are adjacent. This is well-known NP-hard ...
Mostafa's user avatar
  • 2,104
1 vote
1 answer
225 views

interior point computational complexity for SDP

I am trying to get the complexity of the SDP problem for my specific problem, but I’m facing some problems. I found in the literature that the complexity of the SDP problem for an interior point per ...
R. Sh's user avatar
  • 11
5 votes
1 answer
1k 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
1 vote
0 answers
92 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 ...
kachi's user avatar
  • 11
1 vote
1 answer
114 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,\...
Fabius Wiesner's user avatar
7 votes
1 answer
311 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
1 vote
1 answer
141 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 ...
prakash gawas's user avatar
2 votes
1 answer
166 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 ...
prakash gawas'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
1 vote
1 answer
130 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 ...
Tim's user avatar
  • 359
7 votes
2 answers
383 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
  • 544
5 votes
0 answers
113 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
6 votes
2 answers
171 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
  • 676
4 votes
2 answers
321 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
2 votes
1 answer
120 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 ...
stats_noob's user avatar
  • 1,841
7 votes
2 answers
574 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
9 votes
1 answer
189 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
  • 543
2 votes
1 answer
158 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 ...
Powereleven 's user avatar
0 votes
1 answer
98 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 ...
MAJID majid's user avatar
7 votes
1 answer
788 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
5 votes
2 answers
363 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
0 votes
1 answer
118 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 ...
O. Sd's user avatar
  • 65
3 votes
0 answers
111 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\\ ...
Samuel Bismuth's user avatar
3 votes
0 answers
125 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 ...
A.Omidi's user avatar
  • 8,960
4 votes
1 answer
365 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
6 votes
1 answer
388 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
-1 votes
1 answer
234 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?
Optimization team's user avatar
6 votes
0 answers
94 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
7 votes
1 answer
349 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,652
8 votes
2 answers
213 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
  • 203
7 votes
2 answers
623 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
1 vote
1 answer
3k 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.
Shayan zargari's user avatar
4 votes
1 answer
108 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
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 ...
ephemeral's user avatar
  • 917
5 votes
1 answer
255 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
3 answers
753 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
2 votes
1 answer
92 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 ...
fathese's user avatar
  • 423
4 votes
1 answer
273 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
6 votes
3 answers
2k 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
4 votes
1 answer
189 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 ...
batwing's user avatar
  • 1,583
6 votes
1 answer
104 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,583
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,583
5 votes
2 answers
318 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
1 answer
388 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
0 answers
116 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
1 answer
89 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
7 votes
1 answer
128 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