Skip to main content

# Questions tagged [lp-relaxation]

For questions relating to the relaxation of linear integer or mixed-integer-linear programming (MILP) problems where the integer constraints are removed.

24 questions
Filter by
Sorted by
Tagged with
0 votes
0 answers
90 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 ...
• 8,950
2 votes
1 answer
84 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 ...
2 votes
0 answers
87 views

• 2,100
6 votes
2 answers
598 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,671
5 votes
0 answers
1k views

### What is the difference between root relaxation and LP relaxation

(I apologize. I saw this question but, I do not know these may be the same or not.) I am trying to solve a MIP problem and have an issue about that. The problem's LP relaxation has the objective ...
• 8,950
4 votes
0 answers
87 views

### Problem related to machine's performance while solving an LP-relaxation of a set-covering problem using the Column Generation

PS: I am familiar with performance variability encountered while solving large-scale MIPs. My question may not be explicitly related to it but maybe to the inefficiency of python packages. I have ...
8 votes
3 answers
2k views

### Cplex 12.10: How can I solve an LP relaxation?

I have an IloCplex object which contains a MILP. Is there a way to obtain the objective value of its LP relaxation, without having to rewrite the entire model as ...
• 1,671
11 votes
1 answer
163 views

### What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
• 331
13 votes
2 answers
1k views

### Is This Constraint Convex?

I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning ...
• 2,309
25 votes
6 answers
2k views

### How to compare two different formulations of a problem?

I somewhat know how to compare two MILP formulations of a problem that both use the same set of decision variables (as in the classical MTZ vs DFJ formulations of the TSP). I was wondering how two ...
• 2,150
15 votes
1 answer
189 views

### Symmetric undirected $p$-median instance with fractional LP solution?

The $p$-median problem is NP-hard, so its LP relaxation does not naturally have all-integer solutions. However, it very often does; in fact, it can be hard to find an instance for which the LP ...
• 13.1k
13 votes
3 answers
622 views

### Efficiency of solving LP relaxation

I'm building a mixed-integer programming model, and the solver is experiencing a very long run time. So I tried to solve the LP relaxation to the MIP, and I get a similarly long solve time, which ...
• 379