Skip to main content

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
3 votes
2 answers
57 views

Constrained optimization with heuristic algorithm in actual production

In a real production problem, if you decide to use a heuristic algorithm (such as GA), what are the mainstream methods to deal with constraints in constraint optimization? I mean, I knew that there ...
CangWangu's user avatar
2 votes
0 answers
82 views

Quickest known integer relation algorithm in the case of signs

Let $x_1,\cdots,x_n,k$ be integers such that $|k|\le\sum_{i=1}^n|x_i|$. What is the quickest known algorithm to determine $w_i\in\{-1,0,1\}$ such that $k=\sum_{i=1}^nw_ix_i$ where they exist? What is ...
TheSimpliFire's user avatar
  • 5,432
1 vote
0 answers
43 views

Primal-dual simplex method for general LP

I've learned the primal-dual method for standard LP, but for a general LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ ...
andy's user avatar
  • 77
0 votes
0 answers
59 views

What's the dual of an LP in its general form?

For an LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ &l^{x}\leq x \leq u^{x} \end{align} how can we get its dual ...
andy's user avatar
  • 77
1 vote
2 answers
282 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
77 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
79 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
58 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
99 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
452 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
104 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
36 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
84 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
193 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
270 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
217 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
139 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
108 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,960
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
86 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
77 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
272 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
163 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
440 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
240 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
206 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
644 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
216 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
197 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
941 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
160 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
574 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
136 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
44 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
111 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
71 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
554 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
722 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
261 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
851 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.5k
1 vote
1 answer
241 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
690 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
216 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