# 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.

20 questions
Filter by
Sorted by
Tagged with
1 vote
102 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 ...
309 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 ...
168 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-...
107 views

1 vote
599 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 ...
510 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 ...
274 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 ...
218 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 ...
212 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 "...
418 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 ...