Tag Info

17

I going to assume that the ratio $L(x)/Q(x)$ is nonnegative. If it can be negative, I think there may be a workaround, but this will complicated enough without dealing with that. I'm also going to assume that $Q(x)$ and $L(x)/Q(x)$ have a priori upper and lower bounds, say $\underline{Q} \le Q(x) \le \overline{Q}$ and $L(x)/Q(x) \in \{1,\dots,N\}$. You can ...

16

Option 1: Submit as is to a solver which can globally optimize MIQPs having non-convex objective, and which might reformulate to a linearized MILP model under the hood. Such solvers include CPLEX, Gurobi 9.x, and BARON, among others. Option 2: Step 1 Linearize the products of binary variables, per How to linearize the product of two binary variables? . <...

14

Here is a simpler symmetry-less formulation based on the one proposed by @RenaudM. For $i \le j$, let binary variable $r_{i,j}$ indicate that the bin represented by item $i$ contains item $j$. (Here, $r_{i,i}$ corresponds to $b_i$ in the other formulation.) For $i \le j < k$, let binary variable $t_{i,j,k}$ indicate that the bin represented by item $i$ ...

14

Maybe I am missing something but it looks like there is no need for a library: \begin{align} \sum_i \sum_j \sum_k x_{ji} y_{kj} cost(i,k)&=\sum_i \sum_j x_{ji} \sum_k y_{kj} cost(i,k) \end{align} Now since $\sum_k y_{kj}=1$, exactly one row is 1, the others zero. We pick the best one: $$=\sum_i \sum_j x_{ji} \max_k cost(i,k)$$ Since $\sum_j x_{ji}=1$ we ...

12

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

12

This is very related to the bin packing with conflicts problem (see eg. here), where you model the conflict as "soft" (with a binary variable to indicate violation, with a penalty in the objective function). The literature about this problem may contain a DP, too.

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

11

