58 votes
Accepted

What are common and not so common abbreviations in Operations Research?

This answer is a Community Wiki post to allow everybody to contribute to the list. As a guideline, only add abbreviations that most people in the field are familiar with. General CS - Computer ...
28 votes
Accepted

Optimization terminology: "Exact" v. "Approximate"

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 ...
24 votes

Dual bounds of integer programming problems

The notions of dual bound and primal bound originate a bit more generally, I think. We typically call an (iterative optimization) algorithm primal when it maintains a feasible solution in every ...
21 votes

Polyhedra, Polyhedron, Polytopes and Polygon

The following definitions are taken from this lecture. Polyhedron A polyhedron in $\Bbb R^n$ is the intersection of finitely many sets of all points $x$, such that $ax\le b$ for some $a\in\Bbb R^n$...
  • 5,199
14 votes

What is a solution?

Great question, @Dirk. People regularly stumble across this, and I believe the notion is not generally agreed upon. Here is how I use it. Main qualifiers for a solution are feasible and optimal. When ...
14 votes

Optimization terminology: "Exact" v. "Approximate"

An exact method will (typically within a bounded number of steps) provide a proven optimal solution. This is, a solution x* and a guarantee that no other feasible ...
13 votes

Optimization terminology: "Exact" v. "Approximate"

Exact: Provably optimal Approximate: offers an upper bound on the gap I would add heuristics: procedures that, as you described, may or may not provide an optimal solution (with out any proof or ...
  • 1,335
13 votes

What is quadratization?

One definition of quadratization (perhaps there is more) is provided in the paper by Boros, 2018. In non-mathematical terms, quadratization is defined as a quadratic reformulation of the ...
  • 5,199
13 votes

Difference between "Optimization" and "Constrained Optimization"?

You are right that most real-world problems are constrained, and therefore, for the most part, "optimization" and "constrained optimization" are synonymous. However, some algorithms only apply to ...
12 votes
Accepted

Geometric programming: Why are the constraints defined to be less than/equal to 1?

Some of the reasons are convention (and the reason $1$ is the convention is that after substituting $x_i = e^{y_i}$ and taking logs of both sides, we get a convex program where all right-hand sides ...
11 votes

Is a mathematical programming problem with no objective function an optimization problem?

Yes. But some software may require explicit specification of an objective, which can be a constant. Yes. An optimization solver will attempt to find a feasible solution. Any feasible solution is ...
11 votes
Accepted

Name for this ILP problem type

This is called the budgeted maximum coverage problem.
  • 23.3k
10 votes
Accepted

Has the expressibility of 'non-integrality testing' as extension to MILP been studied before?

Strict positivity, $x > 0$, is equivalent to the existence of nonnegative variable, $r \geq 0$, such that $xr \geq 1$. This means that it can be represented in second-order cone programming by the ...
10 votes

Optimization terminology: "Exact" v. "Approximate"

In addition to the other answers posted already, I'll add that the term approximation algorithm means an algorithm with a provable worst-case error bound that (as @MarcoLubbecke reminded me in the ...
10 votes

Polyhedra, Polyhedron, Polytopes and Polygon

These are all names used for the feasible set of a linear programming problem. In other words, all the combination of values for the decision variables that correspond to a solution, hence satisfying ...
10 votes

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

Let $w_o$ denote the weight of object $o$, and let $c_b$ denote the capacity of bin $b$. You can interpret this as a job shop scheduling problem. The correspondence is that each object is a job, with ...
  • 23.3k
9 votes

Is a mathematical programming problem with no objective function an optimization problem?

These problems are known as Constraint Satisfaction Problems. In contrast, problems with an objective function are known as Constraint Optimization Problems. Many examples exist. E.g. given some graph ...
9 votes

"Partial" Lagrangian Dual in LP

This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.
  • 23.3k
8 votes
Accepted

What is the name of the graph where any edge is part of a cycle?

Such a graph is called bridgeless.
  • 23.3k
8 votes

Geometric programming: Why are the constraints defined to be less than/equal to 1?

$\log 1 = 0$ could explain that: take $\log$ of both sides. Edit: I have now looked and found this in "A tutorial on geometric programming", Stephen Boyd · Seung-Jean Kim · Lieven Vandenberghe · ...
8 votes

What is a solution?

I often encounter a clear difference in the point of view of an operator (business) and a programmer (engineering): From the business POV: if it's not feasible, it's not a solution. Given that an ...
8 votes
Accepted

"Partial" Lagrangian Dual in LP

Based on the mentioned references, suppose the primal problem is: \begin{align} \begin{array}{cl} \underset{}{\text{minimize}} & c x \\ \text{subject to} & Ax = a \\ & Dx \leq e \\ & x ...
  • 6,206
7 votes

Optimization terminology: "Exact" v. "Approximate"

According to L. Jourdan, et. al.[1], "NP-hard problems are difficult to solve and no polynomial-time algorithms are known for solving them. Most combinatorial optimization problems are NP-hard. Two ...
  • 8,350
6 votes
Accepted

Logical / combinatorial Benders Decomposition vs Cutting plane method

I'm going to assume that "the cutting plane method" refers to branch and cut (branch and bound with cuts added at the root and possibly other nodes), as opposed to older cutting plane ...
  • 32k
6 votes

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

With a low to moderate number of distinct weights, this is a variant of a transportation problem. An appropriate model would be $$\begin{alignat*}{1} \min\ \ & w_{\max}\\ \text{s.t.}\ \ \ & \...
  • 32k
6 votes

What is a solution?

Here are two more "dimensions" to the question which have not yet been addressed in any of the other answers, but can be of great significance in practice. Global optimum vs. local optimum: I will ...
6 votes

What is a solution?

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 ...
5 votes

Difference between "Optimization" and "Constrained Optimization"?

Problems involving physical/tangible systems (such as production scheduling, crew assignment, ...) are inherently constrained, whether the modeler bothers to put all the constraints in or not. Any ...
  • 32k
5 votes
Accepted

Combined arc capacity constraints in network flows

These are called Generalized Upper Bound (GUB) constraints.
  • 23.3k
4 votes

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

Your problem can be modeled differently by following a set-based modeling approach instead of the classical Boolean modeling approach proposed above. This is a modeling approach offered by LocalSolver,...
  • 2,775

Only top scored, non community-wiki answers of a minimum length are eligible