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
1
vote
1answer
55 views

Check if there exists a vector that satisfies a set of inequalities but violates another set of inequalities

Problem Given rectangular matrices $A$, $B$ and vectors $\vec{a}$, $\vec{b}$, how to check if there exists an $\vec{x}$ that satisfies the following conditions? $\vec{x} \succcurlyeq \vec{0}$ is true....
1
vote
0answers
35 views

Importance of Polynomial Time Approximation algorithm for special case

I am an MSc student, searching for an interesting topic in operations research for NP-hard problems. I need your opinion and recommendation about: "Searching a polynomial time approximation ...
0
votes
0answers
63 views

How to prove that given algorithm from shortest path always finds the optimal solution?

The greedy approach which is used here is explained below. For finding the stops where the user should make a stop, first declare a dynamic vector to store all the stops. Take a flag as a starting ...
3
votes
0answers
48 views

Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case

Consider the following mixed-integer linear programming (MILP): \begin{equation*} \begin{array}{ll@{}ll} \text{maximize} & 1 & \\ \text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\ ...
1
vote
0answers
36 views

What is the role of parameters in whale optimization algorithm?

I am trying to understand how the whale optimization algorithm works. When I see the mathematical model of this algorithm there are some parameters I want to understand what they mean and what their ...
8
votes
2answers
323 views

Mixed-Integer Linear Programming With Free Variables

In the classic Mixed-Integer Linear Programming (MILP), the variables are fixed to be either integer or real. I am interested in the following MILP variant, where only one thing different from the ...
2
votes
2answers
84 views

Best way to solve a optimization problem with no objective function?

I have a MILP but fixed the objective function, so at each iteration is constant.Therefore, I solve a constraint satisfaction problem. Is there an algorithm to solve this kind of problem fast? I have ...
7
votes
2answers
159 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
143 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
120 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
146 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
115 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
86 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
129 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
57 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
103 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
76 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
66 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
170 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
200 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
79 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
316 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
112 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
189 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
93 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
256 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
41 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
162 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
194 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
48 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
127 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
80 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
145 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
104 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
200 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
602 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
107 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
104 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
203 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
140 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
155 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 ...
16
votes
1answer
227 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
114 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
168 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 ...