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).
50
questions
2
votes
0
answers
51
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,132
2
votes
3
answers
121
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
33
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/...
- 43
2
votes
3
answers
505
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
139
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
142
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
244
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
135
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
111
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
215
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
178
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
208
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
110
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) ...
- 347
0
votes
1
answer
727
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,668
7
votes
3
answers
276
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,132
1
vote
1
answer
207
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
250
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,074
3
votes
1
answer
220
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
205
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,132
2
votes
1
answer
685
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
285
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
242
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
480
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
152
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{...
- 151
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
184
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
476
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
455
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{...
- 425
6
votes
2
answers
359
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,140
3
votes
2
answers
440
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 ...
- 151
5
votes
2
answers
474
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
3k
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,132
5
votes
1
answer
319
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
658
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
90
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
486
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,132
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,074
5
votes
1
answer
947
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
507
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
867
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
321
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
4
votes
0
answers
65
views
If and then constraint for a special case [duplicate]
I have the following constraint:
$$f\geq C_1\left(d-z-E_1-E_2\right)+C_2\left(E_1+E_2\right).$$
Here $f, d,z\in \mathbb{R}_{\geq 0}$ and $y\in \{0,1\}$ are variables and $C_1$, $C_2$, $E_1$, and $E_2$...
- 1,239
23
votes
2
answers
5k
views
Why is it important to choose big-M carefully and what are the consequences of doing it badly?
The question here discusses the two different use of "big-M method", where one of them is the big-M in logical constraints and linearization in (mixed-)integer programming problems (that's what I'm ...
- 5,796
19
votes
5
answers
7k
views
When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs
Various optimization modeling languages and solvers allow for both indicator constraints (see for example here, here and here) and traditional binary variable and big-M approaches can be used to model ...
- 193
17
votes
1
answer
3k
views
What is the "big-M" method? And are there two of them?
I’ve seen the "big-$M$ method" referred to in different ways. What is the "big-$M$ method" and why does it seem to mean two different things?
- 12.9k
13
votes
4
answers
484
views
The effect of choosing big M properly
I have a set of linearized constraints that are modelled using big-Ms. Now, it is, of course, common knowledge to make the value of M and small as possible in order to provide tighter LP relaxations ...
- 1,859
13
votes
4
answers
1k
views
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
Is there a single crisp and accessible reference which covers how to generate Mixed Integer Programming formulations to linearize products, handle logical constraints and disjunctive constraints, do ...
- 12.4k