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.

Filter by
Sorted by
Tagged with
8
votes
1answer
209 views

Specific algorithms to compute the LP-relaxation of the Set-Cover problem

One of the most commonly known combinatorial problems is the set cover problem, which states that given a collection of sets $S = \{s_1, \dots, s_m\}$ and a universe of elements $U = \bigcup_{i=1}^m ...
5
votes
2answers
135 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\...
5
votes
0answers
177 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 ...
3
votes
0answers
64 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 ...
6
votes
2answers
361 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 ...
9
votes
0answers
69 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 ...
13
votes
2answers
981 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 ...
24
votes
6answers
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 ...
15
votes
1answer
165 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 ...
11
votes
3answers
192 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 ...