Questions tagged [algorithms]

For questions related to the design or implementation of algorithms (exact or heuristic) for solving optimization problems.

Filter by
Sorted by
Tagged with
10
votes
0answers
171 views

Solving large-scale stochastic mixed integer program

What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
16
votes
1answer
1k views

IPOPT with HSL vs MUMPS

What are the advantages (if any) of using IPOPT with HSL vs MUMPS? HSL has a reputation of being faster, but does it walk the walk? In particular, does HSL scale better for large-scale problems? We ...
10
votes
3answers
278 views

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities? If it is not, then what is? For $m$ inequalities in $d$ ...
6
votes
0answers
81 views

What are the top three applications (in terms of number of citations) of the "reverse search" algorithm of David Avis?

I can see that this algorithm is quite popular, and that one of the original papers now has 820 citations on Google Scholar. However, what are the most highly cited applications of it? If in Google ...
26
votes
6answers
2k views

Statistical tests for benchmark comparison

Suppose that you have two algorithms for solving an optimization model, and you want to benchmark their performance over a large set of instances (with only one performance metric, for example, the ...
12
votes
3answers
3k views

Performance of a branch and bound algorithm VS branch-cut-heuristics

I was trying to solve a moderate scheduling model using an open-source solver. I did two different ways. A) using pure branch and bound algorithm (disable all options). B) using the default setting ...
16
votes
6answers
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 ...
8
votes
1answer
423 views

Finding minimum time for vehicle to reach to its destination

Given a set of Vehicles with source and destination I need to find the minimum time of travel for all the vehicles, there are also some charging stations and its necessary for vehicles to charge 1 ...
10
votes
3answers
286 views

Does the "prize-collecting shortest path problem" exist?

The prize collecting shortest path problem (PCSPP) is a special case of the prize collecting Steiner tree problem (PCSTP) (PCSPP is the PCSTP with only two terminal vertices, namely the source and ...
10
votes
2answers
342 views

Many-to-many Breadth First Search

There is a directed social network with large number of nodes and arcs and there are many instances of the network (nodes are same but arcs change in each instance). You can think of it as a ...
18
votes
6answers
3k views

List of Implementations for common OR problems

For the TSP there famously is the concord solver (http://www.math.uwaterloo.ca/tsp/concorde.html) which is argubly the fastest exact solver for the TSP. There are many other problems that also show ...
11
votes
2answers
472 views

Finding an optimal set without forbidden subsets

Given $n$ items, I want to select a set items $S\subseteq\{1,2,\dots,n\}$ that maximize profit. The profit of item $i\in\{1,2,\dots,n\}$ is given by $p_i$ and may be assumed to be non-negative. ...
18
votes
2answers
277 views

Mathematically creating the 'perfect' permutation for reservations in a hostel

I am working at a hostel which uses a reservation system for each room and the beds in the room (e.g. $14$ beds in one room, bed numbers $1-14$.) When we get bookings for multiple people, we assign ...
11
votes
2answers
210 views

partitioning hub assignment models

When solving large-scale hub assignment models (1000+ candidate hubs and 1000+ demand nodes), it is possible that parts of a cost matrix are not connected to one another. A typical workflow would be: ...
1
vote
2answers
370 views

Is there any way to generate all the possible undirected graphs with unlabeled nodes?

I am looking for an efficient algorithm to generate all of the unique graphs for a given number of nodes. For small instances, the total number of graphs are as follows: n=2 G=2 n=3 G=4 n=4 G=11 ...
10
votes
1answer
150 views

Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location

In Jain et al. (2003)1, at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega\left(\...
11
votes
2answers
146 views

Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

I have been trying to implement a variant of LNS on a graph for TSP. One of the ways that I can define a neighborhood for TSP is to find $k$-shortest path between two nodes. But the choice of these ...

1
2