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.

Filter by
Sorted by
Tagged with
21
votes
5answers
345 views

Tightness of an LP relaxation without using objective function

How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and ...
7
votes
3answers
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 ...
7
votes
2answers
614 views

The general meaning of "constraint relaxation" in the context of the Shortest Path Problem

I've read that in the context of the Shortest Path Problem, the use of the term "relaxation" ("relaxing edges") [...][the use of the term "relaxation"] is historical. The outcome of a relaxation ...
6
votes
1answer
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 ...
5
votes
2answers
212 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\...
5
votes
1answer
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 ...
3
votes
2answers
111 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 ...
3
votes
1answer
110 views

"Rank 1" type constraint $X=vw^\top$: MILP representation? Convex relaxation? Other tractable approach?

Suppose $X\in\mathbb{R}^{m\times n}$, $v\in\mathbb{R}^m$, $w\in\mathbb{R}^n$ are variables from an optimization problem, which also includes the constraints: $$0\le v\le a$$ $$0\le w\le 1$$ $$w_1+\...
3
votes
1answer
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 ...
3
votes
0answers
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{...
2
votes
1answer
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 ...
2
votes
0answers
57 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 ...