# Tag Info

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

12

The best publicly available CPLEX global QP algorithm description I am aware of is the tutorial presentation by Ed Klotz of IBM at the March 2018 INFORMS Optimization conference. Performance Tuning for Cplex’s Spatial Branch-and-Bound Solver for Global Nonconvex (Mixed Integer) Quadratic Programs ABSTRACT: MILP solvers have been improving for more than ...

12

While iteratively approximately solving the first order Karush-Kuhn-Tucker conditions, many (nonconvex) nonlinear solvers "roll downhill", i.e., enforce descent (for minimization) of the objective function for algorithms which attain and maintain primal feasibility, or improvement in a merit function (or similarly with filter methods) for algorithms which ...

9

If the IPOPT termination condition is Optimal Solution Found then the returned solution is locally optimal. IPOPT is, by design, not a global solver and therefore does not have any built-in infrastructure for checking if a solution is global vs. local. However, if you know certain features of your problem, like if it is convex, then you as the user might be ...

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

8

In your question, you call a problem 'solvable' if there exists an $\hat{x} \in M$ such that \begin{align}c^\top\hat{x} = \inf_{x \in \mathbb{R}^n}&\quad c^\intercal x\\\textrm{s.t.}&\quad x \in M.\end{align} The following example shows that the answer to your question is no. Let $n = 2$ and take $c = (0,1)^\top$. Furthermore, let $$M = \{x \in \... 8 MIP solvers such as CPLEX & Gurobi indicate a gap (in %) between the current best solution and the current best dual bound (which is a lower bound for a minimization problem). In general, the optimum value is not known until, well, the problem is solved. Different solvers may use slightly different definitions: CPLEX:$$ g = \frac{|Z_{\rm dual} - Z_{\rm ...

7

In general, nonlinear optimization algorithms implemented in finite precision floating point software don't converge exactly to an optimal solution exactly satisfying the optimality conditions. Therefore, practical criteria are developed and implemented whereby the algorithm is terminated and optimality declared when the optimality conditions (or convergence)...

6

Disclaimer: One might want to look for a reformulation or a special structure to apply mathematical tools to find optimal in the feasible set. I am assuming you're already past the possibility that your problem case could be reformulated as a MILP/LP/QP etc. So, with the problem on hand, we're dealing a case where we cannot have a reformulation. Whatever I ...

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

Gaps are typically tied to specific models and solution methods. The gap reflects the difference between the best known bound and the objective value of the best solution produced by a particular algorithm. How that is computed depends in part on whether you are minimizing and maximizing, in part on whether you want the gap as a fraction of the best solution ...

4

The notation $C^1$ means $f'$ is continuous (on $\Bbb R$ as the interval is not stated). In general $C^k(a,b]$ means that all of $f',f'',\cdots,f^{(k)}$ are continuous on $(a,b]$. You are correct that radial unboundedness means that $f\to\infty$ as $\|x\|\to\infty$. This method is essentially that for Lyapunov stability. Ahmadi and Jungers (2018)1 proved ...

4

In addition to the reference of Mark, you can have a look at his technical report: Solving standard quadratic programming by cutting planes. by P. Bonami, A.Lodi, J. Schweiger, A. Tramontani Since the authors are involved with the development of CPLEX, I guess this paper is relevant to your question. Be aware that also Gurobi will soon have support for ...

3

I'm assuming the goal here is shortest (least total weight) path. As long as the "problem constraints" affect the graph only to the extent of causing arcs to exist or not exist, and as long as the graph contains no negative cycles (closed paths whose aggregate weight is negative), Dijskstra's algorithm will work fine. If all arcs go from lower to ...

3

When you call optimize without any options set, the default values will be used, and those are created by the function baronset.

3

A short little note about computing gaps just appeared in 4OR: Laporte, G., Toth, P. A gap in scientific reporting. 4OR-Q J Oper Res (2021). https://doi.org/10.1007/s10288-021-00483-0

3

In general, if the LP is bounded, the optimal set $M(b)$ is a face of the feasible set $P = \{ x | Ax = b, x \geq 0\}$ (which is a polyhedral set). In fact, $M$ is a function, but one that maps a vector $b \in \mathbb{R}^{m}$ to a set of points $M(b) \subseteq \mathbb{R}^{n}$. Thus, in order to talk about piece-wise linearity of $M$, you must define what you ...

2

As a student I am doing research in this field, I found Wikipedia's explanation very useful. You are right, most of the applications of MDO are in the field of design for aerospace and mechanical engineering (they may design product, not systems). In these fields, the reconciliation of different teams in the design process completely follows well-known ...

2

A non-convex QP is solved to global optimality by generating the McCormick relaxation of the objective and using that relaxation in a branch-and-bound framework. For non-convex MIQPs, we also introduce integer cuts during the branch-and-bound procedure (branch-and-cut).

1

In order to pin down a problem type, you will have to answer a number of questions about the application. How are you going to deal with the cost-time conflict? There are quite a few methods for dealing with multiple criteria, including taking a weighted sum, constraining one while optimizing the other (fastest turn-around within a budget, cheapest solution ...

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