Questions tagged [quadratic-programming]
For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).
73
questions
5
votes
3
answers
129
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
151
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 ...
- 171
5
votes
1
answer
87
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
160
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
58
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
61
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
136
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
231
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
84
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,369
3
votes
0
answers
62
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
556
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
64
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
82
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
73
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
110
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:
$$...
- 543
7
votes
1
answer
189
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
4
votes
1
answer
112
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 ...
- 543
8
votes
2
answers
215
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 ...
- 543
4
votes
1
answer
129
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
112
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
443
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
97
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
494
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,357
5
votes
1
answer
295
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
230
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
224
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
121
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
76
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 ...
- 191
1
vote
1
answer
163
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 ...
- 191
5
votes
2
answers
179
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,246
3
votes
2
answers
114
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
227
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,105
2
votes
0
answers
75
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
981
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,467
5
votes
2
answers
210
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
108
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
65
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,467
4
votes
1
answer
123
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
89
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,171
2
votes
0
answers
60
views
Determine set of "arbitrage-free" regional prices
I am seeking for a way how to determine set of "arbitrage-free" regional prices for a single commodity market.
There are $N>1$ production units with costs $C^{prod}_i, i=1,\dots,N$ and ...
- 21
5
votes
1
answer
198
views
PAVA-like solution to simple QP
Let $l,u\in\mathbb{R}^n$, and consider the QP:
$$\min_{l\le x\le u} {(\Delta x)^\top (\Delta x)}$$
where $\Delta x=[x_2-x_1,\,x_3-x_2,\,\dots,\,x_n-x_{n-1}]^\top$.
I.e. we want to minimize the squared ...
- 215
2
votes
3
answers
381
views
Why can quadratic functions over polyhedrons be minimized exactly in finite time?
I have heard it said that QP problems
$$\min f(x) = \frac 12 x^TAx + b^T x$$
$$x \in P$$
where $A$ is a symmetric matrix and $P$ is a polyhedron can all be solved exactly and in finite time (or it can ...
- 593
2
votes
0
answers
98
views
Indicator function for integer variable with inequality constraint
I have $n$ integer variables $\vec{x}$ with the following integer programming problem.
$$
COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0)
$$
Here, $a_i, b_j \in \mathbb{R}_+$ ...
- 201
6
votes
0
answers
113
views
Cases where RLT/SDP relaxation does not work well with standard quadratic optimization
(For people who don't know what RLT is): I am maximizing an indefinite quadratic function over a standard simplex, i.e., the standard quadratic optimization problem. A well-known approach is to relax ...
- 3,776
10
votes
6
answers
2k
views
Nonlinear integer (0/1) programming solver
I have the following optimisation problem.\begin{align}\max&\quad\sum_i\sum_j\sum_k x_{ji}y_{kj} \operatorname{cost}(i,k)\\\text{s.t.}&\quad\sum_j x_{ji}=1\quad\forall i\\&\quad\sum_k y_{...
- 109
5
votes
2
answers
362
views
How to linearize a quadratic constraint to add it then via a callback function
Suppose we have a positive continuous variables $0 \le x \le UB$ where $UB$ is a known upper bound.
How can we linearize the term $x^2$?
Detailled problem:
Suppose that via a callback we compute a ...
8
votes
2
answers
133
views
(Iterative?) Solutions to a certain quadratic program with non-convex constraints
Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$
I would like to efficiently solve the following problem:
Problem 1
Choose $\alpha,z\in\mathbb{R}^m,\beta\...
- 215