Skip to main content
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 ...
prubin's user avatar
  • 39.3k
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, ...
Mark L. Stone's user avatar
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 ...
TheSimpliFire's user avatar
  • 5,412
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,...
RobPratt's user avatar
  • 32.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} ...
phil's user avatar
  • 141
14 votes

Do convex quadratic problems always have sparse solutions?

Consider the convex QP $$\min \lbrace \sum_{i=1}^n x_i^2 : x\in \mathbb{R}^n, \sum_{i=1}^n x_i = 1\rbrace.$$ The solution is $$x = (\frac{1}{n},\dots,\frac{1}{n}),$$which is fully dense.
prubin's user avatar
  • 39.3k
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 ...
Mark L. Stone's user avatar
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 ...
Marco Lübbecke's user avatar
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 ...
Johan Löfberg's user avatar
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 ...
David Bernal's user avatar
  • 1,075
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.
RobPratt's user avatar
  • 32.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 ...
Mark L. Stone's user avatar
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 ...
RobPratt's user avatar
  • 32.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 $\...
Mark L. Stone's user avatar
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 &...
Nikos Kazazakis's user avatar
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 ...
Erwin Kalvelagen's user avatar
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 ...
Richard's user avatar
  • 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 ...
Renaud M.'s user avatar
  • 2,418
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 ...
prubin's user avatar
  • 39.3k
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,...
Kevin Dalmeijer's user avatar
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 ...
JakobS's user avatar
  • 2,767
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 ...
independentvariable's user avatar
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.
fpacaud's user avatar
  • 1,511
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 ...
Ggouvine's user avatar
  • 1,877
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 ...
xd y's user avatar
  • 1,196
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/...
Hexaly's user avatar
  • 2,986
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$ ...
batwing's user avatar
  • 1,508
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 ...
Utkarsh Detha's user avatar
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 ...
prubin's user avatar
  • 39.3k
7 votes

Do convex quadratic problems always have sparse solutions?

Not in general. In quadratic programming (and in nonlinear programming, more general), we have basic, non-basic and super-basic variables. These superbasics can be interpreted as non-basic but between ...
Erwin Kalvelagen's user avatar

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