Questions tagged [quadratic-programming]

For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).

Filter by
Sorted by
Tagged with
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$). ...
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 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 ...
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 ...
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. ...
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$-...
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_{...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 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: $$...
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 ...
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 ...
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_{...
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 ...
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 ...
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 ...
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 ...
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 ...