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
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 ...
satk0's user avatar
  • 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 ...
ConMan's user avatar
  • 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 ...
HunKhle's user avatar
  • 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 ...
Arctic_Skill's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
ABDE's user avatar
  • 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 ...
ABDE's user avatar
  • 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 ...
S. M.'s user avatar
  • 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 ...
Noby's user avatar
  • 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 ...
iyui's user avatar
  • 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 ...
Walton P. Coutinho's user avatar
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 ...
KK29's user avatar
  • 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 ...
A.Omidi's user avatar
  • 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 ...
Ir8_mind's user avatar
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 ...
ryrie23's user avatar
  • 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 ...
Matheus Diógenes Andrade's user avatar
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 ...
Eduardo Silva's user avatar
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}...
falamiw's user avatar
  • 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 ...
BftA's user avatar
  • 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 ...
Daniele Cuomo's user avatar
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 ...
Benjamin Beer's user avatar
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 ...
J. Dionisio's user avatar
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 ...
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
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 ...
Erel Segal-Halevi's user avatar
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 ...
Linh OR's user avatar
  • 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) ...
Rutger's user avatar
  • 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 ...
independentvariable's user avatar
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 ...
user5966's user avatar
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 ...
Brondahl's user avatar
  • 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 ...
Samuel Bismuth's user avatar
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 ...
Monotros's user avatar
  • 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].$$...
independentvariable's user avatar
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. $...
Jose_Peeterson's user avatar
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 ...
dkent's user avatar
  • 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....
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
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\\ ...
Samuel Bismuth's user avatar
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 ...
MAJID majid's user avatar
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 ...
Samuel Bismuth's user avatar
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 ...
orpanter's user avatar
  • 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 ...
Barry S.'s user avatar
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, ...
Kuifje's user avatar
  • 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 ...
maxmitz's user avatar
  • 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 ...
mdslt's user avatar
  • 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 ...
maxmitz's user avatar
  • 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$ ...
PetaGlz's user avatar
  • 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 (...
maxmitz's user avatar
  • 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 ...
Quasar's user avatar
  • 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 ...
Handballer73's user avatar