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
2 answers
270 views

Efficient Algorithm for Scheduling 140 Predefined 1:1 Meetings with Variable Participant Constraints Over 7 Slots?

I’m tasked with organizing a large number (130) 1:1 meetings for 50 people across a limited number of time slots (7) during a conference. I am seeking advice on the best algorithmic approach to tackle ...
Toby's user avatar
  • 11
1 vote
1 answer
75 views

Understanding (1+ ε) approximation when objective is discrete

Some problems in operations research have (1+ε) approximation algorithms which run in polynomial time. So we have an algorihm that produces a solution which is whose objective is within that factor (1+...
worldsmithhelper's user avatar
1 vote
0 answers
64 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 ...
satk0's user avatar
  • 123
1 vote
1 answer
53 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 ...
ConMan's user avatar
  • 111
1 vote
1 answer
95 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 ...
HunKhle's user avatar
  • 11
1 vote
2 answers
315 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 ...
Arctic_Skill's user avatar
1 vote
1 answer
97 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 ...
Arctic_Skill's user avatar
0 votes
0 answers
33 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 ...
ABDE's user avatar
  • 1
0 votes
1 answer
69 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 ...
ABDE's user avatar
  • 1
2 votes
1 answer
173 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 ...
Noby's user avatar
  • 21
1 vote
2 answers
243 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 ...
iyui's user avatar
  • 11
3 votes
2 answers
197 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 ...
Walton P. Coutinho's user avatar
2 votes
1 answer
131 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 ...
KK29's user avatar
  • 21
2 votes
0 answers
100 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 ...
A.Omidi's user avatar
  • 8,882
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 ...
Ir8_mind's user avatar
2 votes
1 answer
84 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 ...
ryrie23's user avatar
  • 21
3 votes
0 answers
76 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 ...
Matheus Diógenes Andrade's user avatar
2 votes
1 answer
265 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 ...
Eduardo Silva's user avatar
5 votes
1 answer
1k 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}...
falamiw's user avatar
  • 157
3 votes
1 answer
149 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 ...
BftA's user avatar
  • 31
2 votes
1 answer
61 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 ...
Daniele Cuomo's user avatar
2 votes
0 answers
99 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 ...
Benjamin Beer's user avatar
7 votes
1 answer
431 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 ...
J. Dionisio's user avatar
2 votes
2 answers
223 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 ...
Elis's user avatar
  • 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 ...
Antonio's user avatar
  • 319
2 votes
2 answers
202 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 ...
Erel Segal-Halevi's user avatar
1 vote
2 answers
599 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 ...
Linh OR's user avatar
  • 21
4 votes
1 answer
210 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) ...
Rutger's user avatar
  • 115
1 vote
2 answers
194 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 ...
user5966's user avatar
4 votes
0 answers
81 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 ...
Brondahl's user avatar
  • 171
5 votes
0 answers
113 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 ...
Samuel Bismuth's user avatar
7 votes
3 answers
889 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 ...
Monotros's user avatar
  • 179
2 votes
2 answers
157 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].$$...
independentvariable's user avatar
0 votes
1 answer
169 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. $...
Jose_Peeterson's user avatar
7 votes
2 answers
561 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 ...
dkent's user avatar
  • 217
2 votes
1 answer
133 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....
Duh Huh's user avatar
  • 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 ...
Shawky's user avatar
  • 29
3 votes
0 answers
108 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\\ ...
Samuel Bismuth's user avatar
1 vote
0 answers
70 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 ...
MAJID majid's user avatar
9 votes
2 answers
543 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 ...
Samuel Bismuth's user avatar
2 votes
2 answers
605 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 ...
orpanter's user avatar
  • 517
7 votes
2 answers
256 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 ...
Barry S.'s user avatar
2 votes
1 answer
838 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, ...
Kuifje's user avatar
  • 13.3k
1 vote
1 answer
226 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 ...
maxmitz's user avatar
  • 659
3 votes
1 answer
648 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 ...
mdslt's user avatar
  • 615
4 votes
1 answer
214 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 ...
maxmitz's user avatar
  • 659
5 votes
1 answer
168 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$ ...
PetaGlz's user avatar
  • 75
5 votes
1 answer
253 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 (...
maxmitz's user avatar
  • 659
0 votes
1 answer
78 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 ...
Quasar's user avatar
  • 203
1 vote
1 answer
346 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 ...
Handballer73's user avatar