# Questions tagged [algorithms]

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

76 questions
Filter by
Sorted by
Tagged with
1 vote
99 views

### How to solve assignment problem with additional constraints?

The assignment problem is defined as: Let there be n agents and m tasks. Any agent can be assigned to perform any task, incurring some costs that may vary depending on the agent-task assignment. We ...
93 views

### Efficiently updating latest finish times via Critical-Path-Method

For a Resource-Constrained-Project-Scheduling problem, I need to calculate Critical-Path-Method (CPM) values for each of the activities. These values are: Earliest Start (ES) Earliest Finish (EF) ...
464 views

### Julia JuMP successive optimization

I am using Julia's JuMP package to solve a cutting-plane method. Namely, I solve a sub-problem, find the most-violated constraint in the master problem, add that to ...
1 vote
138 views

### How to solve assignment problem with type constraints?

There are $n$ jobs and $m$ machines. Assigning job $i$ to machine $j$ yields a profit of $c_{ij}$. Each job has a type $t_i$. Machine $j$ can take on up to $a_j$ jobs, but the number of job types must ...
71 views

### Is this weighted feedback concept a known, solved, problem?

Imagine a fairly standard Thumbs Up/Down feedback system. For each piece of content they consume, every user has the ability to give a binary positive/negative feedback that piece of content. They're ...
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 ...
97 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 ...
366 views

### Combining Multiple Cost Values in Shortest Path Problem

I am trying to solve a shortest path problem through Dijkstra's algorithm. However in my case, cost between nodes (nodes $i$ and $j$) are more than one- two nodes are compared based on two different ...
131 views

590 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 ...
87 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 ...
128 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 ...
218 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 ...
129 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 ...
166 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. ...
260 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 ...
45 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:...
1 vote
220 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 ...
251 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 ...
49 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 ...
150 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 ...
46 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 ...