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

9 questions
Filter by
Sorted by
Tagged with
32 views

### difference between lower bounds and upper bounds for an optimization problem [closed]

What is the exact definition of a lower and an upper bound for an optimization problem in general like routing and scheduling? What are the most known methods for generating tight lower bounds? and ...
98 views

### Relaxation and complexity of two formulations

I have two different MILP formulations for the same scheduling problem with the same complexity but with different running times. Why it is recommended to compare the relaxed versions of each ...
47 views

### how to convert type of variable in CPLEX

I have an Integer Linear Problem which is solved quickly when I change my variable type to double. now I'm developing a fix and relax algorithm and I used conversion to change data type which takes a ...
135 views

### What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

Say that I have a binary IP $$z=\max_x \{c^\top x: Ax=b, x\in B^n\}$$ where $B^n$ is the set of $n$-dimensional $0-1$ vectors. Its LP relaxation will be z^{LP}=\max_x \{c^\top x: Ax=b, 0\leq x\leq 1\...
117 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{...
91 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 ...
161 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 ...