Questions tagged [valid-inequalities]
The valid-inequalities tag has no usage guidance.
18
questions
0
votes
1
answer
153
views
Proving the Validity of a Given Inequality Involving Ratios of $p$ and $q$
Consider the following inequality:
$$\left(\frac{p}{1-q}\right)^p \geq \left(\frac{q}{1-p}\right)^{1-p}$$
where $0<p, q< 1$ and $p+q<1$. I am trying to show that the following inequality ...
- 63
2
votes
0
answers
28
views
The facet-defining inequalities for a single resource scheduling problem
Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions:
$$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ...
- 8,450
1
vote
0
answers
262
views
Deriving a valid inequality
Given a set of facilities $I$ and days $J$, each facility $i \in I$ has a capacity of $C_i$, and a set of days $J$ where in each day $j \in J$ there's a total demand of $q_j$ that can be satisfied by ...
- 111
1
vote
1
answer
77
views
Finding a maximum violated infeasible subset
Given a binary optimization problem of the following form:
\begin{align}
min\; &cx&\\
&Dx \leq e&\\
&\sum_{i\in S} x_i \leq r(S) &\forall S\in \mathbb{S}\\
&x_i binary &...
- 3,396
1
vote
1
answer
77
views
down lifting of variable coefficients for cover inequalities
Given a cover inequality of the form:
\begin{equation}
\sum_{j\in C}x_j \leq |C|-1
\end{equation}
A lifted version of this inequality takes the following form:
\begin{equation}
\sum_{j\in C}x_j+\sum_{...
- 3,396
5
votes
2
answers
255
views
Separating violated cover inequalities
Consider a knapsack problem with binary variables and a standard knapsack constraint $\sum_{j\in N}a_jx_j\leq b$.
A set $C\subseteq N$ is a cover if $\sum_{j\in C}a_j >b$
If $C\subseteq N$ is a ...
- 3,396
6
votes
2
answers
195
views
Cover cuts for knapsack constraint with integer variables
It is known for knapsack type constraint $\sum_{i \in N} a_i x_i \leq b , x \in \{0,1\}$, we can generate the so called cover cuts that have the sum of coefficient in a set C greater than b. The cover ...
- 111
6
votes
1
answer
349
views
Valid Inequality Example (Wolsey Example 9.3)
I was following Wolsey Example 9.3: Let $X = \{(x,y) \in (R^{m}_+,B^1) : \sum_{i=1}^m x_i \leq my\}$. Now consider the valid inequality $x_i \leq y$ and show that it is facet defining.
My question is ...
- 61
4
votes
1
answer
127
views
Exploiting ordering to removing infeasible solutions in MILP
I kindly ask for some ideas or references to exploit ordering in MILPs.
In particular, there are resources $ r = [r_1, r_2, ..., r_K] $ such that $r_{i} \leq r_{i+1} $. These are input to the problem.
...
- 303
9
votes
3
answers
975
views
No-good cuts for general integer variables
Question:
Suppose we have an integer program $\min\{c^\top{x}\mid{Ax\leq{b}},x\in\mathbb{Z}_+^n\}$, and suppose that $x^*$ is a feasible solution for this IP (or even that $x^*$ is an extreme point of ...
- 2,047
8
votes
4
answers
650
views
Algorithm for simplifying a set of linear inequalities
I am looking for an algorithm that, given a set of linear inequalities in $m$ variables, returns a simplified set. "Simplified" may mean an equivalent set with a smallest number of ...
9
votes
1
answer
277
views
How to get all the facet inequalities from a set of valid inequalities?
For a given set of valid inequalities $\cal V$
$$
\left\{\sum_{i}^n w_k x_i + c_k \le 0\right\}_k
$$
we can obtain a polyhedron $P$ in $n$-dimensional space. It's known that the polyhedron $P$ can be ...
- 191
5
votes
1
answer
204
views
Guidelines for adding user cuts to models
Given that you have identified a new class of valid inequalities.
What are some guidelines on when and how many and which of the violated user cuts you add to the model?
I know that this involves a ...
- 3,635
10
votes
3
answers
388
views
Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?
Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities? If it is not, then what is?
For $m$ inequalities in $d$ ...
- 1,268
11
votes
2
answers
2k
views
Valid Inequalities and Strong Inequalities
Consider the following mixed-integer set:
\begin{equation}
P(A, b ; S) \stackrel{\text { def }}{=}\left\{x \in \mathbb{R}^{n} : A x \leq b, x_{j} \in \mathbb{Z} \text { for } j \in S\right\}
\end{...
- 8,450
15
votes
2
answers
2k
views
State-of-the-art algorithms for solving linear programs
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
- 2,140
11
votes
1
answer
165
views
How to relate dual values of valid inequality to the dual values of the original problem?
I have a given formulation that looks like this (just for the constraints):
$$\sum_i \beta_{i,j} \geq \alpha_j,\qquad\forall j$$
$$\alpha_j \geq \sum_i f_{i,j},\qquad\forall j$$
$$\alpha_j \geq 0, ...
- 998
20
votes
3
answers
2k
views
Are valid inequalities worth the effort given modern solvers?
In Laurence Wolsey's Integer Programming[1], he presents a well-known procedure for deriving valid inequalities (VI) suitable for integer and mixed integer linear problems (see Section 8.3, and also ...
- 1,885