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
7
votes
2answers
152 views

What strategies to use for Scheduling of Connected Sequences?

I'm given a problem in which I need to schedule multiple sequences. The goal is to minimize the makespan. I'm allowed to elongate all tasks, but I cannot reduce their width nor disconnect any of the ...
2
votes
1answer
116 views

How to compute the minimum number of vehicles required

I am trying to solve the following problem: I have a set of $N$ requests that must be processed by vehicles. I do not know the locations of these requests. Requests can be processed by a same vehicle, ...
1
vote
1answer
117 views

Christofides algorithm, transform from Eulerian tour to Hamiltonian cycle

How do I do the change from an Eulerian tour to a Hamiltonian cycle in the Christofides algorithm? In the original paper from Christofides (1976)1 I found that A Hamiltonian circuit $i$ of $G$ can be ...
3
votes
1answer
99 views

Does Dijkstra's algorithm find the optimal solution for a weighted and directed shortest paths problem?

I was wondering to know whether Dijkstra's algorithm can find the optimal solution for a weighted and directed shortest paths problem where: 1) for each arc $(i,j)$, $i>j$ and 2) it is not always ...
4
votes
1answer
109 views

Which constructive heuristics exist for the time-dependent TSP?

A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained. (Wikipedia) Which ...
5
votes
1answer
85 views

Find Extreme direction of equality constraints

I think this is a very basic question, but I failed to find an algorithm for this... When I have a set of inequality constraints, $Ax \leq b$ as my feasible region, I can set $b = 0$ and find $n-1$ ...
5
votes
1answer
128 views

Quickest shortest path algorithm

