Questions tagged [algorithms]
For questions related to the design or implementation of algorithms (exact or heuristic) for solving optimization problems.
100
questions
0
votes
0
answers
15
views
Resources about Busacker & Gowen algorithm
I have a relatively hard time understanding the Busacker & Gowen algorithm. I could not
find any resources on it, contrary to Ford-Fulkerson method that is described in Comen's "Introduction ...
- 113
1
vote
1
answer
46
views
Making a batch of related linear problems more efficient
I have a linear system that is of the form
$$My = b \\
L \leq y \leq U$$
i.e. all of the $y_i$ are potentially bounded, and there are various linear relationships between them.
I want to find the ...
- 111
1
vote
1
answer
84
views
Optimization algorithm for space debris
I'm currently working on a research project to optimize the recovery of space debris. We have to recover 50 pieces of space debris with the minimum number of missions possible. The missions are sent ...
- 11
1
vote
2
answers
106
views
Understanding the L-shaped-method and the different variants of it
I am currently trying to understand the integer L-shaped-method/stochastic version of Benders Decomposition because I have practical problem MIP that is stochastic and thus has very good decomposition ...
- 139
1
vote
1
answer
67
views
How do I check convergence in stochastic Benders?
So in the deterministic version of Benders, the main process works like this:
I initialize my x-vector (Integer variables from the master problem) and solve the dual subproblem (SP).
I add an ...
- 139
0
votes
0
answers
26
views
Error while using subgradient method to update lagrange multipliers
I am trying to implemet the subgradient method in Lagragian relaxation to update the multiplier lamda which has three dimension, I have ecountered an Except error, it looks the is bugs in the code. it ...
- 1
0
votes
1
answer
54
views
Finding lower bound (maximization problem) in Lagrangian Relaxation with subgradient method
I have tried to implement a toy problem (MIP) from the literature using Lagrangian Relaxation with the subgradient method, I implemented it correctly and I got the upper bound which is updated at each ...
- 1
2
votes
0
answers
121
views
Is OCN=DOCN decidable?
One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that
cannot decrease below zero and cannot be explicitly tested for zero.
An OCN $A$ over alphabet $\sum$ accepts a ...
- 21
2
votes
1
answer
113
views
Find an algorithm for quickly computing results to a given equation
There is an equation:
280a + 80b + 75c + 50d + 25e - 30f - 42g = R
a, b, c, d, e, f, g - those are modifiers. They're strictly ...
- 21
1
vote
2
answers
202
views
Best algorithm for scheduling interviews
I posted the same question on stackoverflow and immediately referred to post it here.
I want to think about the best algorithm which let the interviewer meet maximum number of candidates.
Suppose that ...
- 11
3
votes
2
answers
153
views
Simplest Quadratic Programming algorithm for teaching
Can anyone recommend a straightforward quadratic programming (QP) algorithm suitable for an undergraduate engineering class? I'm interested in finding an algorithm that they can easily grasp and ...
2
votes
1
answer
103
views
Finding the minima of a multivariable function with constraints
I have a multivariable function (9 variables), and I want to find where the function records a minimum value. The function is as follows:
It also has a few constraints:
I tried a brute force ...
- 21
2
votes
0
answers
86
views
The linearization of the logical constraints
I know the logical constraints can be linearized by either the logical representation of whose relation, (for pure binary variables e.g. CNF/DNF) or for general form by using Big-M formulation. As I ...
- 8,382
5
votes
6
answers
2k
views
How can I solve this algorithmic task in Python?
I am trying to solve this task:
There are three datasets: first data on offices in cities: each city has a certain number of offices and each office has its own capacity of employees. Second, data on ...
- 61
2
votes
1
answer
76
views
How to find the maximum probability of satisfying the conditions in all combinations of arrays
for example, I got a list of tokens and each token's number of characters(length) is
length = [2, 1, 1, 2, 2, 3, 2, 1, 1, 2, 2, 2]
and here is the list of each ...
- 21
3
votes
0
answers
70
views
Flow problem with flow demands
Recently I found a subproblem in a project I am working with. This problem is a sort of flow variant, as you will see. And I am looking for literature-related articles and also fast approaches for ...
- 1,198
2
votes
1
answer
255
views
Is Dantzig-Wolfe decomposition an example of a divide and conquer algorithm?
Typical Divide and Conquer algorithm solves a problem using following three steps:
Divide: This involves dividing the problem into smaller sub-problems.
Conquer: Solve sub-problems by calling ...
- 153
5
votes
1
answer
775
views
Understanding L-shaped algorithm in a two-stage stochastic problem
I am facing a problem understanding the L-shaped algorithm in a two-stage stochastic problem.
$$\operatorname{Min} z=100 x_1+150 x_2+E_{\xi}\left(q_1 y_1+q_2 y_2\right)$$
subject to
$$
\begin{aligned}...
- 157
3
votes
1
answer
141
views
Benders Decomposition for Fixed Charge Transportation Problem
I am trying to write down the steps in Benders decomposition for the Fixed Charge Transportation Problem and was hoping someone could confirm/deny whether my understanding of it is correct. The ...
- 31
2
votes
1
answer
60
views
Find the shortest path connecting some (s,t) - a greedy (?) criterion to a multi-commodity flow problem
At page 7 from these slides there is a Greedy algorithm I want to implement.
It says
let $P_i$ be the shortest path (if one exists) that [...]
connects some ($s_j$, $t_j$) pair that is not yet ...
- 561
2
votes
0
answers
98
views
Optimal spending of cash problem
I have often wondered whether there is an optimal way to spend cash denominations. For example: Suppose that Bob needs to pay Jill \$5, Jane \$10, Billy \$3.50 and John \$45.75. Furthermore suppose ...
7
votes
1
answer
407
views
Can't solve a specific instance of Gilmore & Gomory Cutting Stock with Delayed Column Generation
I am now somewhat comfortable with delayed column generation, but one specific example has been bugging me, as it's quite simple (on the second iteration we stop) and I can't reach the optimal ...
- 516
2
votes
2
answers
204
views
Assign jobs to least people with multiple job constraints
Assume I have an infinite number of staff/supply. I have a table of how much time in hours needs to be spent on certain tasks:
Task
Demand
A
0.75
B
0.8
C
0.65
D
0.7
E
0.6
F
0.65
And the tasks ...
- 23
1
vote
0
answers
47
views
Adjust pseudocode for outliers
I'm doing a clustering algorithm to group properties. In this sense, I have geographic coordinate information for these properties. However, for the clustering process, I would like to exclude some ...
- 319
2
votes
2
answers
179
views
A branch-and-bound algorithm for number partitioning
I am working on a branch-and-bound algorithm for number partitioning, similar to Complete greedy algorithm. The input is a list of positive integers and an integer $k$; the output is a partitioning of ...
1
vote
2
answers
529
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 ...
- 21
4
votes
1
answer
186
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)
...
- 115
5
votes
2
answers
1k
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 ...
- 3,980
1
vote
2
answers
186
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 ...
- 51
4
votes
0
answers
79
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 ...
- 171
5
votes
0
answers
110
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 ...
- 173
7
votes
3
answers
734
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 ...
- 179
2
votes
2
answers
155
views
Minimizing a KS function
For convex functions $f_i, \ i \in I$, the KS function is defined as the following for any $\rho > 0$:
$$KS[\{ f_i \}_{i \in I}](x):= (1/ \rho) \ln \left[ \sum_{i \in I} \exp(\rho f_i(x)) \right].$$...
- 3,980
0
votes
1
answer
166
views
Algorithms and analytical solution methods/tools to solve an optimization problem for a particular objective function
I have the following objective function:
\begin{equation}
\min_{I_{i,v}} \ \sum^{N_v}_{v}\sum^{TT_v}_{i} \ C_{loss,cyc}
\end{equation}
where $I_{i,v}$ is the only positive decision variable. $...
- 349
7
votes
2
answers
531
views
Optimization Solution Framework
I am working through Pascal Van Hentenryck's excellent discrete optimization course on Coursera.
While the course certainly touches on it in some ways, I am looking for more of a framework in terms of ...
- 117
2
votes
1
answer
123
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....
- 29
2
votes
0
answers
42
views
Importance of Polynomial Time Approximation algorithm for special case [closed]
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 ...
- 29
3
votes
0
answers
97
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\\
...
- 173
1
vote
0
answers
63
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 ...
- 335
9
votes
2
answers
524
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 ...
- 173
2
votes
2
answers
420
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 ...
- 507
7
votes
2
answers
249
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 ...
- 73
2
votes
1
answer
740
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, ...
- 12.9k
1
vote
1
answer
212
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 ...
- 659
3
votes
1
answer
598
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 ...
- 573
4
votes
1
answer
206
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 ...
- 659
5
votes
1
answer
149
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$ ...
- 75
5
votes
1
answer
227
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 (...
- 659
0
votes
1
answer
77
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 ...
- 203
1
vote
1
answer
332
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 ...
- 291