All Questions
Tagged with linearization quadratic-programming
20
questions
2
votes
1
answer
84
views
Is the linearization with first-order Taylor approximation correct?
I have a QP problem as
$\min \hspace{2mm} x^TQx-c^Tx$
here $x$ in binary
I want to transform it into a MILP by writing the objective function as
$\min \hspace{2mm} z-c^Tx$
and then adding a constraint
...
- 2,377
0
votes
0
answers
64
views
Is it possible to transform MIQP into MILP without introducing new variable?
I have a QP optimization problem in the form
$$\min {\bf x}^T{\bf Qx}-{\bf c}^T{\bf x}$$
here $\bf Q$ is a symmetric matrix.
$\bf x$ is the optimization variable, and it is binary.
Is there a way to ...
- 2,377
1
vote
1
answer
89
views
Linearizing a quadratic constraint
I am working on a quadratic conic optimization problem, but I have discovered that it would be preferable if the quadratic constraint is linearly approximated. In other words, I need some way to make ...
2
votes
1
answer
216
views
How to transform a binary QP into an MILP?
I have a binary quadratic problem with objective ${\bf{x}}^T{\bf{Qx}}+{\bf{c}}^T{\bf{x}}$
subject to
${\bf{A}}{\bf{x}}\le{\bf{b}}$
${\bf{A}}_{eq}{\bf{x}}={\bf{b}}_{eq}$.
here ${\bf{x}}$ is binary.
...
- 2,377
0
votes
0
answers
58
views
Better formulation of bilinear terms
I am working on an optimization problem where I need to formulate a constraint that represents the total sales value under specific conditions. The challenge lies in creating an expression that ...
- 23
3
votes
0
answers
124
views
From Quadratic to MILP?
I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP:
(QP) $\min c^T x + x^T Q ...
- 1,240
2
votes
1
answer
148
views
How to show that minimizing the epsilon-insensitive loss is equivalent to a quadratic program with inequality constraints?
This question is about an optimization problem that arises in support vector regression (SVR). Suppose you have $N$ pairs $(\vec{x}_n, y_n)$ as data and would like to find a vector of weights $\vec w \...
- 123
3
votes
0
answers
153
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[...
6
votes
2
answers
241
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$-...
- 179
2
votes
2
answers
243
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
272
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
4
votes
1
answer
370
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 ...
- 150
2
votes
1
answer
134
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\}$ ...
- 4,037
3
votes
1
answer
327
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,160
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