17
votes
Accepted
Divisibility constraints in integer programming
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 ...
- 37.8k
16
votes
Nonlinear integer (0/1) programming solver
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, ...
- 13.1k
15
votes
What is quadratization?
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,341
14
votes
Accepted
Bin Packing with Relational Penalization
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,...
- 30.3k
14
votes
Nonlinear integer (0/1) programming solver
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}
...
- 141
13
votes
Accepted
CPLEX non-convex Quadratic Programming algorithms
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 ...
- 13.1k
12
votes
Bin Packing with Relational Penalization
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 ...
- 5,909
11
votes
How can I model regression with an asymmetric loss function?
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 ...
- 1,702
11
votes
Where can I find test instances for convex quadratic programming?
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 ...
- 1,065
11
votes
Accepted
Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only
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.
- 30.3k
10
votes
Accepted
How to model nonlinear regression?
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 ...
- 13.1k
10
votes
Nonlinear integer (0/1) programming solver
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 ...
- 30.3k
9
votes
Why is there a constant in the objective function of the *best subset selection problem*?
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 $\...
- 13.1k
9
votes
Accepted
How do Quadratic Programming solvers handle variables without bounds?
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 &...
- 11.9k
9
votes
Accepted
Non-symmetric Positive Definite/Semidefinite Matrix in Quadratic Program
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 ...
- 2,585
9
votes
Accepted
Sensitivity analysis of QP
The sensitivity analysis of optimization problems is called parametric programming or sometimes "post-optimal analysis".
The short version is that you describe the variability of your ...
- 3,459
8
votes
Bin Packing with Relational Penalization
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 ...
- 2,398
8
votes
How can I linearize or convexify this binary quadratic optimization problem?
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 ...
- 37.8k
8
votes
Accepted
How can I linearize or convexify this binary quadratic optimization problem?
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,...
- 6,063
8
votes
How to model nonlinear regression?
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 ...
- 2,737
8
votes
Where can I find test instances for convex quadratic programming?
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 ...
- 3,980
8
votes
Accepted
Sequential quadratic programming source
I would suggest reading Numerical Optimization by Nocedal and Wright. It has a pretty neat chapter devoted to SQP methods.
- 1,471
8
votes
Accepted
Efficient way to solve "easy" quadratic optimization problem
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 ...
- 1,842
8
votes
Accepted
Bilinear programming vs Mixed integer linear programming performance comparison
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 ...
- 1,036
7
votes
Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?
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/...
- 2,925
7
votes
Accepted
Quadratic programming using CPLEX: how to check whether candidate is an extreme point?
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$ ...
- 1,458
7
votes
Integer programming problem with simple quadratic objective function in Python
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 ...
- 141
7
votes
Accepted
Randomly constructing a bounded ellipsoid
As noted in a comment to the original question, I have (I believe) a proof that the ellipsoid is bounded with probability 1 (assuming the pseudorandom number generator is, well, random). I've also ...
- 37.8k
6
votes
Integer programming problem with simple quadratic objective function in Python
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 ...
- 2,305
6
votes
Accepted
Convexity of a QP
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.
- 676
Only top scored, non community-wiki answers of a minimum length are eligible