Questions tagged [quadratic-programming]
For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).
81
questions
4
votes
0
answers
64
views
Analytical solution of constrained quadratic program
I'm trying to solve a "simple" (= small) optimization problem often, with only minor changes to the objective function. Therefore it's important to keep the "time per solve" as low ...
- 41
4
votes
1
answer
381
views
Is this a non-linear integer model?
Let's say if I have two decision variables, $f$ and $g$ respectively, where $f$ is continuous, and $g$ is binary.
If I have a constraint like this,
$$ f\cdot g \le C$$
Does this make my model ...
- 513
1
vote
0
answers
57
views
Does Gurobi solve QCQMIPs with Quadratic terms faster with then Bi-Linear terms in general?
Based on the color distance function defined here i try to find $n$ RGB colors with large inter set color distances and good color distance to white.
...
- 3,898
6
votes
2
answers
142
views
When should we avoid linearizing a quadratic term?
Some solvers like Gurobi can handle mixed-integer quadratically-constrained quadratic models regardless of their nonconvexity. I have some experience that Gurobi can handle instances of the max $k$-...
- 169
10
votes
1
answer
127
views
Sensitivity analysis of QP
Given a quadratic program
$$
f^* \equiv x^\top Q x + b^\top x \\
x \geq 0 \\
A^\top x = d \\
x \in \mathbb{R}^n
$$
I would like to analyze the sensitivity of the solution $x^*$ to perturbations in $Q$ ...
- 203
2
votes
2
answers
153
views
Difference between constraint formulation and performance
I am wondering about the characteristics and performance of some constraints with only binary variables. I assume that solving (integer) linear programs is faster than quadratic ones.
At first:
$$
a,b,...
- 85
1
vote
0
answers
98
views
Converting quadratic constrains to linear constraint [closed]
I try to convert a quadratic constraint to a linear one:
$$
w_j = \sum w_\text{j,i} \\
w_\text{j,i} = \frac{w_j}{D} \times u \\
w_j,D,u \in \mathbb{N} \\
$$
The values for $w_j$ and $D$ are constant ...
- 85
1
vote
0
answers
47
views
Dual of a quadratic constraint
This is my model.
\begin{align}
\min_x&\quad\sum_{e\in E} X_e p_e \\
\text{s.t.}&\quad\sum_{e \in E: T(e)=i} X_e - \sum_{e \in E: H(e)=i} X_e = \begin{cases}1, \;\text{if}\;i=s\\-1,\;\text{if}...
- 403
5
votes
3
answers
137
views
What is the go-to practical method for optimizing separable quadratic programs?
I have a quadratic program that looks like this:
For fixed vector $b$, and matrices $A_1, ..., A_n$, Find column vectors $x_1, ..., x_n$ that minimize $\sum_{i=1}^n x_i ^T 1 1^T x_i$ subject to $\sum_{...
- 151
2
votes
1
answer
251
views
Can docplex solve a mixed integer quadratic programming (MIQP) problem?
I am trying to solve a mixed integer quadratic programming (MIQP) problem.
The objective function contains the product of two continuous decision variables, some of constraints are non-linear too. I ...
- 307
5
votes
1
answer
115
views
How to handle a non-separable bilinear objective function in the special case of decoupled constraints?
I have a large number of (10000+) non-negative, real decision variables $x_i$ and $y_j$.
Let $I$ and $J$ be the index sets associated with $x$ and $y$, respectively.
Let $\bar{I}$ and $\bar{J}$ be non-...
- 135
5
votes
1
answer
216
views
How to handle a bilinear objective function in the special case of decoupled constraints?
I have decision variables $x_i$ and $y_j$, real positive variables.
I would like to minimize objective function
\begin{aligned}
\min \quad & \sum_{ij} x_iy_j \\
\end{aligned}
All constraints are ...
- 135
3
votes
1
answer
73
views
Translate standard weighted least square regression to quadratic programming
Sorry if this is really easy for you gurus. I'm trying to derive the reformulation of a weighted least square regression to a quadratic programming form. I understand there is a closed form solution ...
- 129
11
votes
5
answers
3k
views
A Stack Overflow user's curious problem of maximising unsortedness
User ddofborg posted on Stack Overflow a programming question which hides a combinatorial optimisation problem.
The idea is the following: given a list of URLs with their respective domain names, he ...
- 1,993
3
votes
1
answer
62
views
Maximizing the number of nonnegative coordinates of $Wx$
I want to find good incumbent solutions to the following problem:
$\newcommand{\RR}{\mathbb{R}}$
$\newcommand{\norm}[1]{\left\Vert#1\right\Vert}$
Given a matrix $W \in \RR^{m \times n}$, find the ...
- 133
4
votes
1
answer
156
views
Can you calculate the mean of some MIP variables using linear constraints?
got a lingering question from a graduate course in integer programming that's been bugging me ever since.
Is it possible to find the mean of some variables in a MIP without resorting to quadratic ...
- 138
2
votes
1
answer
268
views
CPLEX solver for quadratic problems with barrier algorithm
I'm writing a convex minimization model with a quadratic objective function and linear constraints in C#.
I set CPLEX to solve the problem with the barrier algorithm. The interesting thing is when I ...
- 45
2
votes
1
answer
93
views
Linearize product of $x\cdot y \text{ with } x,y \in \{-1,0,1\}$ for MILP
I have a problem where I have many products between variables drawn out of $\{-1,0,1\}$. Could you suggest a linearization in terms of variables in $\{-1,0,1\}$ or $B_1 - B_2$ where $B_i \in \{0,1\}$ ...
- 3,898
3
votes
0
answers
72
views
Automatic quadratization of constraints in pyomo for gurobi
Gurobi 9 can solve QCQPs, and QCQPs capture all of polynomial optimization by the obvious trick that e.g. a cubic term $x_1 x_2 x_3$ can be turned into a quadratic term $y x_3$ and a constraint $y = ...
6
votes
1
answer
671
views
Is there any open source quadratic programming solver with C# API
I have a quadratic programming model (i.e., quadratic objective function and linear constraint) and, I want to solve it on an open-source solver. Since our project developed on C#, we also would like ...
- 63
3
votes
1
answer
65
views
optimizing quadratic form over bounded polytope
As a followup to this question, I am looking for references for the problem of maximizing $x^TQx$, where $Q$ is positive definite, subject to linear equality and inequality constraints bounding all ...
- 31
2
votes
2
answers
105
views
How to use `cplexAPI` to solve quadratic programs/quadratically constrained linear programs?
I am trying to use cplexAPI to solve quadratic programs or quadratically constrained linear program.
While it seems to be pretty straightforward to use ...
- 21
2
votes
1
answer
74
views
Convex function subject to $0\le x_1\le \ldots \le x_n\le 1$ and linear constraint
I am maximizing a convex function (a positive definite quadratic form, if it makes a difference) subject to $0\le x_1\le \ldots \le x_n\le 1$ and a linear constraint $a^\top x+b=0$. Can I conclude ...
- 23
4
votes
1
answer
125
views
Continuous minimax with linear objective and constraints
How to solve the following minimax problem quickly? The variables are all continuous.
$$\max_{x_{1}, x_{4}, x_{5}} \min_{x_2,x_3} \vec{c}^{\intercal} \vec{x}$$
subject to the following constraints:
$$...
- 523
7
votes
1
answer
243
views
Bilinear programming vs Mixed integer linear programming performance comparison
I know that both bilinear programming and mixed integer linear programming are NP-hard. But is there a preference to have when choosing an approach to solve a problem that can be represented in both, ...
- 173
3
votes
1
answer
121
views
How to exponentiate binary variables in QUBO-type problems?
Ising Model
In an Ising model, the Hamiltonian of one configuration of spins $\vec{s}$ is:
$$ H(\vec{s}, \mathcal{J}, \mathcal{h}) = \sum_{i} h_{i} s_{i} + \sum_{i \ne j}J_{ij} s_{i}s_{j} $$
where ...
- 523
7
votes
2
answers
230
views
Inverse Ising problem
Inverse Ising Problem
The inverse ising problem means fitting the coupling $J_{ij}$ and field $h_{i}$ parameters given a sample of configurations of spins.
Each spin $s_{i}$ is either +1 or -1. The ...
- 523
4
votes
1
answer
136
views
How do I formulate constraints that check if a parameter is between certain values, using binary variables?
I have $3$ parameters $a_1,a_2,a_3$ and a variable $d$ and $3$ binary variables $b_1,b_2,b_3$ and a "result" variable $s$. How do I model constraints so that:
If $d$ is between $0$ and $a_1$...
- 43
1
vote
0
answers
80
views
Optimisation Multiple Constraints
I am trying to solve a linear algebra problem: an optimisation problem and I am using CVXOPT. I've split the problem into 3 components
In its simplest form, The general formulation for CVXOPT is \...
- 73
2
votes
1
answer
73
views
Subtracting Values from a Positive semidefinite Matrix in a Semidefinite Program
I'm trying to construct an SDP relaxation for a non-convex quadratic program ($x^{\intercal}\mathbf{H}x$) with the following objective function:
\begin{equation}
x_{11}y_{11} + x_{12}y_{12} + x_{21}y_{...
- 207
3
votes
1
answer
164
views
How do I arrive at the form given in this paper, for the QUBO version of the number partitioning problem?
In this article A new modeling and solution approach for the number partitioning problem1, it transforms the number partition problem into a QUBO form like equation (2.1) on page 2. $$\text{diff}=\...
3
votes
1
answer
589
views
Non-symmetric Positive Definite/Semidefinite Matrix in Quadratic Program
A necessary condition in any quadratic programming to be convex is the matrix $\mathbf{Q}$ in the formulation $x^\intercal \mathbf{Q}x$ to be positive definite or positive semidefinite. Positive ...
- 207
1
vote
0
answers
125
views
Solver issue? Xpress (slp) - Nonlinear - Python - Pyomo
I tried solving my model with xpress:
pip install xpress
And then in the model:
...
- 111
11
votes
1
answer
510
views
Efficient way to solve "easy" quadratic optimization problem
The linear program
\begin{align}
\min &\sum_{i=1}^nc_{i}x_{i}\\\
\mbox{s.t.:}&\sum_{i=1}^nx_{i}=1,\\\
&x_{i}\geq 0,&&\forall i=1,\dots,n
\end{align}
has a trivial optimal solution ...
- 5,543
5
votes
1
answer
325
views
Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only
I'm totally new to the world of optimization and I have an optimization problem that I think it can be formulated as Mixed Integer Quadratically Constrained Quadratic Program (QCQP) but I'm not sure ...
- 207
4
votes
1
answer
257
views
Why are the bounds 3 and 6 instead of 7, in this binary expansion of a slack variable in this QUBO problem?
I've recently started to study how to formulate optimization problems as QUBO models through this paper/tutorial: https://arxiv.org/pdf/1811.11538.pdf
One of the steps is to transform the inequalities ...
5
votes
1
answer
269
views
Solver Recommendation : Discrete Variables and Quadratic Constraints
I would like some solver recommendations to solve a problem with boolean/integer variables, mostly linear constraints but also some quadratic constraints. I also have an objective to minimize which is ...
- 65
6
votes
0
answers
122
views
Water quality component optimization
I have an optimization problem that I'm attempting to tackle. As you can see in the image below, there's a graph network through which water flows. I've drawn out the problem in the image to explain ...
- 61
1
vote
1
answer
81
views
Integral of PWL-Constraint in Gurobi (Java)
In my optimization model, I use piecewise-linear constraints with the output of $y[m]$. The question or problem I have now is whether there is a way in Gurobi (Java) to form the integral for this PWL ...
- 291
1
vote
1
answer
199
views
Method (Algorithm) and Objective used in Gurobi Model
How can I find out which method or algorithm was used to solve my model? When I use GRB.IntParam.Method- to output the method, I get ...
- 291
5
votes
2
answers
280
views
MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?
I missed the opportunity to ask this on OR.SE by 24 days! I asked it at CS.SE on 6 May 2019 and OR.SE entered Private Beta on 30 May 2019.
It's a problem about minimizing a sum of terms that are ...
- 1,256
3
votes
2
answers
121
views
Implementing NLP as QP on docplex
I wanna learn how to solve non-linear programs using the docplex library. according to this link
I should be able to run the model as a QP. But when running the model I got the error: ...
- 75
3
votes
1
answer
255
views
Linearizing a quadratic function with more variables or not in Gurobi?
Suppose I want to set the price $0 \le p_t \le p_{max} $ and based on the price, demand is determined $D_t(p_t)=a-bp_t$. Inventory level at each time is denoted by $I_t$ and it is determined by $I_t= ...
- 2,083
2
votes
0
answers
82
views
Is this semidefinite constraint in fact pointless?
On Wikipedia, I encountered a statement that the semidefinite relaxation of a quadratically constrained quadratic program can be solved more efficiently (using only LP) in the case that no variable is ...
- 201
7
votes
3
answers
999
views
How do Quadratic Programming solvers handle variables without bounds?
Solvers for non-convex QPs generally do the McCormick relaxation of the term $xy=z$ and then do spatial branch and bound.
This requires that $x$ and $y$ have given bounds, how do they handle the case ...
- 3,507
5
votes
2
answers
228
views
Piecewise linear and global optimization
I am new to OR, and apologies if my mathematical notation is not clear. I have tried my best to keep it concise and given an explanation with numerical data.
I would like to understand:
Can this ...
- 81
2
votes
1
answer
117
views
Minimizing a quadratic binary nonconvex function by CPLEX
I am using CPLEX 12.8 to minimize a quadratic binary nonconvex function, according to quadratic function by CPLEX.
In particular, my function is the following:
$$ \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{...
2
votes
1
answer
67
views
Non RLT-Cutting planes for nonconvex QPs?
Consider a general nonconvex QP $x^\top Qx$. This can be linearized in an extended space by using the variable $Y=xx^\top$.
Now a valid inequality $a^\top x \le b$ can be strengthend by the RLT ...
- 3,507
4
votes
1
answer
126
views
Linear objective function with power term in constraint
Given $n$ variables $x_{i}$ where $i\in [0,n)$, denoted as a vector $x$, given a linear objective function that we want to minimize $c^\top x$ with 2 constraints:
$\sum x_{i}^{2} < n+1$
$\sum\log(...
- 171
2
votes
0
answers
106
views
How to linearize this multiplicative constraint?
I have a constraint in the form
$\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$
Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable).
$x$ and $\zeta$ are also optimization ...
- 2,209