Tag Info

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

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,809

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

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,809

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,519

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

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

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.7k
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 ...
• 236

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.3k
Accepted

Name for this ILP problem type

This is called the budgeted maximum coverage problem.
• 23.3k
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 ...

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 ...
• 12.7k

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

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

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,066

"Partial" Lagrangian Dual in LP

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

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

Such a graph is called bridgeless.
• 23.3k

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 · ...
• 11.3k

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,503
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

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

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

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 ...
• 11.3k

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,684

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
Accepted

Combined arc capacity constraints in network flows

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