Questions tagged [algorithms]
For questions related to the design or implementation of algorithms (exact or heuristic) for solving optimization problems.
89
questions
2
votes
1
answer
36
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
54
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 ...
- 7,559
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
59
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
61
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,059
2
votes
1
answer
246
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
352
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
110
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
56
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
93
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
399
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
162
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
42
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
144
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
422
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
163
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
848
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,808
1
vote
2
answers
180
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
76
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
107
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
577
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
146
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,808
0
votes
1
answer
160
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. $...
- 347
7
votes
2
answers
486
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
109
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
82
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
57
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
473
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
254
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 ...
- 423
7
votes
2
answers
225
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
664
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.3k
1
vote
1
answer
182
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
514
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 ...
- 529
4
votes
1
answer
187
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
128
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
199
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
69
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
285
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
2
votes
1
answer
129
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 ...
- 175
4
votes
1
answer
238
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 ...
- 11.8k
4
votes
1
answer
156
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 ...
- 143
9
votes
2
answers
522
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 "...
- 241
2
votes
3
answers
205
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?
...
- 153
8
votes
1
answer
253
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,070
2
votes
2
answers
366
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 ...
- 445
6
votes
2
answers
104
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 ...
- 163
6
votes
3
answers
1k
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
1
answer
158
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
1
answer
247
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 ...
- 445