Operations Research Stack Exchange
Operations Research Stack Exchange

Most Popular

more tags
1500 questions
9
votes
3 answers

Is Dantzig-Wolfe and Benders' Decomposition still applied in Operations Research?

A year ago, I had taken my master's degree class Optimisation Theory, and we were learning Dantzig-Wolfe Decomposition and Benders' Decomposition. I found it very challenging to use these algorithms since there are many iterations inside of them. I…
dozgunay
  • 139
  • 5
9
votes
6 answers

Are optimization results stochastic?

I'm asking myself for some time if the results of optimization are random. As search for stochastic and optimization gives results about stochastic optimization but does not help with the stochasticity of optimization. Let's say we have a simple…
JaBe
  • 491
  • 3
  • 11
9
votes
1 answer

Capacitated VRP-TW: Gehring & Homberger instances

I am trying to benchmark our vehicle routing solver against Gehring & Homberger instances. However, I got bit puzzled by the route duration constraint (maximum driving / maximum working time). In some data set format, this constraint is enforce as…
VeGh
  • 91
  • 2
9
votes
1 answer

Verifying optimality of heuristic solutions

Suppose that we have an mixed-integer linear optimization problem and we obtain a solution using a heuristic. How can one check 1) whether this solution is optimal and 2) how difficult is it to do so? My question is motivated by an instance of CVRP.…
Leon Lan
  • 185
  • 1
  • 8
9
votes
2 answers

Gurobi finishes with 'infeasible' although optimal solution exists

I am using Gurobi (in Python through gurobipy) to solve an IP on tournament graphs. I am searching for a non-zero minimal integer weighting such that for every vertex the sum of weights put on the vertices connected through an outgoing edge is at…
Legsleg
  • 153
  • 7
9
votes
2 answers

CPLEX exceeds time limit issue

I am solving a MILP model using CPLEX 12.8.0, but CPLEX exceeds the time limit on some test instances. More specifically, I set the time limit for 30 minutes using the cplex.setParam(IloCplex::TiLim, 1800) command, but in some instances, CPLEX runs…
OllieK
  • 99
  • 3
9
votes
2 answers

Dealing with Symmetry. Commercial solver defaults vs manual implementations

Since the modeler has domain/business knowledge of the problem being solved, is it possible to manually implement Isomorphism Pruning or Orbital branching and beat the default methods implemented by the solvers under the hood. Also, some of the…
user3711946
  • 305
  • 1
  • 4
9
votes
1 answer

Odd behavior in the branch bound and price algorithm with column generation

I have two questions on branch-bound-and-price. Why does it sometimes fail? For instance, the paper by Dabia et al shows results where the proposed algorithm fails for some cases. The paper does not explain why it fails. Is it because of the time…
Dr. Soomin Woo PhD
  • 91
  • 2
9
votes
0 answers

Modelling resource dependency in the assignment problem

The assignment problem is well-studied and has a nice polynomial time algorithm. I'm interested in an extension of this problem where all edges are in a certain group and taking multiple edges from the same group can end up with diminishing returns…
Discrete lizard
  • 1,482
  • 6
  • 25
9
votes
8 answers

Can we consider the (Famous) "Trolley Problem" as an Optimization Problem?

In the (famous) Trolley Problem (https://en.wikipedia.org/wiki/Trolley_problem) - a runaway train is out of control and unfortunate people are stuck on two different railway tracks. The railway conductor has a choice to make in deciding which track…
stats_noob
  • 1,831
  • 7
  • 30
9
votes
6 answers

Any good MIP LaTeX template?

I am looking for a LaTeX template where a MIP problem formulation will look well-formatted. Can anyone provide some example LaTeX code?
Eddiee
  • 533
  • 2
  • 13
9
votes
1 answer

Modelling stronger binary expression

$\delta_1, \delta_2, ..., \delta_k, W$ are binary variables and the constraint $δ_1 + δ_2 + \ldots + δ_k ≤ W$ holds. Is it better to write $$\delta_1 + \delta_2 + \ldots +\delta_k \leq W$$ or \begin{gathered} \delta_1 \leq W \\ \delta_2 \leq W…
Clement
  • 2,252
  • 7
  • 13
9
votes
1 answer

A clustering problem with 0 or 1 distances for minimizing the summation of distances

I have a clustering problem with $\{0,1\}$ distances between a set of nodes, which can be stated as follows: Given: Finite set $\mathbb{X}$, a distance $d(x, y) \in \{0,1\}$ for each pair $(x, y) \in \mathbb{X}$, and positive integers $S$ and…
OR Junior
  • 521
  • 2
  • 8
9
votes
2 answers

"Partial" Lagrangian Dual in LP

Consider the optimization problem \begin{align}\label{opt-lp}\tag{Primal} \begin{array}{cl} \underset{x \in \mathbb{R}^n}{\text{minimize}} & c^\top x \\ \text{subject to} & Ax = a \\ & Bx = b \end{array} \end{align} where $A \in \mathbb{R}^{m \times…
independentvariable
  • 3,980
  • 10
  • 36
9
votes
2 answers

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 classic MILP: Let $n$ be the number of the MILP…
Samuel Bismuth
  • 173
  • 7
1 2 3
…
99 100