Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
33
questions
10
votes
1answer
110 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$ ...
7
votes
2answers
224 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 ...
10
votes
1answer
130 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 ...
10
votes
2answers
119 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
$...
11
votes
4answers
524 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$ ...
13
votes
6answers
186 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 ...
10
votes
3answers
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,...
7
votes
2answers
412 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 ...
8
votes
1answer
119 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 ...
11
votes
4answers
1k 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, ...
8
votes
3answers
366 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$ ...
6
votes
1answer
136 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 ...
6
votes
1answer
127 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 ...
8
votes
2answers
270 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 ...
12
votes
2answers
149 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:
...
6
votes
1answer
262 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 ...
6
votes
2answers
365 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.&\...
19
votes
4answers
995 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 ...
7
votes
1answer
228 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$ ...
7
votes
2answers
309 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 ...
12
votes
1answer
138 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 ...
14
votes
1answer
564 views
How to formulate 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 ...
10
votes
4answers
209 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 ...
29
votes
7answers
585 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 ...
12
votes
2answers
78 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, ...
12
votes
1answer
127 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 ...
14
votes
5answers
312 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?
13
votes
4answers
178 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 ...
16
votes
3answers
173 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 ...
13
votes
1answer
113 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)$$
12
votes
4answers
453 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 ...
24
votes
1answer
645 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$?
24
votes
2answers
686 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$?
