# Questions tagged [algorithms]

For questions related to the design or implementation of algorithms (exact or heuristic) for solving optimization problems.

104 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
• 5,432
1 vote
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},\\ ...
• 77
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 ...
• 77
1 vote
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 ...
• 11
1 vote
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+...
• 4,037
1 vote
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 ...
• 123
1 vote
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 ...
• 111
1 vote
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 ...
• 11
1 vote
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 ...
• 317
1 vote
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 ...
• 317
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 ...
• 1
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 ...
• 1
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 ...
• 21
1 vote
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 ...
• 11
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 ...
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 ...
• 21
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 ...
• 8,960
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
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 ...
• 21
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 ...
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 ...
1k views

• 3,980
169 views

• 615