Michael Feldmeier
  • Member for 2 years, 8 months
  • Last seen this week
Optimization terminology: "Exact" v. "Approximate"
Accepted answer
27 votes

Exact: algorithm will eventually provide a provably optimal solution. Approximate: algorithm will eventually produce a solution with some guarantees (e.g. a tour being at most twice as long as the ...

View answer
Great Unsolved Problems in O.R
26 votes

Two open problems in linear optimization (which is considered more or less a 'solved' subfield by many): Is there a pivoting strategy for the Simplex algorithm guaranteeing to find an optimal vertex ...

View answer
Automating the column generation decomposition process
Accepted answer
19 votes

You should take a look at GCG, a plugin for SCIP and part of the SCIP Optimization Suite. After the standard presolving process of SCIP, GCG performs a Dantzig-Wolfe decomposition of the problem to ...

View answer
Where can I find open source LP solvers?
19 votes

Mittelmann benchmarks a number of (LP-)Solvers, some of which are open source. A recent new open source solver is HiGHS.

View answer
Guidelines for Linear Optimization approaches?
Accepted answer
17 votes

Let's start with the easy one: Ellipsoid Method Never use it. Even though it might appear efficient in the complexity-theory sense, it performs terrible and suffers heavily from numerical issues. ...

View answer
Are there any OR challenges that are similar to kaggle's competitions?
16 votes

Google Hashcode had some optimization challenges in the past. Problem definitions and data from previous years can be found here.

View answer
Simplex-Implementations in professional Solvers
Accepted answer
16 votes

First of all, usually implementations are centered around the revised dual simplex, not the primal (even though solvers will still use a primal simplex method implementation for some tasks in the ...

View answer
The curse of the benchmark instances
16 votes

There are multiple aspects to this topic. What can be done by testset compilers to prevent finetuning? For one, testset creators are usually not including many very similar problems into the ...

View answer
Why is the programming code of many algorithms not public in the OR community?
15 votes

I agree with @independentvariable. What might be added is that many researchers actually do publish (and what's maybe even more valuable: maintain) their code, if they think it is useful. Take a look ...

View answer
Is This Constraint Convex?
13 votes

Counterexamples to your arguments: Argument 1: Only affine equality constraints are convex, $x = y^2$ is not convex. Argument 3: Take $f(x) = x^4$ and $g(x) = x$. Both are convex, but the ratio $h(x)...

View answer
What global MINLP solvers support trigonometric functions?
Accepted answer
12 votes

SCIP does not currently support any trigonometric functions as of this post from May 2018. COUENNE appears to handle $\sin$ and $\cos$ expressions. ANTIGONE appears to not support any trigonometric ...

View answer
When should I use dual Simplex over primal Simplex?
Accepted answer
8 votes

Not an expert on simplex, but here's my attempt on an answer: In general, the solution of the (previous) LP Relaxation will no longer be primal feasible when the primal LP is tightened (e.g. new cut ...

View answer
Does this $0-1$ integer program have any speciality?
7 votes

While this class of problems is still hard to solve (see the other answers for details), one speciality is that it has a trivial feasible solution $x=0$, which is not the case in general integer ...

View answer
Is there a canonical name for Score Folding (multiplying a priority soft constraint by a big weight)?
7 votes

The act of moving soft constraint into the objective function using penalties is closely related to Lagrangian Relaxation and Lagrangian Multipliers. The method penalizes violations of [...] ...

View answer
What is a solution?
6 votes

I mostly agree with Marco Lübbecke. I would like to add that "vectors of the right dimension" are sometimes called solution candidates. Also when we refer to an "infeasible solution" we often mean ...

View answer
Parallelization of an existing Adaptive Large Neighbourhood Search Heuristic
5 votes

Another paradigm to parallelize search heuristics is the Backbone strategy. See for example this paper. The main idea is to run multiple instances of an arbitrary heuristic in parallel, and then ...

View answer
Modeling floor function exactly
3 votes

You only specified $x$ is "continuous". I'll interpret this as $x$ is rational rather than real. This is not a terrible assumption, as floating point numbers in computers are rational anyways. A ...

View answer