Operations Research Stack Exchange
Operations Research Stack Exchange

Most Popular

more tags
1500 questions
7
votes
2 answers

Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms. It can also be formulated as an integer linear program. In general, an integer linear program might require…
Erel Segal-Halevi
  • 989
  • 5
  • 18
7
votes
3 answers

Modelling precedence relations

I have two tasks $i$ and $k$ with durations $d_i$ and $d_k$, where $d_i$ and $d_k$ are nonnegative variables. I would like to model that $i$ may precede $k$ or $k$ may precede $i$ and that they may not overlap. So, with $t_i$ and $t_k$ denoting the…
Clement
  • 2,252
  • 7
  • 13
7
votes
2 answers

Mixed-integer optimization with bilinear constraint

So I have an optimization problem of the following form: \begin{aligned} \max_{x,y} \quad & \sum_i x_i \\ \text{s.t.} \quad & \sum_i x_iy_i \leq a \\ \quad & x_{\min} \leq x \leq x_{\max} \\ \end{aligned} where $x$ is a vector of real (positive)…
Johnny
  • 293
  • 1
  • 7
7
votes
2 answers

Index of element in MILP vector decision variable that equals 1

Consider a decision variable in a MILP constrained: $$\sum_i p_i = 1$$ $$p_i\ \in \{0, 1\}$$ Obviously one element in $p$ is 1 and all others are 0. How can I set a decision variable to the index i of the element $p_i$ = 1? I think I can do this by…
davidconf
  • 71
  • 1
7
votes
4 answers

What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?

I have a fixed number of bins which are themselves weightless. Each bin can hold only a fixed amount of weight. Not all bins have the same capacity. I also have a fixed number of objects each of which has a weight. Not all objects have the same…
Richard
  • 543
  • 2
  • 13
7
votes
3 answers

Textbook recommendation for linear programming decomposition fundamentals

I am looking for a textbook on linear programming decomposition fundamentals. The book should be clear and easy-to-follow for self study and should include examples to illustrate the concepts.
DSPinfinity
  • 409
  • 2
  • 12
7
votes
3 answers

How do Quadratic Programming solvers handle variables without bounds?

Solvers for non-convex QPs generally do the McCormick relaxation of the term $xy=z$ and then do spatial branch and bound. This requires that $x$ and $y$ have given bounds, how do they handle the case when the variables are unbounded?
user3680510
  • 3,655
  • 6
  • 26
7
votes
2 answers

How to learn about some general Issues related to solvers?

I have found the following slides of talks: Consistency in solvers Performance variability in mixed integer programming I am looking for similar resource (slides, videos, articles, etc.) that treats issues and subjects (numerical issues,…
Leo_Divrik
  • 71
  • 2
7
votes
1 answer

Square packing variant

I saw the following problem and was looking for references about the problem. The problem is stated as “The green field is the empty area, the dark green 2x2 blocks are trees and the grey area is the off area. I’m wondering how to place the blocks…
Ryan Howe
  • 309
  • 1
  • 7
7
votes
2 answers

Measuring performance of Genetic Algorithms

I'm looking for information concerning Genetic Algorithm (GA) outputs reliability. I've found some papers applying metaheuristics that have run their algorithms 30 times and got the best solution among them. However, I did not find a consistent…
campioni
  • 1,133
  • 5
  • 13
7
votes
1 answer

Classical Benders decomposition algorithm implementation details

Given the following problem: \begin{align} P: \min_{x,y}&\quad c^\top x+f^\top y\\ \text{s.t.}&\quad Ax+By=b\\ &\quad y\in Y\\ &\quad x\geq 0 \end{align} Problem $P$ is equivalent to: \begin{align} P': \min_{y}&\quad f^\top…
Joris Kinable
  • 3,451
  • 8
  • 19
7
votes
0 answers

Estimate lagrangian multiplier based on instance characteristics

Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. Moreover, we add a proportion constraint. That is, each…
Pete S
  • 123
  • 4
7
votes
1 answer

How to check whether two formulations are equivalent?

I am given two formulations, that is, two integer programs $ (IP1)\quad \min \{c^tx \mid Ax\geq a, x\in Z^n\} $ and $ (IP2)\quad \min \{d^ty \mid By\geq b, y\in Z^m\} $ and I wish to check whether they describe the same problem. That is, I wish to…
Marco Lübbecke
  • 5,919
  • 22
  • 64
7
votes
1 answer

Is the solution of a convex combination of the objective in simple problems a convex combination of the solutions of the same problems?

Let $\mathbf{A}=\left(a_{ij}\right)$ be a $n\times J$ matrix with $a_{ij}\geq 0$, $n>J$ and such that no row has all its entries equal to zero, and each column has at most one zero. Let also $\mathbf{q}=\left(q_i\right)$ a $n\times 1$ vector of…
Patricio
  • 591
  • 3
  • 9
7
votes
1 answer

MILP formulation for minimum set Vertex cover problem

I’m sorry to bother you with this simple question. I would like to model a simple model of the minimum cover vertex set problem. I believe that the original problem is such as $$ \min \quad \sum_{v\in V} x_v $$ subject to $$ x_u + x_v \ge 1 \quad…
Amedeo
  • 443
  • 3
  • 8
1 2 3
…
99 100