# Questions tagged [algorithms]

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

66 questions
Filter by
Sorted by
Tagged with
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....
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 ...
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 ...
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\\ ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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$ ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 "...
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? ...