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.
15
questions
7
votes
2
answers
469
views
I ran a relaxed MIP and got some integer results; how can I constrain MIP to match those integers?
Suppose I run a relaxation of an MIP. If my result is all integers, I have achieved the same min/max that the MIP would achieve. However, what can I say if some portion of my result is integer?
If ...
- 533
2
votes
1
answer
142
views
KKT conditions analysis for binary constraints
I am wondering if boolean constraints in a linear program can be solved (after linear relaxation from $x\in\{0,1\}$ to both $x\ge0$ and $x\le1$) using KKT analysis.
Most of the algorithms that I have ...
- 51
3
votes
1
answer
134
views
Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT
I am trying to convert a boolean LP to LP using LP relaxation by converting $x \in {0,1}$ to both $x \ge 0$ and $x \le 1$.
Then to use it in my problem analysis, I am trying to build the KKT ...
- 51
7
votes
1
answer
127
views
Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?
The Lagrangian relaxation approach is used to generate lower (upper) bounds for minimization (maximization) problems by moving some constraints to the objective function and multiplying them by "...
3
votes
1
answer
188
views
Obtaining linear relaxation objective value from MILP model coded in Pyomo
I would like to seek some advice on modeling the following:
I am currently using Pyomo to generate my MILP model in Pyomo. It seems that it is not possible to cast the integer and binary variables to ...
- 663
8
votes
1
answer
234
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 ...
- 2,030
5
votes
2
answers
258
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,428
5
votes
0
answers
577
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 ...
- 5,705
4
votes
0
answers
75
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 ...
- 668
8
votes
3
answers
982
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,428
11
votes
1
answer
139
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,249
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,110
15
votes
1
answer
176
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 ...
- 12.5k
12
votes
3
answers
311
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 ...
- 369