I suspect you want to minimize $\sum\limits_i \left[k_1\max(e_i,0)^2 + k_2\max(-e_i,0)^2\right]$. For instance, $a=0.5$ would correspond to $k_1 = 0.25$ and $k_2 = 2.25$). This can be formulated as a quadratic program by introducing new variables $u$ and $v$, using the objective $k_1 u^\top u + k_2 v^\top v$ with the constraints $u\geq 0, u \geq e, v\geq 0, ... 11 There are at least three more problem libraries that you can access. OR-Lib has instances of Quadratic Assignment/Knapsack/Minimum spanning tree that you can use. MINLP-Lib has several QP, BQP, IQP instances that you can filter by convexity. PrincetonLib chapter 2 problems. I think that you can apart of it come up with synthetic instances which are not ... 11 Rather than solving this directly as MIQCQP, you might consider linearizing the products$y_{ij} x_{ij}$, as shown here, yielding instead an MILP problem. 10 NEOS has a nice web page on nonlinear least squares. It contains several classic (i.e., not so new, but still good) references for nonlinear least squares. There is a very nice introduction to the mathematics of nonlinear least squares, and the algorithms to solve them, "Non-linear least squares problems: The Gauss-Newton method" by Niclas Börlin. There ... 9 Besides the traditional linearization suggested by @MarkL.Stone and @Richard, you might consider using the constraints to obtain a compact linearization. Explicitly, multiply both sides of your second constraint by$x_{j,i}$: $$\sum_k x_{j,i} y_{k,j} = x_{j,i}$$ Now replace$x_{j,i} y_{kj}$with$z_{i,j,k}$and impose an additional constraint to enforce$y_{...

9

Unless we can derive bounds during presolving, the standard way is to set a default variable range instead (e.g. $\pm1.e16$) so that we can generate the McCormick constraints. There are numerical & convergence issues to consider depending on the number that is chosen, so setting smaller bounds might be preferable if we are certain that it's safe from a ...

9

Yes, a real PSD matrix $M$ is a symmetric matrix with $$x^TMx\ge 0$$ for any $x$ (see e.g. https://en.wikipedia.org/wiki/Definite_matrix). However, this is not a real restriction. (We have two meanings of "real" here). We can form $$M' = \frac{M+M^T}{2}$$ Now $M'$ is symmetric and we have $$x^TM'x = x^TMx$$ for any $x$. So you can make $M$ ...

8

From a pure optimization point of view you can say that it is possible to transform a linear fractional problem into a linear one (see for example here). In your case, this seems not feasible, as you have a product of variables in the numerator. Nonlinear regression problems are usually solved by employing continuous optimization algorithms such as gradient ...

8

You can reformulate Quadratic Programs as Second Order Conic Programs (SOCPs). Therefore, you can use many conic benchmark libraries and filter SOCPs. For example, Conic Benchmark Library can be a good start!

8

If you are just looking for a formulation here is one (not particularly good due to symmetries, I'll rework it if I can think of something better in this regard). Let $K$ be an arbitrary upper bound on the minimum number of bins needed. Let $a_{i,k} \in [0,1]$ be a binary variable representing the assignment of object $x_i$ to bin $k$. Let $b_{i,j,k} \in [... 8 Kevin Dalmeijer's answer is correct for the general case. Since$A$is symmetric, there may be a method that involves fewer constraints. As suggested by Kevin's comment, I'm going to represent a typical equation with the simpler notation$x^T A x = 0$(mostly to save typing). A square matrix$A$may have a square root$B$, such that$BB=A$. In some cases, ... 8 The constraints $${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$$ can be rewritten as $$\sum_{i=1}^N \sum_{j=1}^N A(i,j) U(i,m)U(j,m)=0,m=1,2,\cdots,M.$$ Next, you can linearize each of the$U(i,m)U(j,m)$terms as explained here. 8 The factor of$\frac{1}{2}$is just for convenience, so that the Hessian of the objective does not have a factor of two. The argmin (optimal value of$\beta$) is the same, whether or not the factor$\frac{1}{2}$is included. Note that rather than$\frac{1}{2}$, some "authors" use$\frac{1}{2n}$, This also does not affect the argmin. 8 Fast resolution Let's start with speeding up the solution process. For the optimal solutions, all variables will be either inactive ($x_i = 0$) or, due to$\sum x_i = 1$, contribute equally to the gradient. So, for some$\gamma$, either:$x_i = 0$and$c_i \geq \gamma$or$c_i + 2\beta_i x_i = \gamma$In particular, the active variables will be the ones ... 8 Constraining a variable to be binary could be expressed as a quadratic constraint: $$x\in\{0,1\} \iff x(1-x)=0$$ This is often mentioned in non-convex QCQP articles to present non-convex QCQP is a somehow more general problem class. $$\{\mbox{MILP}\}\subset\{\mbox{non-convex QCQP}\}$$ There are some off-the-shelf non-convex QCQP (global) solvers, like ... 7 If$\bar{y} \in \mathbb{R}^n$is the point you are feeding, then assuming that you have verified that$\bar{y}$is feasible to your linear constraints to begin with, then try to find a direction$d$such that both$\bar{y}+d$and$\bar{y}-d$are feasible to your linear constraints. In other words, if the following problem has an optimum objective > 0, then ... 7 MOSEK can handle large-scale problems of a wide variety, including conic and Mixed-Integer programming problems. The Fusion API provided by MOSEK makes it straightforward to utilize the MOSEK solver in a structured manner. In the problem that you state, one can rephrase the quadratic objective function by introducing an auxiliary scalar variable$H$, as ... 6 You can use Singular Value Decomposition or Cholesky Decomposition. I recommend you read this Verification of Positive Definiteness. On page 9 there is an algorithm in MATLAB. 6 As the$h_i$are integers, you can reformulate your problem as a Mixed Integer Linear Program. Here's how: Let$c_i^m = \left(\frac{m}{n} - p_i\right)^2$denote the penalty that is received when assigning$m$items to group$i$. Now introduce binary decision variables$x_i^m$that are equal to 1 if$m$items are assigned to group$i$and 0 otherwise. As you ... 6 A recent paper by Quantum Computing Inc people is showing experiments on graph partitioning where QUBO approaches lead to better results than the state of the art. Here is the paper: https://arxiv.org/pdf/2006.15067.pdf Nevertheless, one can argue that this graph partitioning problem is not in essence what we can call a real-world OR problem. But it seems ... 6 You can model this with a binary variable$x_{i,j}$to indicate whether task$i$is assigned to worker$j$, and a binary variable$y_{i,j}$to indicate whether task$i$is the first task assigned to worker$j$in the current batch. The number of switches is then$\sum_{i\ge 2} \sum_j y_{i,j}$because this sum counts the number of times that any worker ... 6 I would suggest reading Numerical Optimization by Nocedal and Wright. It has a pretty neat chapter devoted to SQP methods. 6 There are two possibilities that come to mind, assuming that$x$is a continuous variable. One is to do a piecewise-linear approximation (leading to an answer that is, well, approximate). The other is to replace$x^2$with a new variable$z$and then, on the fly, add constraints of the form$z \ge x_0^2 + 2x_0(x-x_0)$when a solution is obtained containing$...

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