# Questions tagged [relaxations]

A relaxation of a problem is a related problem whose solution is easier in some sense to find, while providing useful information about the solution to the original problem. One common form is a linear relaxation.

84 questions
Filter by
Sorted by
Tagged with
26 views

1 vote
15 views

### optimal ratio of maximum coverage problem with LP relaxation

Consider Maximum-Coverage problem, which means there are set $A$ and $n$ subsets of $A$, we can choose $k$ subsets to cover some elements, and Maximum-Coverage is the assignment that cover most ...
1 vote
45 views

### Restore shuffled function output

There is a function $\mathbf{y} = f(\mathbf{x})$ that takes a vector $\mathbf{x}$ as input and outputs another vector $\mathbf{y}$. The function $f(\mathbf{x})$ is continuous and differentiable. I can ...
1 vote
72 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 ...
151 views

1 vote
336 views

### How to approximate a rank-1 solution after exploiting semidefinite relaxation method?

For my problem, I try to optimize the vector $\mathbf{w}\in\mathbb{C}^{N}$ at first. After exploiting semidefinite relaxation (SDR) method, the variable becomes $\mathbf{W} = \mathbf{ww}^H$ and the ...
• 353
190 views

• 135
25 views

### Understanding the term upper bound?

I am trying to understand the meaning or intuition of upper bound in the following sentence: The relaxed problem is upper bound of the original problem. Any help in this regard will be highly ...
• 71
67 views

### Conversion of SDP relaxation of Travelling Salesman Problem (TSP) to standard SDP form

The standard SDP formulation is given as : \begin{aligned} \min_{X\in H^{n}} \quad& \langle X,M_{0} \rangle\\ \textrm{s.t.} \quad& l_{s} \leq \langle X, M_{s} \rangle \leq ...
1 vote
103 views

### Can I reformulate the given SDP such that the main constraint becomes and LMI?

I am new to SDP and LMI's and trying to solve an optimization problem of the following form: \begin{aligned} \text{maximize} \quad & \sum_{j=1}^k w_j\\ \text{subject to} \quad &...
1 vote
81 views

### How to maximize quadratic form with a integer variables or its relaxation

Let $A$ be a positive semidefinite matrix. Also, let $\forall i\in [1,n], x_i \in \{-1,1\}$. And finally, for some of indices $I\subset \{1,\ldots,n\}$, values of $x_i\in \{-1,1\}$ are known. ...
• 865
38 views

### Name for integrality relaxation in BQP problems

Given a binary quadratic program, what is the name for the relaxation where the binary constraints are relaxed to $[0,1]$ box constraints? For LPs this is normally called LP-Relaxation. However, since ...
• 85
46 views

### Does this relaxation have a name?

Imagine you have e.g. the following optimization objective over a joint $D$-dimensional real-valued space, i.e. $x^* = \min_{x} f(x), \quad x \in \mathbb{R}^D$ And then you have the following ...
• 139
242 views

### Why $x^TAx=\text{Tr}(AX)$?

In many optimization resources, when we reformulate an LP to an SDP, we sometimes use the fact that \begin{equation*} x^{T}Ax = Tr(AX), \end{equation*} where $X=xx^T$ is a number. But when I tried to ...
• 817
1 vote
180 views

### Is Lagrangian relaxation convexity optimization problem or not?

We know that for a regular maximization LP problem, it should be $$z^* = \max_x c^Tx \ s.t. x \in X, Ax \leq b$$ where $b \in \mathbb{R}^m$. There is a technique called Lagrangian relaxation, which ...
• 133
23 views

### Are there continuous relaxations of the notion of function composition (e.g. for automorphisms)?

An automorphism can be applied any integer number of times. Is there a sensible notion of applying it a non-integer number of times? I have the same question for more general types of transformations....
• 1,275
1 vote
28 views

### Relaxation of Chance Constraints Proof

I'm dealing with the following chance constraint $$\mathbb{P}(\|Ax\|_2 \leq c^\intercal x) \geq 1 - \delta,$$ where $x \sim \mathcal{N}(\mu,\Sigma)$ and $\delta \in (0, 0.5]$. Since $x$ follows a ...
1 vote
407 views

### How to iteratively solve Poisson's Equation with no boundary conditions?

I'm working to reimplement the results of this fantastic paper which allows you to design your own caustics. On the top left corner of page 3 there are three images: A blue and red "difference ...
• 113
1 vote
136 views

111 views

### Formulation for IP of large OR statement which gives a good linear relaxation

Let $N$ be a very large number. I want a good way to program that $x$ should be one if and only if one of $x_i$ is equal to one.We can write the following Integer Programming problem: \begin{align*} \...
• 1,135
351 views

### Is there a second-order conic relaxation method for the bilinear term $z=xy$? [closed]

I hope to find a second-order conic (SOC) relaxation for $z = xy$, but it seems very hard.
• 53
1 vote
30 views

### Relaxation of the set given by knapsack constraints

A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$. I have a set of points defined as  \mathcal{X} = \{x \in \mathcal{Z}^n_{+}: w^{\top}x \...
• 1,552
985 views

### Subgradient procedure for lagrangian relaxation of GAP

I'm trying to solve the general assignment problem by relaxing the capacity constraint and applying the subgradient procedure. GAP (from here): Relaxation (same source as above): Subgradient method ...
• 123
96 views

### Probabilistic interpretation of optimality gap in Integer Program

Suppose I have an integer program model in the form of a minimization. I noticed that Gurobi (my solver) often finds a very good upper bound (i.e., feasible solution) whereas it takes a significant ...
• 445
1 vote
I want to solve the following problem with GAMS software: $\min y+\frac{1}{0.05} \sum_s p^s u^s$ $s.t$ $\sum_{j \in V}\delta_j=b$ $\sum_{j\in W^s} x_j^s +q^s=1 \ \ \forall s\in S$ \$ x_j^s \...