Questions Tagged With algorithmshttp://www.or-exchange.com/tags/algorithms/?type=rssquestions tagged <span class="tag">algorithms</span>enSun, 16 Mar 2014 21:34:00 -0400Search Algorithmhttp://www.or-exchange.com/questions/9399/search-algorithm<p>I am working on a research problem, which requires a search algorithm over integer.
I have a code to calculate a cost with given \(x\). \(x\) can be only a positive integer.
I can calculate \(f(x)\), numerically if \(x\) is given. (calculus doesn't work) </p>
<p>Fortunately, \(f(x)\) is convex in \(x\). </p>
<p>But due to the fact that the bigger \(x\) requires the larger matrix to deal with, and consequently, it requires much longer computation time. </p>
<p>We don't have upper nor lower bound. </p>
<p>How can I find \(x\) that minimize the cost function \( f(x)\), effectively ?</p>
<p>I found golden section search and fibonacci search algorithms.
But, they assume that there are upper and lower limits so that the optimal point is located in-between.
And, they are not for integer points.
Since large \(x\) leads a long computation time, I don't want to set a huge number as my upper limit. </p>
<p>I developed my own search algorithm, but I am not satisfied with my algorithm.<br>
</p>ksphilSun, 16 Mar 2014 21:34:00 -0400http://www.or-exchange.com/questions/9399/search-algorithmalgorithmssearchingA clustering algorithm that accepts an arbitrary distance functionhttp://www.or-exchange.com/questions/9273/a-clustering-algorithm-that-accepts-an-arbitrary-distance-function<p>I have about 200 points in Cartesian plane (2D). I want to cluster these points to k clusters with respect to arbitrary distance <strong>function</strong> (not matrix) and get the so-called centroid or representatives of these clusters. I know kmeans does this with respect to some special distance functions such as Euclidean, Manhattan, Cosine, etc. But, kmeans cannot handle arbitrary distance function because for example in centroid-updating phase of kmeans with respect to Euclidean distance function, mean of the points in each cluster is the LSE and minimizes the sum of distances of the nodes in the cluster to its centroid (mean); however, mean of the points may not minimize the ditances when the distance function is something arbitrary. Could you please help me about it and tell me if you know about any clustering algorithms that can work for me?</p>BabakSat, 15 Feb 2014 14:32:36 -0500http://www.or-exchange.com/questions/9273/a-clustering-algorithm-that-accepts-an-arbitrary-distance-functionclusteringalgorithmsChoosing an appropriate meta heuristic methodhttp://www.or-exchange.com/questions/8092/choosing-an-appropriate-meta-heuristic-method<p>I am familiar with many meta heuristic algorithms (including Simulated Annealing, Tabu Search, Genetic, Ant Colony, PSO , Bee Colony) I always have a fundamental question about choosing appropriate algorithm based on problem domain and its characteristics. Which properties I should know about the problem and how can I decide which algorithm is the best choice? I really appreciate any recommendation.</p>esmaeilSat, 08 Jun 2013 22:52:25 -0400http://www.or-exchange.com/questions/8092/choosing-an-appropriate-meta-heuristic-methodevolutionary-algorithmscombinatorial-optimizationalgorithmsmetaheuristics[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-complexitycomplexityalgorithmsWhat is a hyper-heuristic?http://www.or-exchange.com/questions/6690/what-is-a-hyper-heuristic<p>When I ask people this question, I usually get an answer like this:</p>
<blockquote>
<p>A hyper-heuristic is a heuristic that doesn't select moves but instead it selects other heuristics.</p>
</blockquote>
<p><em>That's too abstract for me.</em> It leaves too much room for interpretation.</p>
<p><strong>Which (if any) of the following are worthy to be called a hyper-heuristic?</strong></p>
<ol>
<li>To solve exam scheduling in 5 minutes, I first employ Simulated Annealing for 3 minutes and then - on the result of that - employ Tabu Search for 2 minutes. (Personally I call this <em>phasing</em>.)</li>
<li>To solve exam scheduling, I use Tabu Search with these 4 move types: change 1 exam to another period, change 1 exam to another room, swap 2 exam's (period and room) and swap a set of all exams for 1 period with another such set. (Personally I call this <em>neighborhood composition</em>.)</li>
<li>Same as 2) but favor selecting the move type that statistically gives the best results</li>
<li>To solve exam scheduling, I employ Simulated Annealing, but also discard moves based on tabu acceptance. (Personally I call this <em>acceptor composition</em>.)</li>
<li>None of the above. Please give a clear example :)</li>
</ol>Geoffrey De SmetWed, 03 Oct 2012 05:43:15 -0400http://www.or-exchange.com/questions/6690/what-is-a-hyper-heuristicalgorithmsWhich construction heuristics work well?http://www.or-exchange.com/questions/6404/which-construction-heuristics-work-well<p>As I understand it, a construction heuristic is a heuristic that takes an uninitialized schedule, bin packing problem or TSP and assigns every variable to a value, often in a greedy way.</p>
<p>Currently, I know of the following construction heuristics (thanks to this forum):</p>
<p><strong>First Fit</strong> etc (First Fit, First Fit Decreasing, Best Fit, Best Fit Decreasing)</p>
<pre><code>for (each uninitialized variable X) {
bestValue
for (each value V) {
if (better) bestValue = V
}
assign X to bestValue
}
</code></pre>
<p><strong>Cheapest insertion</strong></p>
<pre><code>while (there are uninitialized variables) {
bestVariableAndValue
for (each uninitialized variable X) {
for (each value V) {
if (better) bestVariableAndValue = (X, V)
}
}
assign bestVariableAndValue
}
</code></pre>
<p><strong>What other construction heuristics are worth implementing?</strong> It's OK if they are problem specific.</p>Geoffrey De SmetMon, 10 Sep 2012 03:38:07 -0400http://www.or-exchange.com/questions/6404/which-construction-heuristics-work-wellalgorithmsWho standarizes algorithms? Who settles algorithm implementation disputes? Do we need a standarized algorithm inventory?http://www.or-exchange.com/questions/6357/who-standarizes-algorithms-who-settles-algorithm-implementation-disputes-do-we-need-a-standarized-algorithm-inventory<p><strong>Update</strong>: The original question "Who standarizes algorithm names?" has been changed to "Who standarizes algorithms?". I never meant to raise an issue as to who gets to decide an algorithm name. I mean to raise an issue as to who decides if a certain implementation can claim that implements a certain algorithm name. More generally: <strong>Do we need to standardize an algorithm inventory?</strong> </p>
<p>We continually use algorithm names like "Tabu Search", "Branch and Bound", "Constraint Programming", ... to identify algorithms from implementations. This is a good thing as it allows us to communicate efficiently. However, more often than not, I see friendly disputes about names, for example:</p>
<ul>
<li>Branch and Bound implies an upper bounding function (to a level close to integer programming)</li>
<li>Constraint programming on Local Search implies CBLS techniques (Constraint Based Local Search)</li>
<li>Tabu Search implies placing tabu on entities or values, not just on solutions</li>
<li>Nearest Neighbor means to iteratively connect the 2 closest cities that are not fully connected. It does not mean to iteratively connect the nearest unconnected city to the TSP tour.</li>
</ul>
<p>For the future of our practice, I believe <strong>we need to clearly define and standardize our algorithms</strong> by settling such disputes. Which organization/medium should do that?</p>
<p>Personally, I think Wikipedia is the fairest and most authoritative medium to do this, but it seems like Wikipedia is very out-of-date and therefore naturally few people in the OR community update and respect its verdict.</p>Geoffrey De SmetWed, 05 Sep 2012 03:28:52 -0400http://www.or-exchange.com/questions/6357/who-standarizes-algorithms-who-settles-algorithm-implementation-disputes-do-we-need-a-standarized-algorithm-inventoryalgorithmsWhat is the correct name of this algorithm? Is "Branch and Bound" the correct name?http://www.or-exchange.com/questions/6339/what-is-the-correct-name-of-this-algorithm-is-branch-and-bound-the-correct-name<p>The algorithm below solves a 4 queen puzzle: put 4 queens on a 4 by 4 board and make sure they can't attack each other.</p>
<p>It is an improvement over brute force. It starts with an empty chess board and explores the most promising branches first. Based on the first initialized solution it comes across, it can <em>prune</em> away all branches who's partial solution doesn't violate less constraints.</p>
<p><img alt="algorithm" src="http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/images/Chapter-Exact_methods/branchAndBoundNQueens04.png"></p>
<p>Someone once told me this algorithm is named <em>Branch and Bound</em>. Is that correct? If that's wrong, <strong>what is the real name of this algorithm?</strong></p>Geoffrey De SmetTue, 04 Sep 2012 10:05:38 -0400http://www.or-exchange.com/questions/6339/what-is-the-correct-name-of-this-algorithm-is-branch-and-bound-the-correct-namealgorithmsWhat would you like to have in a Stochastic Algorithms Optimization Toolbox?http://www.or-exchange.com/questions/5357/what-would-you-like-to-have-in-a-stochastic-algorithms-optimization-toolbox<p>In collaboration with a <a href="http://spinellis.gr/index.html.var">professor</a> of mine, we are starting to build a software toolbox providing implementations for stochastic optimization algorithms.</p>
<p>We would like to provide an open-source library/API in a way that would allow other programmers/researchers to experiment with different parameter tunings and also give them the ability to easily extend the available implementations with different techniques and other problems.</p>
<p>We focus mainly on Stochastic metaheuristic Algorithms such as: Simulated Annealing, Genetic Algorithms. Ant Colony Optimization and GRASP for tackling combinatorial optimization problems.</p>
<p>Our goal is to make this software as widely used as possible which means it has to be useful to its "users".</p>
<p>At this point it would be great to have some "user requirements" from the potential users - the OR community.</p>
<p>So, what would you like to have in a toolbox of this kind? What algorithms? What capabilities? What features would you make use of?</p>Florents TselaiWed, 09 May 2012 18:50:47 -0400http://www.or-exchange.com/questions/5357/what-would-you-like-to-have-in-a-stochastic-algorithms-optimization-toolboxalgorithmsoptimization-softwarestochastic-optimizationTrouble in understanding a simple example of No Free Lunch theoremhttp://www.or-exchange.com/questions/4814/trouble-in-understanding-a-simple-example-of-no-free-lunch-theorem<p>I have trouble in understanding a simple example following No Free Lunch theorem in James Spall's <a href="http://books.google.com/books?id=f66OIvvkKnAC&lpg=PP1&pg=PA19#v=onepage&q&f=false">Introduction to stochastic search and optimization</a>:</p>
<p><strong>My understanding</strong> is that a cost function is a mapping from a finite set ({ heta_i}) to a finite set ({L_j}). A search algorithm, when applied to a cost function, is to search for a ( heta_i) such that the value of the cost function at it is the least. </p>
<blockquote>
<p>If there are (N_ heta) possible values in ({ heta_i}) and (N_L) possible values in ({L_j}), then by direct enumeration there are ((N_{L})^{N_ heta}) possible mappings from ({ heta_i}) to ({L_j}).</p>
<p><strong>The NFL theorems indicate that</strong>: When averaging over all ((N_{L})^{N_ heta}) possible mappings from from ({ heta_i}) to ({L_j}), all algorithms work the same (i.e., none can work better than a blind random search).</p>
<p><strong>Example 1.7 — NFL implications in a small problem.</strong> Suppose that (Theta = { heta_i, heta_2, heta_3}) and that there are two possible outcomes for the noise-free loss measurements, ({L_1, L_2}). Hence, ((N_L)^{N_ heta} = 2^3 = 8).</p>
<p>Table 1.1 summarizes the eight possible mappings.</p>
<p>Note that all rows in Table 1.1 have the same number of (L_1) and (L_2) values. Hence, the mean loss value across all eight possible problems is the same regardless of which ( heta_i) is chosen. Because the algorithm chooses the ( heta_i), all algorithms produce the same mean loss value when averaging across all possible problems. As a specific instance of the implication of the NFL theorems, suppose that (L_1 < L_2). Then, an algorithm that puts priority on picking ( heta) will work well on problems 1, 2, 3, and 7, but poorly on problems 4, 5, 6, and 8. The average performance is the same as an algorithm that puts priority on picking ( heta_2) or ( heta_3).</p>
</blockquote>
<p><img alt="Table 1.1" src="http://i.stack.imgur.com/mXvdW.png"></p>
<p><strong>My questions are:</strong></p>
<ol>
<li>
<p>Does the example assume that an algorithm will always output the same element in (Theta), regardless of which of the eight loss function it is applied to? (This is the only way that I can make sense out of the example. Otherwise, how shall I understand it?)</p>
<p>If yes, isn't it contrary to what an algorithm is in reality? For example, for minimizing different cost functions, the gradient descent algorithm outputs different solutions instead of a fixed solution.</p>
<p>If no, I can construct an algorithm that outputs ( heta_1) for cost functions 1, 2, 3, 7 and 8, ( heta_2) for cost functions 4 and 5, and ( heta_3) for cost function 6. This algorithm outputs the best solution for each cost function, so when considering its average performance over all cost functions, it is obviously better than many other algorithms. This violates NFL theorem. What is going wrong?</p>
</li>
<li>
<p>What exactly is a search algorithm? Is it a mapping from some set to another set?</p>
</li>
</ol>
<p>Thanks and regards!</p>TimoSat, 11 Feb 2012 17:44:39 -0500http://www.or-exchange.com/questions/4814/trouble-in-understanding-a-simple-example-of-no-free-lunch-theoremoptimizationalgorithmstheorydividing into roughly equal sized groups, with a sorted listhttp://www.or-exchange.com/questions/4398/dividing-into-roughly-equal-sized-groups-with-a-sorted-list<p>I have a problem, and it seems like it should be something that someone has studied before. I have a sorted list of N elements, and I want to divide them into K groups, by choosing K-1 split points between them. There may be elements with the same value, and we want to have items with same value in the same group. Find K groups as close in size to round(N/K) as possible.<br>
</p>
<p>For example, divide these 32 elements in to 4 groups of size 8:</p>
<pre><code>1 1 1 1 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 7 8 9 10 10
</code></pre>
<p>One solution would be these 3 break points:</p>
<pre><code>1 1 1 1 2 2 | 3 3 3 3 3 3 3 3 | 4 4 4 4 5 5 5 5 5 | 6 6 6 6 7 8 9 10 10
1 1 1 1 2 2 = 6 elements, error = abs(8-6)=2
3 3 3 3 3 3 3 3 = 8 elements, error = abs(8-8)=0
4 4 4 4 5 5 5 5 5 = 9 elements, error = abs(8-9)=1
6 6 6 6 7 8 9 10 10 = 9 elements, error = abs(8-9)=1
</code></pre>
<p>total error = 4</p>
<p>Does this look familiar to anyone? I'd like an approximation algorithm if possible. </p>
<p>Thanks,
Craig Schmidt</p>CraigFri, 06 Jan 2012 15:40:00 -0500http://www.or-exchange.com/questions/4398/dividing-into-roughly-equal-sized-groups-with-a-sorted-listclusteringcombinatorial-optimizationalgorithmsA confusing step in Stochastic IP Algorithms Article from Handbooks in OR&MShttp://www.or-exchange.com/questions/3798/a-confusing-step-in-stochastic-ip-algorithms-article-from-handbooks-in-orms<p>I'm reading through "Algorithms for Stochastic Mixed-Integer Programming Models", Elsevier Handbooks in OR&MS Volume 12 (Discrete Optimization), Chapter 9 and I'm stuck. For those without access to the Handbooks, I found a preprint version at: <a href="http://server1.tepper.cmu.edu/Seminars/docs/Sen_paper1-2.pdf">http://server1.tepper.cmu.edu/Seminars/docs/Sen_paper1-2.pdf</a>.</p>
<p>On page 531, Sen describes an algorithm from Laporte and Loveaux's 1993 paper "The integer L-shaped method for stochastic integer programs with complete recourse". In step 2b, he says:</p>
<p>Define $$eta_k(x) = max left{ eta_{k-1}(x), alpha + eta x
ight}$$</p>
<p>In the first iteration, ( eta_{k-1}(x)) is the constant lower bound on the expected recourse, and ( alpha + eta x ), the right-hand side of equation 3.4b on page 530, is a function of the binary first-stage variable ( x ). given that the first term of ( max ) is a constant, and the second term is a function of ( x ), I'm not clear what the ( max ) function means. In the example instance on the next page, the ( eta x ) term in( alpha + eta x ) cancels out, but this isn't always the case.</p>
<p>What does step 2b mean? </p>Luis de la TorreThu, 13 Oct 2011 17:20:20 -0400http://www.or-exchange.com/questions/3798/a-confusing-step-in-stochastic-ip-algorithms-article-from-handbooks-in-ormsinteger-programmingoptimizationstochastic-optimizationalgorithmsOR Algorithms: From design to implementationhttp://www.or-exchange.com/questions/3457/or-algorithms-from-design-to-implementation<p>The past couple of months i have been studying the basic algorithms for OR (GLS, ILS, TS, SS etc.)</p>
<p>"Studying" means: </p>
<ol>
<li>
<p>Taking an algorithm, studying the first paper that proposed it.</p>
</li>
<li>
<p>Reading the corresponding chapter from "Handbook of Metaheuristics- 2010" (btw: amazning work. Congratulations to all of the Authors.)</p>
</li>
<li>
<p>Studying papers with illustrative applications for each algorithm.</p>
</li>
</ol>
<p>This procedure works well up to point. This point is where theory stops and practice begins. </p>
<p>So i'm currently trying to code the algorithms i learn.</p>
<p>As a "guiding" book i use <a href="http://www.cleveralgorithms.com/nature-inspired/index.html">Clever Algorithms</a> since it has code examples. But to be more effective i code the examples coded in Ruby, in Java. I've also checked <a href="http://www.amazon.com/Metaheuristics-Implementation-Parallel-Distributed-Computing/dp/0470278587">this</a> but i didn't like it much.</p>
<p>I think most of the OR researchers in this forum have taken this step and my question is quite simple: How did you do it? I would like some advice on the way i should work to effectively go from design to implementation. Is there a good book i could use?</p>
<p>I already have a good understanding of OOP (Java and Ruby).</p>
<p>Finally, do i have to learn an other programming language (such as C++ even if i disagrre with the claim that is faster than java). Also, what about Haskell? Is it worth spending time on learning procedural programming as another perspective? </p>Florents TselaiFri, 12 Aug 2011 04:23:09 -0400http://www.or-exchange.com/questions/3457/or-algorithms-from-design-to-implementationimplementationprogrammingalgorithmsmetaheuristicsBasic/Nonbasic variables of a Nonlinear System of Equationshttp://www.or-exchange.com/questions/2908/basicnonbasic-variables-of-a-nonlinear-system-of-equations<p>I don't know if this a properly posed question (please ask for clarification if it is not), but it arose from a problem I often encounter, and I'm curious to know if anyone has given it any thought.</p>
<p>Here goes: </p>
<blockquote>
<p>Is there a known general
algorithm/code for partitioning an
underdefined nonlinear system of
equations into basic (dependent) and
non-basic (independent) variables? Or
alternatively, is there a way to
automatically determine all sets of
variables that are not independent?</p>
</blockquote>
<p>What I mean is this. Suppose we have a (non-inequality constrained) system as follows</p>
<p>$$ x^2 + exp(yq) + (q+2)^5z^3 = 3 $$</p>
<p>$$ 2x + 3y^2 = 6 $$</p>
<p>This system has 4 unknowns (x,y,z,q) and 2 equations. In order to solve it, we need to specify the values of 2 of the variables. It is obvious that we cannot specify x and y independently, as they are related to each other via the second equation. However, we can specify (x,q), (x,z), (y,q) or (y,z). Is there some sort of algorithm to figure out these sets? (I have a feeling there must be some graph theory algorithm out there that deals with this).</p>GileadTue, 17 May 2011 22:54:53 -0400http://www.or-exchange.com/questions/2908/basicnonbasic-variables-of-a-nonlinear-system-of-equationsalgorithmsExplaining algorithms using LEGO brickshttp://www.or-exchange.com/questions/996/explaining-algorithms-using-lego-bricks<p>Next week, I will introduce some algorithmic concepts to non-OR people with a short presentation. I believe that adding some humor to the presentation will be necessary to attract the attention.</p>
<p>I will do the following to explain the difference between solving shortest path problem with an LP solver and solving with Disjkstra's algorithm.</p>
<p>Imagine that LP solver is a 1x1 Lego brick and Dijkstra's algorithm is 6x1 brick. </p>
<ul>
<li><p>An LP Solver is like a swiss knife, you can solve different problems.
In Legoland, it means that you can build anything you want using 1x1 bricks.</p></li>
<li><p>A specialized combinatorial algorithm, for example Dijkstra's algorithm for shortest path problem, is generally more efficient than using an LP solver. In Legoland, suppose we want to build a 6x6. And assume that putting a single brick takes one second. Then using 1x1 bricks it will take 36 second to build it while using 6x1 brick it will just take 6 second. However you can not use 6x1 bricks for other problems for example building a 4x4. </p></li>
</ul>
<p>Can we do more similar observations like this?</p>ArmanWed, 08 Dec 2010 18:36:41 -0500http://www.or-exchange.com/questions/996/explaining-algorithms-using-lego-bricksalgorithmsfunWhy is it hard to implement the Simplex Algorithm?http://www.or-exchange.com/questions/961/why-is-it-hard-to-implement-the-simplex-algorithm<p>I took many OR courses and I think I have enough knowledge on the theory of the Simplex Algorithm. I mean, I know and I understand what is going on in each step of the algorithm.</p>
<p>On the other hand, everyone suggests to use an existing implementation and to do not begin to implement your own Simplex Algorithm from scratch. I am sure that there are many people like me wondering that which parts of the algorithm makes the implementation hard.</p>
<p>Obviously there are many issues (speeding-up sparse inputs, possible cycling from degeneracy situations etc.) but I think some specific answers will clarify the reasons of such suggestions.</p>ArmanSat, 27 Nov 2010 10:12:43 -0500http://www.or-exchange.com/questions/961/why-is-it-hard-to-implement-the-simplex-algorithmsimplexalgorithmsimplementationHow can I convince my boss that metaheuristics could fail?http://www.or-exchange.com/questions/904/how-can-i-convince-my-boss-that-metaheuristics-could-fail<p>In the company that I am working right now, we deal with OR problems in several industries. My boss, having a PhD in EE, thinks that meta-heuristic methods are general solvers, so we don't need any specific method.
The reason of his belief, I think, that for any problem there is at least one published paper in literature which solves that problem by using a meta-heuristic method. </p>
<p>I want to convince him that in some cases metaheuristics methods can fail.
Do you have any experience or any specific example for this situation?</p>
<p>Thanks. </p>ArmanWed, 10 Nov 2010 19:11:38 -0500http://www.or-exchange.com/questions/904/how-can-i-convince-my-boss-that-metaheuristics-could-failalgorithmsWhat are the top algorithms for Operations Research?http://www.or-exchange.com/questions/803/what-are-the-top-algorithms-for-operations-research<p>This is a simple question to be asked to the Operations Research commumity. I would like to see responses for, in your opinion, the top algorithms that are used in Operations Research. </p>
<p>Please allow only ONE algorithm per answer so that no repeats an included and no lists in answers. Let OR-Exchange users vote up the favorite ones that are already answered.</p>
<p>I'm interested to see what the OR community answers. Also this list could be useful for folks outside of the OR community to understand OR methodologies and best practices.</p>larrydag 1Thu, 14 Oct 2010 18:03:59 -0400http://www.or-exchange.com/questions/803/what-are-the-top-algorithms-for-operations-researchalgorithmsoptimizationSimplest decent revenue management algorithmhttp://www.or-exchange.com/questions/774/simplest-decent-revenue-management-algorithm<p>What is the simplest, but still decent, dynamic pricing algorithm you can think of, which can be used with minimal data sets and just a few "hotel rooms"? What algorithm would you use for demand projection with minimal data?</p>
<p>I'm thinking of one that can use a price ladder and then run an LP and just pick a price inside the ladder, depending on demand projections, but I am sure there's better and simpler out there. Documentation on yield management doesn't seem to be as good as I had hoped.</p>
<p>Thanks</p>JorchiWed, 06 Oct 2010 13:59:01 -0400http://www.or-exchange.com/questions/774/simplest-decent-revenue-management-algorithmseasonal-demandalgorithmsoptimizationComplexity 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-wikiChecking whether a set family forms a matroid.http://www.or-exchange.com/questions/420/checking-whether-a-set-family-forms-a-matroid<p>Given a set family, what is the best way (empirically) to check whether the set family is equivalent to set of independent sets of some matroid. The input can be either the set family explicitly or bunch of cardinality constraints that must be satisfied. For example, given a universe E, subsets A_1,..,A_k of E and positive integers b_1,...,b_k, a set F is in the family iff |Fcap A_i|leq b_i for each `1leq ileq k. Check whether the family is a matroid. </p>Mohit SinghFri, 04 Jun 2010 20:43:08 -0400http://www.or-exchange.com/questions/420/checking-whether-a-set-family-forms-a-matroidcombinatorial-optimizationindependent-setalgorithmsmatroidReferences for Submodular/supermodular optimizationhttp://www.or-exchange.com/questions/155/references-for-submodularsupermodular-optimization<p>I am wondering if you know good references to learn about submodularity. I want to know the basics and perhaps some applications. </p>
<p>Other references about developing algorithms for optimization of submodular functions would also help. </p>MarkWed, 03 Feb 2010 06:30:27 -0500http://www.or-exchange.com/questions/155/references-for-submodularsupermodular-optimizationsubmodularsupermodularalgorithmsoptimizationRobust Group-Ranking Algorithmshttp://www.or-exchange.com/questions/115/robust-group-ranking-algorithms<p>I am looking for a group-ranking algorithm (similar to Google's PageRank algorithm) that can help me solve the following problem:</p>
<p>In a large sparse graph every node can rate other nodes, an arc from node i to node j shows that i has rated j; and the arc-weight,r, which is a number in [0,1] shows how high the rating is. The graph is large (number of vertices>5000) and sparse (average number of adjacent arcs to each node is <5) many nodes do not have any adjacent arc coming in or going out and many only have incoming arcs, some only have outgoing arcs. Few have both incoming and outgoing arcs. </p>
<p>The question is how can we assign a ranking to each node such that the ranking is robust (a small group of nodes cannot push up their own ranking by down voting others) </p>
<p>I appreciate if you could please point out one or two valuable papers related to this question.</p>
<p><strong>Note:</strong> If sparsity makes it difficult (or impossible) you can assume that the graph is dense. </p>
<p><strong>Update</strong> It seems my problem definition was confusing. Here are some more explanations:
Let's assume we have a web graph (although my problem is not related to the web at all). each page links to other pages. some pages are orphans (no incoming arc). But I want to rank the pages. Google does the same thing with their <a href="http://en.wikipedia.org/wiki/PageRank" rel="nofollow">PageRank</a> algorithm. Let's assume that the resulting Markov chain is irreducible and positive recurrent (it makes the problem much easier and better defined). The problem here is that each state rates only a subset of the state space. </p>
<p>The following are a number of related articles that I believe are very close:</p>
<ol>
<li><a href="http://pluto.mscc.huji.ac.il/~levinas/nsf.pdf" rel="nofollow">Methodologies and Algorithms for Group-Rankings Decision</a></li>
<li><a href="http://portal.acm.org/citation.cfm?id=1451580" rel="nofollow">Country credit-risk rating aggregation via the separation-deviation model</a></li>
<li><a href="http://en.wikipedia.org/wiki/HITS%5Falgorithm" rel="nofollow">HITS algorithm</a> via <a href="http://twitter.com/hakankj" rel="nofollow">@hakankj</a></li>
</ol>
<p>I am looking for a public domain algorithm similar to HITS</p>
<p><img src="http://www.logicrepublic.com/images/google_pagerank.gif" width="250"></p>MarkThu, 24 Dec 2009 09:39:57 -0500http://www.or-exchange.com/questions/115/robust-group-ranking-algorithmsgroup-rankingalgorithmsgraphsnetworks