Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
15
questions
5
votes
1answer
138 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$ ...
5
votes
2answers
260 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 ...
8
votes
1answer
94 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 ...
9
votes
1answer
335 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 ...
9
votes
4answers
130 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 ...
27
votes
8answers
464 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
67 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, ...
11
votes
1answer
86 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 ...
8
votes
2answers
123 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?
11
votes
4answers
146 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
3answers
111 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 ...
11
votes
1answer
55 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)$$
6
votes
4answers
304 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 ...
13
votes
1answer
122 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 constraint $x y \leq b$?
17
votes
2answers
226 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$?
