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

46 questions
Filter by
Sorted by
Tagged with
109 views

### Characterise a feasible-to-construct superset of a set

Intro: I have a non-convex set, defined by conditional constraints, that is infeasible to construct exactly. I would like your help to characterise a superset of this set that can be feasibly ...
13 views

### SDP relaxation help

Dears Let’s say I have the following constraints (as an example of my problem. I have other similar constraints as well) [(x_a)^2+(y_a)^2]-[(x_a).(x_b)+(y_a).(y_b)]+z+w=0 [(y_a).(x_b)-(x_a).(y_b)]-...
33 views

### LP Relaxation is unbounded

How do I go about proving the integer linear program has an optimal solution, but that its linear program relaxation is unbounded? \begin{equation} \begin{array}{cl} {\max} & {x_1} \\ {\text{s.t.}...
42 views

### While solving a MILP via subsequent Linear Relaxations are relaxed Indicator variables and constraints still useful to guide the objective function?

I have a multi objective Mixed Quadratic binary non-linear problem. Following a scalarization approach, the objective function includes the sum of some binary variables (say Z_j) minus lambda times ...
46 views

### Relaxation method on a system of two second-order, coupled, non-linear ODEs (boundary value problem)

This is my first question on Stack Exchange - I welcome any suggestions if my approach to asking it does not match the usual conventions around here. So: I need to solve a system of two second-order, ...
37 views

### Is the Frobenius norm defining a Trust-Region for a matrix?

I am minimizing a non convex function $f$ defined over the positive semidefinite cone $S_+^n$ through linearization methods (sequential linear/convex approximation) and I would like to constraint the ...
44 views

76 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 ...
54 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 ...
48 views

227 views

193 views

1k views

### In an optimization problem, why is a rank-1 constraint non-convex?

I was studying a problem in a paper in which the author tries to use the semidefinite relaxation (SDR) technique in order to solve it. After changing the original problem using the SDR technique, a ...
416 views

### Equivalence of a binary linear program and its relaxation

We know that given a binary (0-1) linear program, we can find lower/upper bounds using its relaxation. But, there are instances (such as shortest path problem with non-negative cycles, bipartite ...
55 views

1k views

### Linear Relaxation vs Lagrangian Relaxation

Let's say we are using Integer Programming in order to minimize an objective function. We are interested in computing a lower bound for the problem. My question is: when should we use a Linear ...
82 views

### Proving tightness of a semidefinite relaxation of a nonconvex quadratic program

The Lagrangian of my semidefinite relaxation of a nonconvex QCQP (quadratically-constrained quadratic program) is \begin{align} L&=\sum_{n=1}^{N}\operatorname{tr}\left(\textbf{Q}_n\textbf{X}\right)...
705 views

I am new to optimization and I am trying to understand concepts of semi-definite relaxation (SDR) through examples. It seems my understanding of this topic is not fully clear as I will show in details ...
1k views

### Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t$$ subject to:...
598 views