Skip to main content

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
3 votes
1 answer
71 views

How to reformulate the BigM constraints into its equivalent Convex-hull formulation?

I am trying to work on a scheduling problem based on its polyhedron reformulations. For that, I would like to reformulate a BigM model into its equivalent C-hull formulation. The transforming map is ...
A.Omidi's user avatar
  • 9,044
1 vote
0 answers
43 views

How to force a bounded relationship to "become redundant" or "not needed"?

As an engineer who is currently working with some optimization problem I am currently running into a difficult reformulation problem. Here $a$ is a binary decision variable, $\phi \in [0,1]$ and $d$ ...
Tuong Nguyen Minh's user avatar
3 votes
1 answer
87 views

Enforcing Order in a Linear Programming Question

I have an optimization model to fulfill the water requirements of a city's distribution network. The model includes water sources from rainfall collection, river extraction, reservoir storage, and ...
snek's user avatar
  • 31
1 vote
1 answer
54 views

The first reference which formulated k-means problem as MIQCP using big-M constraint

k-means, or MSS (minimum-sum-of-squares) clustering is a basic problem in statistics. To remind, for a set of points $P_1, P_2, \dots, P_N$ in $\mathbb{R}^d$, the problem is to find $K$ centres $Q_1, ...
MindaugasK's user avatar
2 votes
0 answers
52 views

Using BigM and auxiliary variable to linearise model leads to incorrect results

I am working on a Pyomo optimization model that aims to select the cheapest fuel for production at different facilities over several time periods. The model should select Mode1 for Tech1 when Fuel1 is ...
Jamie Bull's user avatar
0 votes
1 answer
76 views

Getting rid of Big-M notation

i have the following constraint using the Big-$M$ method and i was wondering if it is possible to formulate these constraints without Big-$M$. These are the constraints in question: $$\sum_{j=1}^{t}z_{...
Karl Seidl's user avatar
4 votes
2 answers
230 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
  • 71
2 votes
1 answer
120 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,377
0 votes
0 answers
116 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
97 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
117 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
89 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
69 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
69 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
268 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
97 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
118 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
89 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
59 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
227 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
611 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
261 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
214 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
388 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
168 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
165 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
305 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
253 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
220 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
143 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
952 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,682
7 votes
3 answers
338 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
229 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
337 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
309 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
277 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
905 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
367 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
399 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
542 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
181 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
195 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
595 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
604 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
  • 543