Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
211
questions
3
votes
1
answer
339
views
Linearize sum of product in objective function
Notation:
I have an optimisation problem with objective function: \begin{align}\max&\quad\sum_n Q_n\\\text{s.t.}&\quad Q_n=x_{ij}^{nk}(y_i^{nk}-c_n), \forall n \in N, k \in K, (i,j) \in P.\end{...
- 33
3
votes
0
answers
90
views
Linearization of the shifted copy of a function
Suppose in a model I have the expression $y_{1}(x) = 10 + 5 x^2$ where $x \in [0,20]$ is a continuous variable. In order to be able to use an MILP solver, I piecewise linearise $z_{1} = x^2$, by ...
- 2,170
6
votes
1
answer
465
views
Convert summation of min functions into linear constraints for optimization
I have the following optimization problem:
$$
\mbox{maximize } j^{*} \mbox{ subject to:} \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \geq \lambda, \lambda \in \mathbb{R} \mbox{ and } {\bf A}_j,{...
- 63
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
3
votes
0
answers
59
views
Linearisation using SOS2
I am trying to linearise the following expresssion.
$C(k) = B(k) e^{-d(k)}, B(k) \ge 0 , d(k) \ge 0 $
I am trying to do this by using SOS2 sets.
I set $X(k) = e^{-d(k)}$ and I get $C(k) = B(k) X(...
- 2,170
3
votes
1
answer
515
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
6
votes
1
answer
647
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 ...
5
votes
3
answers
255
views
Problem with binary decision variable constraints in VRP
I would like to create non-linear violation costs in my VRP. I already created my whole VRP with time windows in which I have these decision variable:
...
- 51
2
votes
1
answer
274
views
Inequality Constraint Linearization of a product of an integer and a binary variable
I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable?
But the answers to that questions didn't help me find a solution for my ...
- 93
2
votes
1
answer
92
views
How to linearize a weighted maximum coverage problem?
Is it possible that the binary variables below be modeled as continuous variables?
\begin{alignat}2\max&\quad\sum _{{e\in E}}w(e_{j})\cdot y_{j}\\\text{s.t.}&\quad\sum {x_{i}}\leq k,\quad&...
- 101
5
votes
2
answers
178
views
Minimizing $x_1/x_2$ over a simplex in the positive orthant
I need to solve the following problem
\begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad Ax \leq b\\&\quad x > 0\end{align} where $A$ is a positive matrix.
The best thing I can think ...
- 53
3
votes
2
answers
450
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
524
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
4
votes
1
answer
703
views
Transforming a Quadratic constraint to SOCP
I have a problem similar to Markowitz portfolio optimization that I would like to transform into second-order cone programming. I have a linear objective function with a quadratic constraint (assuming ...
- 151
8
votes
1
answer
695
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
5
votes
1
answer
607
views
How can I deal with a possibly undefined constraint?
I have a minimization problem minimizing $d_k \geq 0$ and some other variables with all strictly positive coefficients. I leave my objective function below to better convey my goal.
$$\min_{\mathbf{d}...
- 1,239
6
votes
1
answer
230
views
Linearizing the square root of binary summations
My question is similar to this one and almost identical with this. I am so confused due to indexing and could not make sure if I could apply the solution in here to this indexed version as shown below....
- 1,239
7
votes
1
answer
91
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
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
92
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
503
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,170
5
votes
2
answers
600
views
Trade off between number of constraints and bounds of a variable
I am not familiar with the inner working of the solvers. I mostly use the python pulp or IBM CPLEX solver.
For fast execution ...
- 1,589
3
votes
1
answer
285
views
Linearizing constraint with continuous and boolean variables
I have two continuous variables $A$, $B$ and two binary variables $x$, $y$.
Condition: if $A = B \wedge x = 1 \wedge y=1$ then $z = 1$ else $z = 0$ from
In an integer program, how I can force a ...
- 1,589
5
votes
1
answer
78
views
How to formulate case distinctions in AMPLs objective function?
This is my first real optimisation problem I formulated and now trying to solve by using AMPL.
The following objective function is from a linear 0-1 LP means all variables $x_i^b\in\{0,1\}$, with $i\...
- 287
3
votes
0
answers
61
views
Extract binary value from continuous variable [duplicate]
I have a continuous variable $c$ which has value in between $[-R, +R]$.
I want to create a boolean variable $x$ and,
$x = 1$ when $c = 1.0$ otherwise $x = 0$
In more general form:
$x = 1$ when $c \...
- 1,589
1
vote
0
answers
80
views
Converting Nonlinear Program into an LP
I have a problem with a nonlinear objective function which is
\begin{align}\min&\quad Z_j\cdot(N_j)^{0.5}\end{align} where $j$ is the index.
I want to know how can I turn it into a linear ...
- 35
6
votes
1
answer
169
views
How to propagate time using linear inequalities?
I have an adjacency matrix $G_{i,j}$ that tells the distance between $i$ to $j$ (between 0 to 1) if there is no edge between $i$ to $j$ I am putting a large integer $100$.
This is my previous ...
- 1,589
6
votes
1
answer
155
views
Linearizing objective function with absolute differences
I want to turn this objective function
$$\max \sum_{i=1}^{N-1} \sum_{j=i+1}^N |TX_i^T - TX_j^T|$$
where $T$ is just a vector with increasing integers (e.g $[1 \ 2]$) and $X_i$ is a vector ...
- 61
11
votes
1
answer
614
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
9
votes
2
answers
785
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,211
12
votes
1
answer
518
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
10
votes
2
answers
361
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
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
13
votes
6
answers
249
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 ...
- 13k
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,211
7
votes
2
answers
489
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,299
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,211
11
votes
4
answers
8k
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,299
8
votes
3
answers
469
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
6
votes
1
answer
658
views
Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?
I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know ...
- 447
6
votes
1
answer
265
views
How To Linearize $X = \max\{x_1,x_2\}$
I am new to thinking about math programming and I have a particular constraint I am hoping to reformulate, I just don't know the proper mathematical translation for what I am hoping to do. Enforcing ...
- 2,299
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
12
votes
2
answers
233
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.9k
6
votes
1
answer
8k
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
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
7
votes
1
answer
398
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,211
7
votes
2
answers
468
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,211
12
votes
1
answer
305
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
16
votes
1
answer
8k
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,086