I want to do a shortest path algorithm. My direct and not acyclic graph contains only positive numbers. I have to do the scan for all pairs of nodes in complete depth in python. My graph is big (...
0
votes
1answer
56 views

Trouble implementing a line-search algorithm

I am trying to implement a simple line-search algorithm in Julia. I am new to Julia programming, so I am learning it on the go. I'd like to ask for some help, if possible, to correct an error while ...
1
vote
1answer
93 views

Method (Algorithm) and Objective used in Gurobi Model

How can I find out which method or algorithm was used to solve my model? When I use GRB.IntParam.Method- to output the method, I get ...
2
votes
1answer
71 views

Bounding box fusion with constraints

I have N bounding boxes that I want to fuse/merge given some constraints. Each bounding box has a label. Goal: The main goal is to minimize ...
4
votes
1answer
225 views

Algorithms for sparse linear systems

I've long wondered this, but what is the algorithm(s) implemented in modern linear equation solvers for sparse systems? The obvious answer I can think of is Gauss-Jordan with a bunch of tricks to make ...
4
votes
1answer
64 views

Greedy algorithms for assignment problems --- prediction doesn't match simulation

I'm considering the following basic assignment problem: a group of $n$ people is to be assigned, in one-to-one fashion, a set of $n$ jobs. Write $C_{ij}$ for the cost incurred when person $i$ gets ...
9
votes
2answers
420 views

How to maximize "contrast" between nodes on a graph?

I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
2
votes
3answers
169 views

Are there any standard "tests" that determine if a model will not optimize / no solution?

As the title says, what are the tests for optimality or non-optimality I can build into my procedure and code to alert me that the model is going to be infeasible so I need to revise my constraints? ...
8
votes
1answer
220 views

Specific algorithms to compute the LP-relaxation of the Set-Cover problem

One of the most commonly known combinatorial problems is the set cover problem, which states that given a collection of sets $S = \{s_1, \dots, s_m\}$ and a universe of elements $U = \bigcup_{i=1}^m ...
2
votes
2answers
190 views

implementation of heuristics using C++ to solve operations research problems

can anyone suggest some good books with the implementation of heuristics and matheuristics using C++ to solve operations research problems especially routing problems such as TSP and VRP. also, I need ...
6
votes
2answers
78 views

Optimizing MIP Parameters For Various Data Sets

I have a MIP that runs for several different data sets. For each data set the MIP runs multiple times, once for each time period in the data set, and each time period is independent. I've experimented ...
6
votes
3answers
251 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 ...
3
votes
1answer
102 views

A variant of maximum sum subarray problem?

This is related to the foillowing Q on Cross Validated https://stats.stackexchange.com/questions/483002/experimental-design-problem-with-goofy-constraints which I am trying to answer, but the ...
4
votes
1answer
184 views

Column Generation algorithm

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
5
votes
0answers
88 views

Column generation approach for CVRP

I want to use a column generation based heuristic to solve a capacitated Vehicle Routing Problem. I know the basics of the algorithm but I don't have much experience in coding. is there any code about ...
3
votes
1answer
255 views

social network analysis - relations between people with weights

I asked this question on datascience.stackexchange but they directed me here. I have a social network represented as a set of people $S$ and individual weights for each of person (weight is the cost ...
2
votes
0answers
40 views

Algorithms for finding step sizes which satisfy the Wolfe conditions?

I am a student studying optimization, and I am interested in algorithms which finds step sizes satisfying the Wolfe (or strong Wolfe) conditions. I do know of one book which provides such an algorithm:...
7
votes
1answer
159 views

Why is this version of the algorithm more efficient?

I am a student self-studying Optimization, and I am reading about the Conjugate Gradient Method in Numerical Optimization by Nocedal & Wright, and they present two different algorithms for it. ...
1
vote
2answers
188 views

How to correct this scheduling algorithm?

I have a scheduling problem to solve. It's a resource-constrained project scheduling problem with time-varying resource availabilities. The objective is minimizing tardiness. The full detailed model ...
2
votes
0answers
47 views

Decision-making algorithm for dynamic load balancing

I'm researching a subject of balancing the load between two black-box systems (with some twists). I thought that I could record latest response time log from each of those systems and process such a ...
5
votes
0answers
124 views

A good memoryless elevator strategy?

Could you OR whizkids please help me out with this one: https://stackoverflow.com/questions/61854621/a-good-memoryless-elevator-strategy Surely somebody has solved this before. How do you classify ...
4
votes
0answers
120 views

Does anyone have the criss cross algorithm programming code to solve linear programming problems?

I have a project that requires programming code for the simplex algorithm and criss-cross algorithm. The purpose of this project is to compare the two methods. I've tried to find it, but the ...
5
votes
0answers
39 views

Relative Weakness of Rolling Horizon Optimization

I am running a fairly complex and dynamic(multi-period) model, and as a result of the complexity, solvers are not able to solve the problem in a reasonable time frame. I have since discovered the ...
1
vote
0answers
74 views

Rolling Horizon in Pyomo

I am trying to figure out how one could write a rolling horizon algorithm in PYOMO to speed up the solution of a model that I am building. My understanding of the Rolling Horizon Algorithm is that you ...
6
votes
2answers
144 views

Find a point inside non-empty difference of ellipsoids

Given two ellipsoids \begin{align}\mathcal{E}_1 &= \{ X \mid X^\top A_1 X + 2B_1^\top X + C_1 \leq 0\}\\\mathcal{E}_2 &= \{ X \mid X^\top A_2 X + 2 B_2^\top X + C_2 \leq 0\}\end{align} are ...
3
votes
1answer
101 views

Linear programming explanation in Algorithms by Sanjoy Dasgupta

I am reading about simplex algorithms in a textbook titled Algorithms by Dasgupta-Papadimitriou-Vairani. On each iteration, simplex has two tasks: Check whether the current vertex is optimal (and if ...
10
votes
1answer
187 views

Lagrangian Relaxation bound greater than optimal solution

I am working on a Lagrangian relaxation for a minimization MIP. Everything seemed to be working fine before I started to run a batch of instances. Checking the log results for one of the instances ...
7
votes
2answers
465 views

The general meaning of "constraint relaxation" in the context of the Shortest Path Problem

I've read that in the context of the Shortest Path Problem, the use of the term "relaxation" ("relaxing edges") [...][the use of the term "relaxation"] is historical. The outcome of a relaxation ...
10
votes
5answers
1k views

How to implement a "generic" solver for scheduling problems?

I have been accepted for an internship for 6 months. The aim of this internship is to implement a "generic" solver for scheduling/production planning problems. This solver will bill a small prototype ...
7
votes
1answer
103 views

Design choices on how to implement several algorithms for the same problem

When one is interested in solving a problem but considering different objective functions the choice is easy, a class for problem, a class for solution and a class by algorithm then in the main ...
8
votes
1answer
95 views

Speed of convergence for minimizing Rosenbrock's function

I am minimizing $f(x_1,x_2) = 100(x_2-x_1^2)^2 + (1-x_1)^2$, where I try many algorithms to compare with each other. All of the algorithms find the optimal solution $(1,1)$ quickly, so I am not ...
6
votes
1answer
198 views

When does the Junction Tree Algorithm work better than Variable Elimination?

Compared with the Variable Elimination algorithm, when does the Junction Tree algorithm work better? For what kind of graph structures? Size of the problem? Sparsity of the network?
11
votes
0answers
118 views

Armijo Line Search Parameters

I am trying to compare many unconstrained optimization algorithms like gradient method, Newton method with line search, Polak-Ribiere algorithm, Broyden-Fletcher-Goldfarb-Shanno algorithm, so on so ...
7
votes
1answer
146 views

How to convert 3D bin packing problem to 2D bin packing approximation?

I'm trying to approximately solve a 3D container loading problem. Is it possible to use 2D bin packing algorithms? If so, how do we make the transformation? What are the conditions needed to make the ...
15
votes
1answer
226 views

Was there something specific that caused graph cuts to lose popularity in the last 5 years?

Almost every graph-cut paper I look at seems to have exactly the same pattern of monotonic growth in citations and then monotonic decline starting around 5 years ago: For privacy I've cut the all ...
7
votes
1answer
112 views

Maximize charging, minimize cost

The task pertains to choosing an algorithm based on the data, requirements and constraints. I have a number of electrical devices ($d_1,d_2,\dots,d_n$) with batteries. Throughout the day I will ...
10
votes
0answers
165 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
987 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
263 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
79 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
2k 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
410 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 ...