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.
22
questions
0
votes
0
answers
31
views
On Linear Relaxation of Convex Quadratic Maximization over Linear Constraints
Consider the following QP problem, where the matrix $Q$ is positive definite:
\begin{align*}
\max_{x} \quad & x^\top Qx + c^\top x \\
\text{s.t.} \quad & Ax \geq b, \\
& ...
1
vote
1
answer
77
views
On Linear Relaxation of Standard Quadratic Programming
Consider the following StQO problem where matrix $Q$ is indefinite:
\begin{align*}
\text{minimize} \quad & x^\top Qx \\
\text{subject to} \quad & e^\top x = 1, \\
& ...
2
votes
1
answer
89
views
Optimization under cardinality constraint
When we consider the following optimization problem:
\begin{equation}\label{P}\tag{P}
\begin{array}{ll}
\displaystyle\min_{x \in \mathbb{R}^n} & f(x) \\
\text{s.t.} & Ax = b,~ x \geq 0, \\
&...
2
votes
1
answer
94
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 ...
- 21
1
vote
0
answers
69
views
Strong relaxations for binary variables
Having the following optimization problem that models $\sum_i\min(c_i, C)$:
$$
\min_{\mathbf{Y},\,\,\{x_i\}_i} \sum_i^{n} c_ix_i + C(1-x_i)
$$
and where
$C$ is a positive constant,
each $x_i$ is a ...
- 11
2
votes
2
answers
182
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{...
- 639
4
votes
1
answer
170
views
Does minimizing the upper bound due to Jensen's inequality yield an equivalent solution?
$\DeclareMathOperator*{\argmin}{\arg\!\min}$Consider the convex function $f : X \to \mathbb R$, where $X \subseteq \mathbb R^n$ is a convex set. Define the functions $g_\ell : X^m \times \Delta \to \...
- 639
1
vote
2
answers
97
views
Relaxing non-affine equality constraints in convex optimization
Consider the convex function $f$. In section 4.2.1 in these lecture notes, the author writes:
4.2.1 Relaxing non-affine equality constraints
For functions $g_i(x)$, $i \in \{1,\dots,d\}$ that are ...
- 639
1
vote
0
answers
39
views
Convex quadratic maximization over cartesian product of simplices
Suppose we are maximizing $f(x^1,\ldots,x^t)= \begin{bmatrix}{x^1}^\top & \ldots & {x^t}^\top \end{bmatrix}^\top Q \begin{bmatrix}{x^1}^\top & \ldots & {x^t}^\top \end{bmatrix}$ ...
- 4,020
3
votes
1
answer
1k
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 ...
- 43
2
votes
1
answer
330
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 ...
- 51
3
votes
1
answer
229
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 ...
- 51
6
votes
1
answer
167
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 ...
- 71
4
votes
1
answer
260
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+\...
- 269
3
votes
2
answers
144
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 ...
- 423
2
votes
0
answers
126
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 ...
- 29
6
votes
2
answers
643
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\...
- 1,701
3
votes
0
answers
155
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{...
6
votes
1
answer
844
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 ...
8
votes
3
answers
225
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 ...
- 12.2k
7
votes
2
answers
3k
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 ...
- 169
21
votes
5
answers
694
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 ...
- 540