Skip to main content

# Tag Info

## Hot answers tagged terminology

61 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 ...
• 2,856
27 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 ...
• 5,929
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,412
15 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,412
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 ...
• 5,929
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 ...
• 1,574
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,355
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 ...
• 13.1k
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 ...
• 235
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 ...
• 13.5k
11 votes
Accepted

### Name for this ILP problem type

This is called the budgeted maximum coverage problem.
• 32.7k
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 ...
• 13.1k
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 ...
• 671
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 ...
• 32.7k
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 ...
• 3,461
9 votes

### "Partial" Lagrangian Dual in LP

This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.
• 32.7k
9 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 ...
• 8,940
8 votes
Accepted

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

Such a graph is called bridgeless.
• 32.7k
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 · ...
• 13.5k
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 ...
• 4,891
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,667
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 ...
• 39.5k
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.}\ \ \ & \...
• 39.5k
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 ...
• 13.5k
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 ...
• 2,856
6 votes

### Using the "true" sample rather than sampling from a distribution - is there a name for this?

This is called an Empirical distribution function. You can check out this.
• 1,696
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 ...
• 39.5k
5 votes
Accepted

### Combined arc capacity constraints in network flows

These are called Generalized Upper Bound (GUB) constraints.
• 32.7k

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