# Questions tagged [relaxation]

For questions related to optimization problems that are obtained from other optimization problems by increasing the feasible region, typically by removing one or more constraints or changing their right-hand sides.

22 questions
Filter by
Sorted by
Tagged with
31 views

### On Linear Relaxation of Convex Quadratic Maximization over Linear Constraints

Consider the following QP problem, where the matrix $Q$ is positive definite: \begin{align*} \max_{x} \quad & x^\top Qx + c^\top x \\ \text{s.t.} \quad & Ax \geq b, \\ & ...
1 vote
77 views

### On Linear Relaxation of Standard Quadratic Programming

Consider the following StQO problem where matrix $Q$ is indefinite: \begin{align*} \text{minimize} \quad & x^\top Qx \\ \text{subject to} \quad & e^\top x = 1, \\ & ...
89 views

### Optimization under cardinality constraint

When we consider the following optimization problem: \label{P}\tag{P} \begin{array}{ll} \displaystyle\min_{x \in \mathbb{R}^n} & f(x) \\ \text{s.t.} & Ax = b,~ x \geq 0, \\ &...
94 views

### Why this ILP and LP are equivalent?

Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
1 vote
69 views

### Strong relaxations for binary variables

Having the following optimization problem that models $\sum_i\min(c_i, C)$: $$\min_{\mathbf{Y},\,\,\{x_i\}_i} \sum_i^{n} c_ix_i + C(1-x_i)$$ and where $C$ is a positive constant, each $x_i$ is a ...
• 11
182 views

### How can I relax the equality constraint in this problem?

Consider the following problem \begin{aligned} \min_{x,y} \quad & f(x,y), \\ \textrm{s.t.} \quad & \exp(x) + \exp(y) = 1 \end{aligned} \tag{1} \end{...
• 639
170 views

225 views

### Ways to strengthen QCQP relaxations

I was wondering what types of methods can be used to strengthen QCQP relaxations. Our solver has all the standard stuff, like constraint propagation, presolving, etc., but some QCQP problems seem to ...
• 12.2k