Questions tagged [reformulation-linearization]
The reformulation-linearization tag has no usage guidance.
20
questions
2
votes
1
answer
195
views
Linearize piecewise function without big-M constraints
I have been attempting to solve a maximization problem where there is a piecewise function in the objective. Something like:
$\sum_{n}(1-prob_{n})(1+x_n)$
Where $prob_{n} = $
\begin{cases}
0.25,...
- 67
2
votes
0
answers
33
views
Addressing Variable Multiplication in Constrained Infinity-Norm Maximization with Hypercube & Polyhedron Constraints
I am reaching out to this knowledgeable community for assistance with a complex optimization problem that I have been investigating. Here is the formulation of the problem I'm addressing:
$$\tag{1}
\...
- 151
1
vote
0
answers
34
views
Convex quadratic maximization over cartesian product of simplices
Suppose we are maximizing $f(x^1,\ldots,x^t)= \begin{bmatrix}{x^1}^\top & \ldots & {x^t}^\top \end{bmatrix}^\top Q \begin{bmatrix}{x^1}^\top & \ldots & {x^t}^\top \end{bmatrix}$ ...
- 3,980
0
votes
1
answer
59
views
Min-convex function as constraint
I have a constraint that is as follows:
$$
Ax - f(x) \leq 0
$$
where $f(x)=min_y(g(x,y))$. Which is convex. I can even get the gradient in $x$. How can I reformulate my constraint? or what ...
- 507
2
votes
1
answer
45
views
Automatic Reformulation Tools For AML Programs
Are there any tools to transform programs written in an algebraic modeling language like GAMS,AMPL,... into a different formulation.
E.g. there is a quadratic constraint $\sum_j b_i b_j = N, b \in \...
- 153
2
votes
1
answer
137
views
Loglog transformation of optimization problem, how can the solution be equal to the nontransformed counterpart?
Consider the following two functions:
$$y_t = e^{lt} \cdot e^{st} \cdot \prod_{p=0}^{n} x_{tp}^{b_{tp}}\tag1$$
Where $e^{lt}$ captures the trend, $e^{st}$ captures the seasonality and $x_{tp}$ is our ...
5
votes
1
answer
385
views
Can we linearize the division of a binary variable by a continuous variable?
I'm trying to solve an MINLP problem where the following division term is appearing in the objective:
$$z_r = \frac{x_{ry}}{\sum_r d_r x_{ry}}, \forall r, y,$$ where $x_{ry}$ is a 2D binary variable ...
3
votes
1
answer
177
views
If-then condition formulation to avoid variable multiplication
I'm trying to formulate the following logic:
If $y_i =1$, then $c_i \leq x_i$
If $y_i =0$, then $c_i \leq 0$
Where $y_i$, $c_i$, and $x_i$ are decision variables.
The easy way would be to write:
$$c_i ...
- 169
2
votes
2
answers
311
views
Change the objective function formula change the complexity of a linear program?
I have a linear program, where I can use it with the same constraint to minimize objective 1 or minimize objective 2. I noted that when I use the formula of objective 2 the problem can be solved with ...
- 335
4
votes
1
answer
155
views
DCP formulation of sum of nonconvex and convex functions
I am trying to find a DCP formulation for the following convex objective function (using CVXPY):
Let $x$ be the $N$-dimensional vector variable on which we optimize on, $c$ be a known scalar value ...
- 41
2
votes
2
answers
314
views
Linearize a product of binary variables
I have a function to minimize which has the following term $$\sum_{i\in I}\sum_{j\in J}\sum_{k\in K}x_{ijk}N_{ij}a_{ijk},$$ where the variables are $x_{ijk}\in\{0,1\}$, $a_{ijk}$ are given as input ...
- 381
6
votes
1
answer
208
views
How to treat a system of bilinear constraints
A model contains constraints of the following form
$R(k) \leq X(k) G(k)$
where $X(k)$ binary and $G(k)$, $R(k)$ non-negative variables.
The index $k$ runs from $1$ to $50$.
I linearise the equations ...
- 2,180
5
votes
2
answers
293
views
Piecewise linear and global optimization
I am new to OR, and apologies if my mathematical notation is not clear. I have tried my best to keep it concise and given an explanation with numerical data.
I would like to understand:
Can this ...
- 81
4
votes
2
answers
253
views
How to deal with an optimization problem that have a sum of nonlinear functions of Z as a constraint when Z is the quantity to be minimized?
I have to minimize a quantity $Z$ subject to the following constraints:
$$ w_1 + w_2 + w_3 = 1 \tag{1}$$
$$ \frac{f_1(w_1 Z) + f_2(w_2 Z) + f_3(w_3 Z)}{Z} \ge k \tag{2}$$
where $k$ is a known ...
- 141
7
votes
1
answer
281
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
4
votes
1
answer
260
views
Switching of decision variables to be equal to a certain decision variable according to a binary (indicator) variable
I would like to seek some advice on modeling the following:
I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is to be equated to a third ...
- 707
2
votes
1
answer
104
views
Formulating indicator constraint set
I am having difficulty formulating the indicator constraints for the following:
Consider a set of $A_{n}$ decision variables such that $A_{1},A_{2},⋯,A_{n}<A$. While all of them are integers that ...
- 707
2
votes
1
answer
66
views
Reformulating to locate the second largest decision variable of a set of decision variables
Consider a set of $A_{vn}$ decision variables such that $A_{v1},A_{v2},\cdots,A_{vn}<A$. While this is the standard formulation finding the maximum value of $A_{vn}$, I would also like to find the ...
- 707
2
votes
1
answer
245
views
Linearize sum of continuous and boolean variable
For maximizing the objective function $\sum_i{d_i y_i}+ A x - B \cdot \mathbb{I}_{x>0}$, how can I linearize $ A x - B \cdot \mathbb{I}_{x>0}$ term where $d_i, A$ and $B$ are positive constants ...
- 123
6
votes
0
answers
132
views
Cases where RLT/SDP relaxation does not work well with standard quadratic optimization
(For people who don't know what RLT is): I am maximizing an indefinite quadratic function over a standard simplex, i.e., the standard quadratic optimization problem. A well-known approach is to relax ...
- 3,980