Skip to main content

Questions tagged [valid-inequalities]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
88 views

Tightening a specific constraint

I would like to know if there exists any way to reformulate the following constraint in which one can relax the binary variable $z_{j,m}$, and the solution still being an integer for that. The ...
A.Omidi's user avatar
  • 8,950
0 votes
1 answer
157 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 ...
Javidit's user avatar
  • 63
2 votes
0 answers
32 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+}, ...
A.Omidi's user avatar
  • 8,950
1 vote
0 answers
263 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 ...
CHE's user avatar
  • 113
1 vote
1 answer
81 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 &...
Joris Kinable's user avatar
1 vote
1 answer
81 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_{...
Joris Kinable's user avatar
5 votes
2 answers
307 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 ...
Joris Kinable's user avatar
6 votes
2 answers
254 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 ...
CHE's user avatar
  • 113
6 votes
1 answer
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 ...
Joshua's user avatar
  • 61
4 votes
1 answer
129 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. ...
Duns's user avatar
  • 303
9 votes
3 answers
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 ...
David M.'s user avatar
  • 2,107
8 votes
4 answers
668 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 ...
Erel Segal-Halevi's user avatar
9 votes
1 answer
289 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 ...
Eden Harder's user avatar
5 votes
1 answer
232 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 ...
user3680510's user avatar
  • 3,655
10 votes
3 answers
392 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$ ...
Nike Dattani's user avatar
  • 1,278
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{...
A.Omidi's user avatar
  • 8,950
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)....
rasul's user avatar
  • 2,150
11 votes
1 answer
167 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, ...
dourouc05's user avatar
  • 998
21 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 ...
SecretAgentMan's user avatar