Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
198
questions
36
votes
2
answers
9k
views
How to linearize the product of a binary and a non-negative continuous variable?
Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
- 2,411
35
votes
3
answers
12k
views
How to linearize the product of two binary variables?
Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
- 2,411
32
votes
8
answers
2k
views
Modeling floor function exactly
Suppose we want to enforce a constraint
$$
y=\lfloor{x}\rfloor
$$
where $x$ is some continuous variable. One option is to use
$$
x-1\leq{y}\leq{x},\quad y\in\mathbb{Z},
$$
which fails on the edge case ...
- 2,027
22
votes
4
answers
3k
views
Linearize or approximate a square root constraint
I encounter a nonlinear constraint that contains the square root of a sum of integer variables. Of course one could use nonlinear solvers and techniques; but I like linear programming. Are there any ...
- 1,859
21
votes
3
answers
1k
views
How to minimize an absolute value in the objective of an LP?
I want to solve the following optimization problem
$$\begin{array}{ll} \text{minimize} & | c^\top x |\\ \text{subject to} & A x \leq b\end{array}$$
Without the absolute value, this a ...
- 1,472
16
votes
1
answer
764
views
How to linearize a constraint with a maximum or minimum in the right-hand-side?
Suppose we have three variables, $x, y, z \in \mathbb R$. How can we linearize constraints with the following structure?
$$z \geq \min(x, y)$$
$$z \leq \max(x, y)$$
- 2,411
15
votes
5
answers
6k
views
How to linearize the product of two continuous variables?
Suppose we have two variables $x, y \in \mathbb R$. How can we linearize the product $xy$?
If this cannot be done exactly, is there a way to get an approximate result?
- 2,411
15
votes
1
answer
7k
views
How to formulate (linearize) a maximum function in a constraint?
How to formulate (linearize) a maximum function in a constraint? Suppose $C = \max \{c_1, c_2\}$, where both $c_1$ and $c_2$ are variables. If the objective function is minimizing $C$, then it can be ...
- 2,074
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
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
6
answers
243
views
How to formulate: each pair of elements in $A$ has one common unit in $B$
We have two sets, $A$ and $B$. Some elements of $A$ must be connected to some elements of $B$, but no element of a given set is connected to another element of the same set. (Think of a bipartite ...
- 12.9k
13
votes
2
answers
118
views
Sensible and realistic way to model truck based transport costs depending on amount
Different kinds of problems involve transporting an amount $x$ from A to B which results in a cost $c(x)$ in the objective function.
Traditionally, often linearized costs are used to get an easy, ...
- 1,100
12
votes
1
answer
297
views
QA techniques for optimization problem coding
I often spend much, much, more time QAing and debugging my code than I do actually writing the optimization problem or shaping my data. Are there any tools or techniques to make it easier? I am asking ...
- 747
12
votes
1
answer
639
views
McCormick envelopes and nonlinear constraints
I have a problem with a nonlinear constraint. The non-linearity stems from a term of the form $xb$, where $x \in \mathbb{R}^+$, $x < M$ and $b \in \{0, 1\}$. I am able to remove this non-linearity ...
- 221
12
votes
2
answers
224
views
Linearisation techniques for MINLPs
I am wondering what kinds of linearisations people do for MINLPs outside my field of expertise.
I work in global optimisation, so by "linearisation" we would typically mean one of the following:
...
- 11.8k
12
votes
1
answer
485
views
Linearization of the product of two real valued variables - Binary expansion approach
I want to minimize the following objective function:
\begin{align}\min &\quad x\cdot y\\\text{s.t.}&\quad2 \le x \le 5\\&\quad5 \le y \le 10.\end{align}
Since the objective function is ...
- 793
11
votes
4
answers
806
views
How to linearize a constraint with a maximum of binary variables times some coefficient in the right-hand-side
I have the following constraint that I'd like to linearize:
$P$ is a given set
$b_p \in \{0,1\} , \forall p \in P$ a binary variable associated with each element of $P$
$c_p \in \mathbb{R}^+$, a ...
- 2,378
11
votes
1
answer
464
views
How to linearize membership in a finite set
Given finite set $S$ and variable $x$, how do I linearize the set membership constraint $x\in S$?
- 28.2k
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
11
votes
4
answers
7k
views
What are the benefits of linearization?
So I am new to OR (not my field, but I have found myself working in it for a thesis project). My problem is a non-linear problem by design and unfortunately I cannot linearize everything, however, ...
- 2,289
11
votes
1
answer
586
views
k-means/k-medoids Clustering Implementation in CPLEX Java
I am trying to model a grouping algorithm as k-means clustering problem, by referring to the general definition as mentioned in Wikipedia.
In my system, I have $N$ nodes that I want to group in $m$ ...
- 534
10
votes
6
answers
2k
views
Nonlinear integer (0/1) programming solver
I have the following optimisation problem.\begin{align}\max&\quad\sum_i\sum_j\sum_k x_{ji}y_{kj} \operatorname{cost}(i,k)\\\text{s.t.}&\quad\sum_j x_{ji}=1\quad\forall i\\&\quad\sum_k y_{...
- 109
10
votes
4
answers
2k
views
Integer programming problem with simple quadratic objective function in Python
I have $n$ objects that need to be divided among $k$ groups. Each group must receive at least $5$ objects. In addition, the percentage of objects in group $i$ should be as close as possible to $p_i$ ...
- 343
10
votes
3
answers
1k
views
Is there a heuristic approach to the MILP problem?
I have the following optimization problem which is a MILP. I can solve it with a MILP solver.
\begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
- 2,191
10
votes
2
answers
337
views
Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint
I have a MIP minimization problem where I have a maximization in the constraints:
$$\max(c_1x_2,\, c_2x_2,\, \ldots,\, c_nx_n) \geq q$$
Where:
$c_n$ constants
$x_n$ binary variables
$q$ constant
$...
- 205
8
votes
2
answers
769
views
MILP Penalty Function Only for Negative Values
This is (hopefully) an easy answer but I haven't dealt with this before.
I have a MILP which includes an unbounded, continuous decision variable. However, I generally don't want this decision ...
- 721
8
votes
2
answers
736
views
How can I transform this MILP into an LP problem?
I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient ...
- 2,191
8
votes
3
answers
467
views
Linearization of a scheduling objective function
I am trying to maximize the workload per employee.
An example:
$e$ the index of an employee
$j$ the index of a project
decision variable: $x_{e,j} \in \mathbb{Z}$ and $0 \leq x_{e,j} \leq 100$ ...
- 1,193
8
votes
2
answers
629
views
knapsack problem with non-linear constraint
I have a basic knapsack problem where I need to fit the most weight possible in a bin:
...
- 215
8
votes
2
answers
2k
views
How to linearize a constraint with max
I would like to linearize a constraint with max. I have the following constraint:
$$\max_{pcj}X_{pwcj}\leqslant L_{wk}.$$
With this constraint, I would like to ensure that for $\forall w \in W$, no ...
- 1,133
8
votes
1
answer
657
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
8
votes
1
answer
2k
views
How to linearize the multiplication of an integer and a binary integer variable?
I have the following constraints
\begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align}
where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable ...
- 2,191
7
votes
2
answers
1k
views
Mixed-integer optimization with bilinear constraint
So I have an optimization problem of the following form:
\begin{aligned}
\max_{x,y} \quad & \sum_i x_i \\
\text{s.t.} \quad & \sum_i x_iy_i \leq a \\
\quad & x_{\min} \leq x \leq x_{\max} ...
- 193
7
votes
2
answers
845
views
Is there a better way of defining a constraint on positive integer variables such that no two variables are the same and are uniquely assigned a value
So suppose I have integer variables $x_1,x_2,\dots,x_N$ and I enforce that the integer variables are bounded i.e $1 \leq x_i \leq N$
I was interested in posing a constraint so that in the collection $...
- 205
7
votes
2
answers
480
views
Why does a Max constraint work, but this non-negativity constraint does not?
Suppose I have the following constraint: \begin{align}x_{t} &= x_{t-1} + y_{t-1} - z_{t-1}\\x_{t} &\ge 0\end{align}
From my limited experience in coding my own problem, I have found that my ...
- 2,289
7
votes
2
answers
459
views
How can I linearize or convexify this binary quadratic optimization problem?
I have an optimization problem as below. I am having a hard time with the last constraint.
$\max \eta$
subject to
${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$
here
$\bf{A}$ is a Binary ...
- 2,191
7
votes
2
answers
245
views
Product of weighted binary variables equivalent to sum of weighted binary variables?
I'm working on an optimization problem with a non-linear objective function of the form $$\max\prod_{i=1}^{n}(1-a_{i}x_{i}).$$
The objective function represents the combined probability of success for ...
- 313
7
votes
1
answer
272
views
Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem
I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem.
Informally:
We have a $m \times n$ decision matrix of binary variables
Each row of the matrix ...
- 173
7
votes
1
answer
390
views
How to reformulate (linearize/convexify) a budgeted assignment problem?
I have a scheduling problem at hand. In my system, there is a service station with $M$ service outlets, therefore, the service station can serve $M$ users at a time. But, there are $N$ users $N>M$ ...
- 2,191
7
votes
1
answer
248
views
Linearizing a program with multinomial logit in the objective
I have a nonlinear problem as follows: \begin{align}\min&\quad\sum_{k=1}^{K}\left|y_k - \sum_{i=1}^{N} \frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K} e^{x^{i}_{j}}}\right|\\\text{s.t.}&\quad x^i_{j} \ge ...
- 173
7
votes
1
answer
88
views
Linearizing the square root of two binary summations
My question is similar to this one though a bit more complicated. Though my question also includes indices, I am removing them to ease readability.
Let binary variables $x,y\in\{0,1\}$, non-negative ...
- 1,239
7
votes
1
answer
217
views
Maximizing a Ratio/Percent
I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they ...
- 195
6
votes
2
answers
843
views
How to transform this logical if-then constraint?
Consider the binary variables $x, y, z \in \{0,1\}$.
I'd like to formulate the two if-then constraints:
$$ x + y \geq 2 \implies z = 0, \tag{1} $$
$$ x + y \leq 1 \implies z = 1. \tag{2} $$
Constraint ...
- 385
6
votes
1
answer
7k
views
How to linearize min function as a constraint?
I'm trying to solve an optimization problem including following constraint, and I need to linearize it in a maximization nonlinear programming model. Please help me to reformulate it with mixed ...
- 77
6
votes
2
answers
2k
views
Linearization of objective function
Notation
$\text{src}_{h,s},\text{dst}_{h,s},\text{ch}_{h,s}$ are constants.
$a_{h,s},x_{i,j,s}$ are binary variables.
$\text{wt}_{h,s}$ are continuous variables.
Problem
\begin{align}\min.&\...
- 1,589
6
votes
2
answers
371
views
How to model this expression?
Suppose $0\le x \le 1$ is a decision variable and $\gamma(x)$ is defined as follows:
$$
\gamma(x)= \begin{cases}
\theta & x>0\\
0 & x=0
\end{cases}
$$
where $0\le \theta\le 1$.
In my model, ...
- 2,140
6
votes
2
answers
440
views
How to measure the tightness of MILP models?
Suppose we have a MILP model. How can we say this model is tight or not?
How to make it more tight? Any advice or example?
- 1,120
6
votes
2
answers
287
views
Forbid transformation of max(x,y) into MILP
The function $\max(x,y)$ can be linearized by making use of additional binary variables. I suppose global optimisers are implemented to perform this transformation automatically.
Is there a global ...
- 2,132
6
votes
1
answer
608
views
Linearize a product of an integer variable (not just binary) and a continuous variable?
I have a constraint in my formulation that contains multiplication of an integer variable $y$ and a continuous variable $x$, which is $xy=q$ where $y$ is the number of units in which $q$ gets equally ...
6
votes
2
answers
541
views
How to solve Rogo Puzzle with an extra constraint?
Given a n×m grid with numbered cells and forbidden cells, the objective of the Rogo puzzle is to find a loop of fixed length through the grid such that the sum of the numbers in the cells on the loop ...
- 1,120