# 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.

12 questions
Filter by
Sorted by
Tagged with
100 views

### KKT conditions analysis for binary constraints

I am wondering if boolean constraints in a linear program can be solved (after linear relaxation from $x\in\{0,1\}$ to both $x\ge0$ and $x\le1$) using KKT analysis. Most of the algorithms that I have ...
121 views

### Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT

I am trying to convert a boolean LP to LP using LP relaxation by converting $x \in {0,1}$ to both $x \ge 0$ and $x \le 1$. Then to use it in my problem analysis, I am trying to build the KKT ...
135 views

### Two equivalent soft constraint implementations

Take the following optimization problem: \begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g(x)\le0\end{align} with $f$ and $g$ nonlinear functions. Suppose I want to relax the constraint by ...
110 views

129 views

### SDP relaxation with greater-than and less-than inequalities at the same time

I am dealing with the following nonconvex fractional quadratic optimization problem \begin{align} & \min_{\boldsymbol{x}} && \max_{t \in \mathcal{T}} \frac{\boldsymbol{a}_t^T \boldsymbol{...
177 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 ...
227 views

### Linearize a product of an integer variable (not just binary) and a continuous variable?

I have a constraint in my formulation that contains multiplication of an integer variable $y$ and a continuous variable $x$, which is $xy=q$ where $y$ is the number of units in which $q$ gets equally ...