Questions Tagged With complexityhttp://www.or-exchange.com/tags/complexity/?type=rssquestions tagged <span class="tag">complexity</span>enThu, 04 Dec 2014 19:15:51 -0500Scheduling problem with minimum up/down constraintshttp://www.or-exchange.com/questions/10796/scheduling-problem-with-minimum-updown-constraints<p>Hello everyone.</p>
<p>I have a scheduling model derived from a Unit Commitment Problem (UCP).</p>
<p>A horizon \(T\) divided in periods is defined. There are \(m=|M|\) identical plants which can work in parallel.</p>
<p>In each period each plant can be either on or off. There are minimum up/down constraints which force a plant to keep the new state after a switching operation for a number of consecutive periods. Different numbers of "waiting" periods \(\tau_{ON}\), \(\tau_{OFF}\) are defined for switching on and off operations.</p>
<p>When a plant is on it can produce up to a bound \(P_{\max}\). In each period a global demand \(d_t\ge 0\) is given. A constraint states that at each period there must be enough active plants to satisfy the global demand.</p>
<p><strong>EDIT</strong> Demand comes from the fractional solution of a subproblem inside a decomposition scheme for a bigger UCP model. As such the demand can vary in very irregular ways compared to a real demand for a UCP model For this reason it can only be assumed that the demand is going to assume a strictly positive value for some periods along the horizon.</p>
<p>At each period a different cost is borne for having a plant active. <strong>EDIT</strong> Costs are the same for all the plants.
The objective is to minimize the total scheduling cost.</p>
<p>The problem could be reformulated as fixed interval scheduling model with parallel identical machines by representing demand slices as different tasks to be assigned to the different plants.
The peculiarity of this model is that all the tasks have a processing time of exactly 1, i.e. start and end time coincide, while minimum up/down constraints force plants to be active or inactive for more than one period. </p>
<p>In absence of both minimum up and down constraints, i.e. if I could switch the plants at every period, the problem would be trivial.
With those constraints the problem seems to be significantly harder. I think its decision version could be NP-complete.</p>
<p>Currently we have a heuristic which solves lots of these models over a long horizon of about 8000 periods. The models are solved to optimality via MIP solvers, implemented with CPLEX/C++, which can fathom them in less than a minute each. However in practice the real time and memory needed to solve these problems is way higher and a more efficient solving method is needed.</p>
<p>I'd like to assess the complexity of this problem and, possibly, find an efficient heuristic.
I've been searching the literature for references about those constraints or similar scheduling problems but I could not find any.</p>
<p>Do you have any pointer?</p>
<p>TIA</p>Andrea TThu, 04 Dec 2014 19:15:51 -0500http://www.or-exchange.com/questions/10796/scheduling-problem-with-minimum-updown-constraintsschedulingcomplexityreductioncomplexity of feasibility checking for a convex optimization problemhttp://www.or-exchange.com/questions/9557/complexity-of-feasibility-checking-for-a-convex-optimization-problem<p>Hi, all,</p>
<p>I just want to check with you all whether I understand it correctly or not. If I have a convex optimization problem like</p>
<p>\(
\begin{align}
\min & ~f(x)\\
\text{s.t.} & ~h(x) \le 0
\end{align}
\)</p>
<p>and assume the complexity to solve this problem is \(O((MN)^{3.5})\) by interior-point method. Then if I implement the following feasibility checking problem in CVX (with the same constraints as above)</p>
<p>\(
\begin{align}
\min & ~0\\
\text{s.t.} & ~h(x) \le 0
\end{align}
\)</p>
<p>the complexity to solve the feasibility checking problem is the same as the first problem or not? (i.e., still \(O((MN)^{3.5})\) or not?)</p>
<p>And the feasibility checking problem is also solved by interior-point method?</p>
<p>Thanks a lot.</p>Armstrong_landedMon, 05 May 2014 01:25:46 -0400http://www.or-exchange.com/questions/9557/complexity-of-feasibility-checking-for-a-convex-optimization-problemcomplexityoptimizationComplexity of a mathematical modelhttp://www.or-exchange.com/questions/9531/complexity-of-a-mathematical-model<p>How can I find the complexity of a mathematical model with the big O notation? For example, I want to find the complexity of the knapsack problem model formulation not its related solution algorithm. The complexity is defined for which one? The mathematical model, the solution algorithm or both of them. </p>hkarimiWed, 30 Apr 2014 15:49:49 -0400http://www.or-exchange.com/questions/9531/complexity-of-a-mathematical-modelcomplexitymathematical-modeling[ANN] An interesting site on algorithmic complexityhttp://www.or-exchange.com/questions/7951/ann-an-interesting-site-on-algorithmic-complexity<p>The website <a href="http://bigocheatsheet.com/"></a><a href="http://bigocheatsheet.com/">http://bigocheatsheet.com/</a> has a big collection of lot of commonly used algorithms and their time complexity. Recently came across this site and thought it might an interesting resource for this community.
I am not related to this site.</p>Samik R.Tue, 07 May 2013 14:33:30 -0400http://www.or-exchange.com/questions/7951/ann-an-interesting-site-on-algorithmic-complexitycomplexityalgorithmsTime complexity of a non-linear modelhttp://www.or-exchange.com/questions/5192/time-complexity-of-a-non-linear-model<p>Hello
I have faced a non-linear problem in my modeling. My model is as follows:
max sum {x_i}
s.t.
x_i.y_i=z_i 1<i<n
....
some linear constrains</p>
<p>In this models, x_i, y_i, and z_i are continuous variables for {1<i<n}. As you can see we have a product term in constrains. My question is if this problem is P or NP? I strongly think it is NP. This is because the I found that the product term can be approximated by peicewise linear optimization techniques ("AIMMS Optimization Modeling" ebook, chapter 7, <a href="http://www.aimms.com/downloads/manuals/optimization-modeling">http://www.aimms.com/downloads/manuals/optimization-modeling</a> ). This method convert the constrain to a MILP form, which is NP-hard. But this proof is not precise. So, I would like to ask if anyone can help me on this topic.
Thanks<br>
</p>jamedadiSun, 01 Apr 2012 15:33:00 -0400http://www.or-exchange.com/questions/5192/time-complexity-of-a-non-linear-modelcomplexitynp-hardnon-lineartimeSpeed of max-flow algorithms when max known in advance?http://www.or-exchange.com/questions/4335/speed-of-max-flow-algorithms-when-max-known-in-advance<p>I have a generalized flow network. I want to maximize the flow to the sink, and the flow along each arc must be integral (all capacities and gains are integral). If I know, in advance, the value of the max flow to the sink (but not the routes through the network), does this in any way speed up any algorithms usually used to solve this problem? If so, what would this speed up be (in terms of Big-O notation)?</p>OR_MRTue, 03 Jan 2012 21:57:25 -0500http://www.or-exchange.com/questions/4335/speed-of-max-flow-algorithms-when-max-known-in-advancecomplexitynetworksIs there any simple optimization problem example which is not in class NP?http://www.or-exchange.com/questions/841/is-there-any-simple-optimization-problem-example-which-is-not-in-class-np<p>The first step of an NP-completeness proof for a problem B is that we show B is in class NP:
i) B can be solved in polynomial time with a nondeterministic turing machine
or equivalently
ii) There exists a polynomial time "verifier" for the problem that is for a given candidate solution we can decide "YES/NO" in polynomial time. </p>
<p>I couldn’t find any simple optimization problem example which is not in NP.
There are some weird examples (Halting Problem), but I am wondering whether there exist any optimization problem example?</p>ArmanSat, 23 Oct 2010 10:39:27 -0400http://www.or-exchange.com/questions/841/is-there-any-simple-optimization-problem-example-which-is-not-in-class-npcomplexityWhy can't we solve longest path problem by using shortest path algoritms?http://www.or-exchange.com/questions/823/why-cant-we-solve-longest-path-problem-by-using-shortest-path-algoritms<p>Consider a maximization problem of a function f(x) on a feasible set S.
We know that the following problem is equivalent to the problem above: min -f(x) on S.</p>
<p>Now, suppose that we want to solve a longest path problem instance on a network (possibly containing some cycles).
Since shortest path problem is solvable in polynomial time, one can do the following
multiply all arc weights by -1 to make it a shortest path problem instance and solve it by Bellman's algorithm to get a solution which is equivalent to solve longest path problem instance due to the statement in the first paragraph since we only multiplied all the coefficients of the objective function by -1.
However, the longest path problem is NP-hard, so I know that this should not work but why? </p>
<p>Maybe the answer is obvious but I could not figure this out.</p>
<p>Thank you.</p>ArmanMon, 18 Oct 2010 19:33:53 -0400http://www.or-exchange.com/questions/823/why-cant-we-solve-longest-path-problem-by-using-shortest-path-algoritmscomplexityoptimizationComplexity results for classical OR problemshttp://www.or-exchange.com/questions/754/complexity-results-for-classical-or-problems<p>I'm looking for [concise, yet comprehensive] online resources and/or (state of the art) survey papers presenting complexity results for classical OR problems such as</p>
<ul>
<li>Shortest Path and Spanning Tree Problems;</li>
<li>Network Flow, Assignment and Knapsack Problems;</li>
<li>Traveling Salesman and Vehicle Routing Problems;</li>
<li>...</li>
</ul>
<p>(and their respective variants).</p>
<p>By "complexity results", both problem-specific lower bounds (resp., complexity classes) as well as performance of seminal algorithms (optimal, approximative) should be addressed.</p>
<p>For instance, the <a href="http://www.lix.polytechnique.fr/~durr/query/">Scheduling Zoo</a> is a nice searchable bibliography on results w.r.t. scheduling problems (though, it does not offer detailed statements in terms of Big-\(O\)-assessments).</p>
<hr>
<p><strong><em>Collected web resources:</em></strong></p>
<ul>
<li><a href="http://qwiki.stanford.edu/index.php/Complexity_Garden">Complexity Garden</a> <em>(w.i.p.)</em></li>
<li><a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations">Computational complexity of mathematical operations</a></li>
<li>
<p><a href="http://bigocheatsheet.com/">Big-O Algorithm Complexity Cheat Sheet</a></p>
</li>
<li>
<p><a href="http://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms">Shortest Path Problems</a></p>
</li>
</ul>
<ul>
<li>Assignment Problems</li>
<ul>
<li>Quadratic Assignment Problem</li>
<ul>
<li><a href="http://www.seas.upenn.edu/qaplib/">QAPLIB - A Quadratic Assignment Problem Library</a></li>
</ul>
</ul>
</ul>
<ul>
<li>Network Flow Problems</li>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Maximum_flow_problem#Solutions">Maximum Flow Problem</a></li>
</ul>
</ul>
<ul>
<li>
<p><a href="http://www.tsp.gatech.edu/">Traveling Salesman Problems</a></p>
</li>
<li>
<p><a href="http://neo.lcc.uma.es/radi-aeb/WebVRP/">Vehicle Routing Problems</a></p>
</li>
</ul>
<ul>
<li>Scheduling Problems</li>
<ul>
<li><a href="http://www.informatik.uni-osnabrueck.de/knust/class/">Complexity results for scheduling problems</a></li>
<ul>
<li><a href="http://www.lix.polytechnique.fr/~durr/query/">The scheduling zoo — A searchable bibliography</a></li>
</ul>
</ul>
</ul>
<hr>
<p>PS: This is a "community question". Feel free to edit as needed. (That is, if you have at least 30 "karma points".)</p>fbahrWed, 29 Sep 2010 19:47:15 -0400http://www.or-exchange.com/questions/754/complexity-results-for-classical-or-problemscomplexityalgorithmscommunity-wikiNew Proof that P!=NPhttp://www.or-exchange.com/questions/623/new-proof-that-pnp<p>So, has anyone been following this new claim on a proof? I recall a thread on sci.op-research from a few days back. Obviously, it's natural to be skeptical after all the cranks who pop up at regular intervals, but the guy in question seems like a serious researcher. It's even been covered in today's New York Times: <a href="http://www.nytimes.com/2010/08/17/science/17proof.html?ref=technology" rel="nofollow">http://www.nytimes.com/2010/08/17/science/17proof.html?ref=technology</a>. Although that's not a claim to fame, perhaps!</p>
<p>Complexity is not one of my areas, but perhaps someone who works in the field can shed some light on whether this will go anywhere...</p>Jay RajgopalTue, 17 Aug 2010 20:01:53 -0400http://www.or-exchange.com/questions/623/new-proof-that-pnpcomplexityDoes cellular automaton have any kind of real life application?http://www.or-exchange.com/questions/332/does-cellular-automaton-have-any-kind-of-real-life-application<p>I watched Stephen Wolfram's <a href="http://www.youtube.com/watch?v=60P7717-XOQ" rel="nofollow">TED Talk</a> and although I enjoyed it, I have a hard time finding any relationship between his "New Kind of Science" and the reality. I understand that his cellular automaton may be used in random number generation (although reported to perform poorly) but I am wondering if there are other applications for it. </p>
<p>And as far as I can understand some of his rules are Turing Complete. Does it mean that by studying these we can better understand the complexity theory? </p>
<p>If you have read his book, do you recommend it?</p>
<p>Update:</p>
<ul>
<li><a href="http://www.cscs.umich.edu/~crshalizi/reviews/wolfram/" rel="nofollow">Here is</a> a review of Worlfram's work</li>
</ul>MarkFri, 30 Apr 2010 08:36:06 -0400http://www.or-exchange.com/questions/332/does-cellular-automaton-have-any-kind-of-real-life-applicationcomplexity