# Questions tagged [valid-inequalities]

The tag has no usage guidance.

20 questions
Filter by
Sorted by
Tagged with
1 vote
30 views

• 9,123
1 vote
268 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 ...
• 113
1 vote
83 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,481
1 vote
86 views

### down lifting of variable coefficients for cover inequalities

Given a cover inequality of the form: $$\sum_{j\in C}x_j \leq |C|-1$$ A lifted version of this inequality takes the following form: \sum_{j\in C}x_j+\sum_{...
• 3,481
323 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,481
292 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 ...
• 113
351 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
131 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
1k 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,117
672 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 ...
• 1,015
295 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
243 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,655
395 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,278
2k views

### Valid Inequalities and Strong Inequalities

Consider the following mixed-integer set: 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{...
• 9,123
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,170
168 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
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,895