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

Filter by
Sorted by
Tagged with
4 votes
1 answer
145 views

Big-M in model notation?

I am currently writing my first paper and I was wondering whether it is usual to list Big-$M$ or Small-$m$ in the model notation, or are these values that can be regarded as standard? If so, do you ...
Uni ewr's user avatar
  • 61
2 votes
1 answer
113 views

Modelling L-0 norm of a vector

I have a binary variable $\bf x$ of length 4000. Let ${\bf x}=[x_1,x_2,\cdots, x_{4000}]$. Let's say we have ${\bf y}=[y_1,y_2,y_3,y_4]$, where \begin{align} y_1&=x_1+x_5+x_{9}+\cdots+x_{3997} \\ ...
KGM's user avatar
  • 2,265
0 votes
0 answers
114 views

why this little constraint changes my whole program?

I'm trying to linearize a CP in ILOG CPLEX. I have the following constraint that I want to linearize (I already simplified it with the big M) : ...
Marcocorico's user avatar
0 votes
0 answers
66 views

Why are these two constraint equations not equivalent?

I've made a CP Model of an hospital in ILOG CPLEX and I want to test the performance of the CPLEX version of it. In my CP model, I have the following constraint : ...
Marcocorico's user avatar
1 vote
1 answer
94 views

Logical conditions

This is similar to question I asked here: Priotization rules for variable allocation in linear programming. In an optimization problem, the goal is to manage the purchase and sale of items under ...
Lemma's user avatar
  • 23
1 vote
2 answers
114 views

Priotization rules for variable allocation in linear programming

I’m working on an optimization problem and need help with correctly prioritizing the allocation of certain variables in a constraint. The rules are: Only one of the variables $y_{t}$, $zn_{t}$ and $...
Lemma's user avatar
  • 23
1 vote
1 answer
86 views

Problems with Big-M Constraint

I have the following constraints for my roster optimisation problem: \begin{align} &(1-r_{i,t})\le \sum_{j=t-\chi}^{t-1}sc_{i,j}\quad &\forall i\in I, t\in \{1+\chi,\ldots,T\} \end{align} \...
lukdooxb1's user avatar
0 votes
1 answer
65 views

MIP binary decision value under a condition if else

In MIP, I have a constraint that is validated only if the demand $d_i\leq Q$: C1 : $d_i \leq x_i \leq Q$ where $x_i \geq 0$. I tried to introduce big M with binary variables as follows: $My \leq x_i \...
MAYA's user avatar
  • 129
-1 votes
1 answer
67 views

MIP formulation for a lower semi-continuous function

How can I formulate in mixed linear programming (a set of constraints) the following issue. I have an objective function $\underset{x}{\max} g(x)$. I need to convert a continuous linear function $f(x)$...
Di Al's user avatar
  • 11
2 votes
1 answer
229 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,...
akkha's user avatar
  • 67
0 votes
1 answer
101 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? I am sure there is ...
uni_lad's user avatar
  • 39
1 vote
0 answers
137 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}...
akkha's user avatar
  • 67
1 vote
1 answer
90 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?
uni_lad's user avatar
  • 39
0 votes
2 answers
111 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 ...
Karl Seidl's user avatar
-1 votes
1 answer
77 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\\ &...
marvelfab12's user avatar
2 votes
0 answers
58 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?
Clement's user avatar
  • 2,252
2 votes
3 answers
207 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} ...
Ahmed's user avatar
  • 113
2 votes
0 answers
40 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/...
akkha's user avatar
  • 67
2 votes
3 answers
595 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 ...
Hussein Sharadga's user avatar
0 votes
2 answers
214 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}...
Hussein Sharadga's user avatar
2 votes
0 answers
202 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
354 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 ...
Mike's user avatar
  • 147
3 votes
1 answer
159 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,...
Danish Shaikh's user avatar
2 votes
1 answer
155 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$). ...
Meth's user avatar
  • 424
3 votes
1 answer
290 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 ...
ORLover's user avatar
  • 33
-2 votes
1 answer
241 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-...
TheInquirer's user avatar
4 votes
1 answer
219 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+...
Amateur Reader's user avatar
1 vote
0 answers
130 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) ...
Jose_Peeterson's user avatar
0 votes
1 answer
897 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 ...
PeterBe's user avatar
  • 1,642
7 votes
3 answers
325 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 ...
Clement's user avatar
  • 2,252
1 vote
1 answer
224 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 ...
Marry's user avatar
  • 81
2 votes
3 answers
2k 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. ...
S_Scouse's user avatar
  • 803
8 votes
1 answer
321 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(...
Mostafa's user avatar
  • 2,104
3 votes
1 answer
281 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 ...
WindBreeze's user avatar
1 vote
2 answers
269 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} &...
Clement's user avatar
  • 2,252
2 votes
1 answer
870 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 $...
wlans's user avatar
  • 23
4 votes
2 answers
336 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{...
Pramesh Kumar's user avatar
5 votes
1 answer
382 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:
xuezheng's user avatar
4 votes
2 answers
536 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 ...
Bobby Kurniawan's user avatar
2 votes
1 answer
173 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{...
Sam's user avatar
  • 161
1 vote
0 answers
65 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)?...
S_Scouse's user avatar
  • 803
2 votes
1 answer
193 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 ...
SAH's user avatar
  • 294
3 votes
1 answer
576 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 \ \& \ ...
SAH's user avatar
  • 294
0 votes
3 answers
559 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{...
OR Junior's user avatar
  • 521
6 votes
2 answers
427 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....
Amin's user avatar
  • 2,150
3 votes
2 answers
496 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 ...
Sam's user avatar
  • 161
5 votes
2 answers
614 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 ...
Pierre's user avatar
  • 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 ...
Clement's user avatar
  • 2,252
5 votes
1 answer
349 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 &\...
S_Scouse's user avatar
  • 803
8 votes
1 answer
849 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 ...
user199's user avatar
  • 83