Questions tagged [big-m]
For questions related to the use of a "big M" (large constant) in a mathematical modeling context, either in the objective function (to initialize the simplex method) or in constraints (to formulate logical constraints, to linearize constraints, and so on).
56
questions
2
votes
1
answer
194
views
Linearize piecewise function without big-M constraints
I have been attempting to solve a maximization problem where there is a piecewise function in the objective. Something like:
$\sum_{n}(1-prob_{n})(1+x_n)$
Where $prob_{n} = $
\begin{cases}
0.25,...
- 67
0
votes
1
answer
69
views
Travelling salesman problem
This is a CVRP problem and I have difficulty understanding the constraints in the red box.
For the sub-eliminator constraint (MTZ), my question is how can we make it on our own? Like I am sure there ...
- 39
1
vote
0
answers
136
views
Non-Linear objective function due to piecewise component (part 2)
This is a follow up to this question: Non-Linear objective function due to piecewise component
Consider a piecewise function but now with three segments but the objective remains the same as:
$\sum_{n}...
- 67
1
vote
1
answer
75
views
Mixed Integer programming, the big M
In the constraints below, why have they used the big M? What do we look for in order to identify the big M in other questions?
- 39
0
votes
2
answers
104
views
Modelling a binary variable in LPs
I need your help.
I'm setting up an LP and I'm trying to find constraints to introduce the binary varibale $b_{ij}$. So it should take the value 0 if the sum of all $a_{ij}$ values to the period t are ...
- 11
-1
votes
1
answer
65
views
Literature for the Big-M constraint method
I've come across the possibility of introducing binary variables in linear programming with the Big-M method here several times now. Here is an example:
\begin{align}
&(1-x_{i})\le \sum_i y_i\\
&...
2
votes
0
answers
57
views
Big M Modelling [duplicate]
It is advised that in a big M constraint, M should be chosen as small as possible.
Is this recommendation a hard fact or heuristics?
- 2,180
2
votes
3
answers
169
views
Linearization the product of three variables (two binary & one continuous)
Consider the following binary variable $x \in \{0,1\}$ and two continuous real variables $y,p \in \mathbb{R}$.
I am trying to model the following conditional equations as constraints:
\begin{cases}
...
- 103
2
votes
0
answers
39
views
Choosing upper and lower bound using big-M [duplicate]
This question is related to my previous question posted here: Piecewise constraint using big-M notation and this question posted on the math stackexchange: https://math.stackexchange.com/questions/...
- 67
2
votes
3
answers
538
views
How to find the index of the item, the first time appears?
How to formulate this problem as MIP:
For example, we have the following vector of binary variables:
$$
x= [0, 0, 0, 1, 0, 1, 1]
$$
How to find out when the first "1" is recorded? For ...
- 391
0
votes
2
answers
167
views
How to formulate "If statement with equality constraints" using big m? [duplicate]
How to convert this one to a linear program:
if $x=1$ then $B=1$; otherwise, $B=0$.
If I use the Big M method: \begin{align}x&\ge1-M(1-B)\\x&\le1+M(1-B)\end{align}
A) with $B=1$: \begin{align}...
- 391
2
votes
0
answers
166
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-...
- 121
3
votes
1
answer
300
views
gurobi bigM constraint vs. epsilon
I am new to mathematical programming and I am trying to implement case specific constrains in Gurobi with Python.
I am wondering about how I can implement my constraints in the fastest or most common ...
- 147
3
votes
1
answer
148
views
Disjunctive Constraint , Using Binary Variable to Replace a If or condition
I am trying to use a binary variable based on an inequality.
The value of binary variable $q $ is 1 or 0 based on the following equation.
[
$q $ =
\begin{cases}
0,& \text{if } b \geq \pi ,\\
1,...
2
votes
1
answer
134
views
Robust way to implement $(x=0) \Rightarrow (y=0)$, with $x$ nonnegative and $y$ binary
I am formulating a MILP in which there is a continuous variable x and a binary variable $y$.
In the program formulation there are the following constraints:
$Ay\leq x \leq By$ (with $0\leq A\leq B$). ...
- 424
3
votes
1
answer
265
views
Disjunctive equality constraints: modelling
I have the following constraint in my model:
$$x = 0 \lor \sum_{i=1}^n y_i = 3$$
where $x$ and $y_i$ are all binary variables.
How this can be linearized by means of big-M notation?
Should I include ...
- 33
-2
votes
1
answer
220
views
How to solve this linear programming minimization problem with the BigM method
Given this minimization problem:
$$z=100x_1+77x_2+80x_3\\10x_1+7x_2+2x_3 \geq 12\\2x_1+3x_2+4x_3 \geq 3\\x_1+2x_2+x_3 \geq 1\\x_1,x_2,x_3 \geq 0$$
After adding artificial variables:
$$z-100x_1-77x_2-...
4
votes
1
answer
214
views
How do constraints become redundant in a Big-M conjunction?
The following Big-M conjunction appears on page 14:3 of The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management:
\begin{align*}
\text{(i)} \quad t_{(g, \; s)} - t_{(f, \; s+...
1
vote
0
answers
120
views
vehicle routing optimization, Big M method of reformulation of constraints
Please excuse me for the long question, if I dont prrovide this info. my post gets removed!
The following optimization problem is called Mixed-Integer Quadratically Constrained Programming
(MIQCP) ...
- 349
0
votes
1
answer
811
views
Mutable parameter in Pyomo causes a problem
I am defining a Pyomo model that should have some mutable Big-M parameters whose values should be dynamically assigned (once). However, I am having a problem with a difference equation as described in ...
- 1,632
7
votes
3
answers
313
views
Modelling precedence relations
I have two tasks $i$ and $k$ with durations $d_i$ and $d_k$, where $d_i$ and $d_k$ are nonnegative variables.
I would like to model that $i$ may precede $k$ or $k$ may precede $i$ and that they may ...
- 2,180
1
vote
1
answer
223
views
Non-linear optimization local or global solution
In an NLP, I have a constraint that I would like to formulate in a convex manner preferably without introducing binary variables and/or big M formulations if possible. The actual problem is non-convex ...
- 81
2
votes
3
answers
1k
views
Linearizing a Max Function in the constraint - not working
I have a minimization function which is in its simplest form looks like below. I am including the index of the variables.
...
- 793
8
votes
1
answer
300
views
Formulating two non-negative variables without binary and/or big-M
There are two non-negative integer variables $q$ and $p$, where only one of them can take a positive value. To impose this relation, I write:
\begin{align}
q &\leq M(1 - y) \tag1 \\
p &\leq M(...
- 2,086
3
votes
1
answer
255
views
In integer programming what's the difference between using lower upper bound constraints and using a big M constraints?
I've noticed that for integer programming models with binary variables some use upper bound constraints and others use big M constraints in order to have two mutually exclusive choices.
I have trouble ...
- 181
1
vote
2
answers
242
views
Modeling the product of two variables
Suppose we have two continuous nonnegative variables $X_{1}$ and $X_{2}$ both bounded by the number $M$ from above.
I would like to model the following:
If $X_{1} > 0$ then $X_{2} = 0$
If $X_{2} &...
- 2,180
2
votes
1
answer
819
views
If-Then-Else modeling in MILP using the Big M method
I have trouble finding a solution to the following problem. I have a decision variable $x$. If the value of $x$ is between 0 and a constant $A$, then the binary variable $y_1$ must be equal to 1. If $...
- 23
4
votes
2
answers
312
views
Benders subproblem with product of continuous and discrete variables
I am trying to solve the following problem. The decisions in the problem are $x, y, v, $ and $W$, where $x, y$ are binary and $v, W$ are continuous variables.
\begin{equation}\label{eq:3}
\begin{...
- 411
5
votes
1
answer
309
views
how to apply Big M to model the logic constraint （if-then-else）
I was hoping to get some help in modelling the following logic as an MIP Constraint
c_{m,l}^{RC} is binary decision variable.
Simplify it：
- 51
4
votes
2
answers
520
views
Formulating the conditional constraint
I want to develop a model extension of capacitated location problem.
The variables are a binary $x_i$ and a continuous $Q_i$. The following condition must be satisfied:
if $x_i = 0$, $Q_i$ must be ...
2
votes
1
answer
162
views
Scenario based approach to value-at-risk optimization using mixed-integer programming
For a discrete set of scenarios, minimising value at risk can be formulated as a mixed integer linear programming problem. If each scenario has equal probability then this can be written as
\begin{...
- 161
1
vote
0
answers
64
views
Linearize max function in a constraint [duplicate]
I have a constraint as follows:
$ \sum_i {r_i} \geq \max \{g_j, B_j\} $
where, $r_i$, $g_j$ are variables and $B_j$ is a parameter.
How do I linearize the constraint (I suppose using big-M method)?...
- 793
2
votes
1
answer
191
views
How to transform these conditional constraints to linear integer ones in a more efficient way?
The conditional constraints A and B can be transformed to a set of linear integer constraints as follows:
A) $\text{if} \ x_1=0 \ \text{then} \ d_1=1 \ \text{else} \ d_1= 0\\ x_1\in {\rm I\!R}^{\geq ...
- 294
3
votes
1
answer
541
views
How to fomulate the following conditional constraint in MILP?
How can I formulate the following conditional constraint to a linear constraint using indicator variables? Please note that all variables are continuous and $c \ge 0$
$\text{1: if} \ c=0 \ \& \ ...
- 294
0
votes
3
answers
520
views
Using big M values for a constraint
I want to enforce $x_{i,j}=x_{k,j}\implies z_i \neq z_k$ where $k = i-1$ so I used \begin{align}z_k + 1 - (x_{i,j} - x_{k,j})) \leq z_i \leq z_k - 1 - (x_{i,j} - x_{k,j})\quad\text{for each $j$}\end{...
- 489
6
votes
2
answers
404
views
How to handle bigM in sub-problem of benders decomposition?
Suppose you want to solve a MIP with Benders decomposition and the binary variables ($y_i$) are fixed in the master problem but these variables are used in the sub-problem with bigM like $x_{ij} \le M....
- 2,150
3
votes
2
answers
467
views
Mocking up conditional statements in LP
I would like to know how if condition statements in linear programming can be reformulated using indicator constraints, and hence solved as a mixed integer linear program. Specifically:
1. Is it ...
- 161
5
votes
2
answers
560
views
Linearizing objective function with variables inside an indicator function
I am working on a problem in which I am trying to maximize the average of a variable only for the data that meet a certain condition with a constraint on the number of data that meet this condition. I ...
- 53
6
votes
2
answers
4k
views
IF X = 0 THEN Y = 1, IF X > 0 THEN Y => 0
I'm trying to model the following
IF $tS = 0$ THEN $Y = 1$, IF $tS \gt 0$ THEN $Y \ge 0$
$tS$ is a positive real number and $Y$ is binary.
I tried the following:
$tS - \epsilon \ge -M Y$ but ...
- 2,180
5
votes
1
answer
337
views
Converting if else condition to MIP constraints - validation
I have an if else condition as follows: If $g \ge 0$ then $e=1$, else $e=b$.
I formulated MIP constraints using big-M as follows where I am setting $\delta=1$ if $g \ge 0$:
\begin{alignat}2g &\...
- 793
8
votes
1
answer
764
views
if-else condition for the objective variable using big M notation
Let $0\leq \beta\leq 1$ be an objective variable. The size of $\beta$ is $N\!\times\!N$.
Now, how can I impose the following?
if $\beta_{i,j}>0$ then $\beta_{j,i}=0$
Big M notation can be ...
- 83
11
votes
2
answers
1k
views
Linear programming: objective function with "buckets"
I had a linear programming problem with the following objective function
$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$
Where $q, p, C, c$ are known.
This problem was ...
- 241
3
votes
1
answer
92
views
defining Mixed integer linear inequalities for a set of variables
The problem is described as follows:
considering $n$ variables which are continuous and bounded such that
$$L_i \le x_i \le U_i\quad \forall i=1,2,\dots,n.$$
How can i define a set of mixed integer ...
- 135
5
votes
2
answers
527
views
How to model If $A \le B$ then $Y = 1$, otherwise $Y = 0$
Somehow I don't get it right.
I would like to model the following conditional:
If $A\le B$ then $Y=1$ otherwise $Y=0$
where $A, B$ are reals and $Y$ is binary.
I can model as follows:
$Y \cdot A \le B$...
- 2,180
3
votes
2
answers
1k
views
Problem with big-M in CPLEX OPL
I have a model for the no-wait flow shop scheduling problem, that utilizes the linear ordering variables, and there is a constraint with big-M. When I implement the model in ...
- 2,086
5
votes
1
answer
1k
views
How is Big M calculated?
Because of excessive pollution on the Momiss River, the
state of Momiss is going to build pollution control stations.
Three sites (1, 2, and 3) are under consideration. Momiss is interested in ...
- 107
9
votes
1
answer
560
views
Introducing a big M variable in given equations
While I do understand the general workings of the Big-M-method I am struggling with the following sample exercise, in which the Big-M-method has to be used to find a first feasible solution:
\begin{...
- 93
6
votes
1
answer
996
views
Integer programming example clarification
There is an explanation in my book for an integer programming example, which goes like this:
A company is considering manufacturing three types of autos: compact, midsize, and large. The resources ...
- 107
10
votes
1
answer
1k
views
Linear programming with if-then-else (big-M)
I am trying to formulate the following in linear programming.
\begin{cases}\text{if}\,\,a>b\,\,\text{then}\,\,c=a\\\text{else}\,\,c=b.\end{cases}
I tried some things with big $M$, like $$a + my &...
- 367
7
votes
1
answer
339
views
Logical Constraints Modelling using Big-M formulation
I am trying to model some logical constraints in ILOG. Logical constraints could be given such as:
Constraint 1 or Constraint 2,
Constraint 3 or Constraint 4,
Constraint 5 or Constraint 6.
The ...
- 71