A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

40

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 Science IE - Industrial Engineering MS - Management Science OM - Operations Management OR - Operations Research Problem classes BLP - Binary Linear Program BMI - ...

23

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 shortest tour) Heuristic: Algorithms that do not give any worst-case guarantee whatsoever. Finite convergence and runtime are separate from "exactness" ...

19

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$ and $b\in\Bbb R$. Polyhedra Polyhedra is the plural of polyhedron. Polytope A polytope is a bounded polyhedron, equivalent to the convex hull of a ...

15

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 iteration. The Ford-Fulkerson algorithm for solving maximum flow is an example where we have a feasible flow in every iteration, or the simplex method, where we have ...

14

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 nothing is said, I associate with "solution" (without qualifiers) that it is feasible, that is, it satisfies all the constraints. This goes also for "a ...

13

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 guarantee).

13

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 unconstrained problems: an easy example is bisection search. So when people say "constrained optimization," they are emphasizing that they're considering the ...

12

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 are $0$). But the primary practical reason to put the constraints in a standard form - that is, $g_i(\mathbf x) \le 1$ - is that then the dual of a geometric ...

12

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 solution has an objective better than that of x*. Typically, exact methods compute two types of bounds: lower (L) and upper (U) bounds. Optimality is then proven whenever both bounds coincide. In ...

11

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 nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques. Rewriting this in ...

10

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 all of the constraints. In linear programming, you have continuous variables and linear constraints, which can be equalities or inequalities. For example, let ...

9

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 comments) has polynomial runtime. But the term is often misused to refer to a heuristic that may or may not have such a provable bound. I would have interpreted ...

8

$\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 · Arash Hassibi. Look on p. 73 equation (6), and the paragraph which precedes it: The conversion of a GP to a convex problem is based on a logarithmic change of ...

8

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 unfeasible solution is useless to them, it's pretty easy to argue this is also the dictionary definition (an answer to, explanation for, or means of effectively ...

7

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 approaches can be considered to solve this kind of problems depending on their size. For small instances, researchers usually use exact methods. Exact methods ...

6

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 first assume that only globally optimal solutions are of interest. Let us just consider feasible and globally optimal solutions to the problem. What does the ...

6

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 that a piece of software determined that the problem is infeasible, not an actual vector of values.

5

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 variable representing a physical process has a finite domain (presuming that the physicists are correct in saying there is a finite amount of matter in the known ...

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