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
-1
votes
0answers
99 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
1answer
177 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
0answers
65 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) ...
0
votes
1answer
248 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 ...
5
votes
3answers
177 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 ...
1
vote
1answer
145 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 ...
2
votes
3answers
165 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. ...
7
votes
1answer
147 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(...
3
votes
1answer
94 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 ...
1
vote
2answers
133 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
votes
1answer
255 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 $...
4
votes
2answers
152 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{...
4
votes
1answer
141 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:
4
votes
2answers
226 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
1answer
116 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{...
1
vote
0answers
59 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)?...
2
votes
1answer
117 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 ...
3
votes
1answer
228 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 \ \& \ ...
1
vote
3answers
231 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{...
6
votes
2answers
207 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....
3
votes
2answers
346 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 ...
5
votes
2answers
292 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 ...
6
votes
2answers
2k 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 ...
5
votes
1answer
187 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 &\...
8
votes
1answer
402 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 ...
11
votes
2answers
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 ...
3
votes
1answer
54 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 ...
5
votes
2answers
339 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$...
3
votes
2answers
527 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 ...
5
votes
1answer
505 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 ...
9
votes
1answer
194 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{...
6
votes
1answer
411 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 ...
10
votes
1answer
565 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 &...
7
votes
1answer
258 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 ...
4
votes
0answers
63 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$...
23
votes
2answers
2k 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 ...
19
votes
5answers
4k 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 ...
16
votes
1answer
1k 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?
13
votes
4answers
274 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 ...
13
votes
4answers
866 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 ...