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.

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

Why do I get a binary solution even when I solve an LP problem with continuous variables?

I have a MILP in the following form maximize $${\bf c}^T{\bf x}$$ subject to $${\bf Ax}\le {\bf b}$$ Matrix ${\bf A}$ is a binary matrix, and very sparse. It is a larger matrix with 300 rows and 1000 ...
KGM's user avatar
  • 2,377
0 votes
0 answers
95 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,940
2 votes
1 answer
87 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 ...
occasional's user avatar
2 votes
0 answers
88 views

Re-formulating an LP where a subset of constraints can be loosened?

I have an LP of the structure below (omitting some constraints that are not directly applicable for this question). $$\text{min } c'x$$ $$Ax + By \geq d$$ for a given $A \in R^{m \times a}_{>0}, B \...
Mason's user avatar
  • 515
0 votes
0 answers
75 views

Cost function value of relaxed ILP after rounding is less than or equal to the optimal one

I have a minimization problem for which I am having some misunderstandings and confusions with regard to some results I am getting for an ILP and its LP relaxation. In the ILP I have two decision ...
LyLa's user avatar
  • 1
1 vote
2 answers
112 views

Modeling of a special form of the precedence constraint

There exists a scheduling problem in which some tasks should be processed on some resources. Additionally, each task needs to be assigned to a specific position on each resource. Let the decision ...
A.Omidi's user avatar
  • 8,940
4 votes
1 answer
397 views

How do we branch a Cutting Stock problem using Branch and Price?

I'm sure this is a straightforward question, but since I started learning integer programming recently this isn't clear to me. Consider solving a 1 dimensional cutting stock problem using delayed ...
133crem's user avatar
  • 41
2 votes
0 answers
207 views

Big M and convergence of LP to IP

I have been working on an applied problem with Big M constraints (due to several security issues in the company, I cannot write the formulation I am working on). While solving with a partially LP-...
Applicable Math's user avatar
3 votes
1 answer
118 views

Totally unimodular towards linear programming relaxation

I'm currently studying about totally unimodular. I was reading this link: https://ostad.nit.ac.ir/upload/Integer_Programming_1.pdf, from page 38-41 and I came across the statement: 'It is clear that ...
Michelle Gunawan's user avatar
1 vote
3 answers
609 views

How to transform this BIP into LP with the help of penalty function?

I have an BIP problem as below $$\underset{\bf b}{\max}{\bf u}^T\bf b$$ $$\text{subject to}$$ $${\bf Ab}\le1$$ Here, ${\bf b}=\{b_1,b_2,\cdots,b_N\}$ is a column vector of decision/optimization ...
KGM's user avatar
  • 2,377
7 votes
2 answers
514 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 ...
Brannon's user avatar
  • 900
2 votes
1 answer
307 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 ...
amr zaki's user avatar
3 votes
1 answer
227 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 ...
amr zaki's user avatar
7 votes
1 answer
232 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 "...
Mehdi Iranpoor's user avatar
3 votes
1 answer
477 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 ...
Mike's user avatar
  • 717
8 votes
1 answer
267 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 ...
Paul Bouman's user avatar
  • 2,100
6 votes
2 answers
611 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\...
k88074's user avatar
  • 1,691
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 ...
A.Omidi's user avatar
  • 8,940
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 ...
Divyam Aggarwal's user avatar
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 ...
k88074's user avatar
  • 1,691
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 ...
gornvix's user avatar
  • 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 ...
GrayLiterature's user avatar
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 ...
rasul's user avatar
  • 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 ...
LarrySnyder610's user avatar
13 votes
3 answers
634 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 ...
Yinan's user avatar
  • 379