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

18 questions
Filter by
Sorted by
Tagged with
99 views

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

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

733 views

### Solving a MIP by Relaxation

I have tried to understand the method of relaxing an integer program. I am in the process of implementing and solving a MIP for the FJSSP. For this I use the python-MIP package to solve it. From my ...
274 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 ...
218 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 ...
159 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 ...
189 views

146 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{...
686 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 ...
219 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 ...