# Tag Info

54

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 BP - Bilevel Program BLP - Binary ...

26

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" ...

21

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

20

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

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

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

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

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

11

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 optimal. Feasibility problem. Some optimization modeling systems or optimization software require an objective to be provided. In such case, you can specify the ...

10

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 duration $w_o$, each bin is a machine that is available for only $c_b$ time units, and $z$ is the makespan. It is also a special case of the bottleneck ...

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

9

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 with an incomplete edge set, does there exist a closed tour in the graph such that every city is visited exactly once? Or find a schedule that satisfies all ...

8

Such a graph is called bridgeless.

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., "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

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.}\ \ \ & \sum_{j=1}^{J}x_{ij}=n_{i}\ \ \ i=1,\dots,I\\ & \sum_{i=1}^{I}a_{i}x_{ij}=w_{j}\ \ \ j=1,\dots,J\\ & w_{j}\le w_{\max}\ \ \ j=1,\dots,J\\ & 0\le ...

6

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 algorithms that relied exclusively on adding cuts to the LP relaxation (no branching). I would consider branch and cut different from logical or combinatorial Benders ...

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

5

These are called Generalized Upper Bound (GUB) constraints.

4

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, which is different from traditional MILP solvers. Note that LocalSolver is commercial software. Nevertheless, it is free for faculty and students. Below is ...

3

within CPLEX CPOptimizer you could rely on the pack constraint. A slight change of the model in the documentation: using CP; int m = 2; int n = 3; dvar int l[j in 1..m] in 0..10000; dvar int p[i in 1..n] in 1..m; dvar int nb; int w[1..n] = [i : 1 | i in 1..n]; // minimizing the weight of the heaviest bin. minimize max(i in 1..m) l[i]; subject to { ...

3

Don't know if there's a definition per se, but for any constraint that consists of solely integer variables, it is highly beneficial for all the coefficients to be integral as well, because that allows us to easily apply integer cuts. If the coefficients are not naturally integral, we can impose that by applying GCD rounding. In this example, you have a ...

3

For a Poisson process the rate of events is constant. The distribution of time between events in the Poisson process is exponential with $F(v)=1-e^{-\lambda v}$ for $v\ge 0$ which gives the hazard rate $\lambda$. So a non-constant hazard rate can be seen as a way of comparing with a Poisson process, an increasing hazard rate means the events come faster and ...

3

I've seen the first one under the name "moving horizon models". It seems to me that some people refer to the second with the term "online" (as in "online optimization"), which (confusingly) does not refer to the Internet but to reacting as new data points (orders, gate changes, accident reports) arrive. The fifth one is referred ...

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