Questions tagged [quadratic-programming]
For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).
92
questions
1
vote
1
answer
97
views
Solver for quadratically constrained mixed-integer linear programs
I have an optimization problem with vectors $x$, $y$, and $z$, where $x$ is an integer vector. My objective function is linear (i.e. $\|y\|_1$), but one of my constraints is quadratic ($x^Ty \leq z$). ...
- 141
5
votes
2
answers
241
views
Simple OLS problem can only be solved in SCS. Is the dual infeasible?
Essentially, I am trying to solve a simple orthogonal least-squares (OLS) problem with some constraints — the coefficients must sum to $1$, no coefficient can be less than $0$, and no coefficient can ...
3
votes
1
answer
102
views
How do I pass an objective bound to Gurobi?
I have a non-convex Quadratic Programming over unite simplex set. I have a valid lower bound on the objective function (goal is minimization problem).
If I add a constraint like
$$f(x)\geq lower~bound,...
-2
votes
1
answer
54
views
Converting a quadratic objective function in piecewise linear function
The objective function is of the form:
$max$ $x^2/2+y^2/2+z^2/2$
I would like to convert it to piecewise linear function. How do I achieve that?
- 1
1
vote
1
answer
93
views
How to model and solve such a 0-1 programming problem
My problem is described in this picture(It's like a Pyramid structure):
The objective function is below: $$\min\sum_{k=1}^\ell\sum_{i=0}^{2^k-1}\sum_{j=0}^{2^k-1}\left(A_{i,j}^k-A_{i,j+1}^k\cdot\frac{...
- 63
3
votes
2
answers
760
views
Is solving a quadratic programming optimization problem using python slower than C++？
I am using the cvxpy library in python to solve a quadratic programming problem and the solver used is scip. I found that when the amount of data becomes large, the solution process will be ...
- 63
1
vote
1
answer
141
views
MIQP — CVXPY unable to treat summation of variables as a variable
I have a quadratic integer programming assignment problem. The goal is to assign riders seats on a bus such that distance between any two riders is maximized; however, the importance of each objective ...
- 471
3
votes
0
answers
79
views
Linearize objective function with non-linear terms
I have a problem with linear constraints but in the objective function I want to have some linear terms along with a $x^2$ term. So it is like the following:
$$\min \sum \limits _i \sum \limits _j (a[...
1
vote
2
answers
178
views
How to solve this mixed integer quadratic program using cvxpy or other method?
My problem is described in this picture:
$$
\begin{array}{l}
\left\{\begin{array}{l}
\text { objective function: } \\
f = \min \sum_\limits{l=1}^2 \sum_\limits{i=0}^{2^l-1} \sum_\limits{j=0}^{2^l-2}\...
- 63
2
votes
1
answer
157
views
Poorly conditioned quadratic programming with "simple" linear constraints
I have many quadratic programming problems of the following form:
$$\min_{x\in\mathbb{R}^n} { \tfrac{1}{2} {\lVert Cx-d \rVert}^2} $$
$$\textrm{s.t.}\ x_1\le 0,\ x_n\le 0,\ x_n\le a_1^\top x_{1:n-1},\ ...
- 235
3
votes
2
answers
252
views
How to view pause and view current solution in CPLEX Optimization Studio?
I am solving my first model in CPLEX 22.1. I have setup a quadratic MIP with 100 variables and the model has been running for a day already with the best integer and best bound solutions barely ...
- 63
4
votes
0
answers
101
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
396
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 ...
- 573
1
vote
0
answers
65
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,928
6
votes
2
answers
163
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
223
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$ ...
- 235
2
votes
2
answers
179
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,...
- 147
1
vote
0
answers
153
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 ...
- 147
1
vote
0
answers
58
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}...
- 423
5
votes
3
answers
143
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
362
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
152
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
300
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
114
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 ...
- 2,043
3
votes
1
answer
67
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
219
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
303
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
104
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,928
3
votes
0
answers
88
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 = ...
7
votes
1
answer
875
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 ...
- 73
3
votes
1
answer
73
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
125
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
78
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
156
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
338
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
135
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
271
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
153
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
137
views
Optimization Multiple Constraints
I am trying to solve a linear algebra problem: an optimization problem and I am using CVXOPT. I've split the problem into 3 components
In its simplest form, The general formulation for CVXOPT is \...
- 173
2
votes
1
answer
82
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_{...
- 235
3
votes
1
answer
196
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
800
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 ...
- 235
1
vote
0
answers
182
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
553
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,954
5
votes
1
answer
385
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 ...
- 235
4
votes
1
answer
302
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
312
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
124
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
87
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