8 votes
Accepted

Can we linearize the division of a binary variable by a continuous variable?

You want to linearize \begin{align} z_r &= \frac{x_{ry}}{\sum_s d_s x_{sy}} &&\text{for all $r$ and $y$} \tag1 \\ \sum_s x_{sy} &= 1 &&\text{for all $y$} \tag2 \end{align} If $...
RobPratt's user avatar
  • 32k
7 votes
Accepted

If-then condition formulation to avoid variable multiplication

Something like: $$\begin{align} & c_i \le x_i + M(1-y_i)\\ & c_i \le My_i \end{align}$$ $M$ can be interpreted as an upperbound on $c_i$. If you don't like the big-$M$'s, consider using ...
Erwin Kalvelagen's user avatar
7 votes
Accepted

How to treat a system of bilinear constraints

You want to enforce $X(k) = 0 \implies R(k) = 0$ and $X(k) = 1 \implies R(k) \le G(k)$. You can use indicator constraints for that. Alternatively, a straightforward big-M formulation yields \begin{...
RobPratt's user avatar
  • 32k
5 votes
Accepted

Linearize a product of binary variables

Introduce bounded variable $y_{jk}$ to represent $\sum_{i\in I} x_{ijk} N_{ij} a_{ijk}$, and minimize $\sum_{j\in J}\sum_{k\in K} y_{jk}$. Now enforce $x_{ijk}=1 \implies y_{jk} = N_{ij} a_{ijk}$, by ...
RobPratt's user avatar
  • 32k
5 votes
Accepted

Linearize sum of continuous and boolean variable

If $M$ is a (small) upper bound on $x$, introduce a binary variable $z$ and big-M constraint $x \le M z$. The idea is that $x>0$ implies $z=1$. Now use $B z$ in the objective.
RobPratt's user avatar
  • 32k
4 votes
Accepted

Reformulating to locate the second largest decision variable of a set of decision variables

To get the second largest variable when all are nonnegative and at most two can be nonzero, just take the sum of all of them and subtract the largest.
RobPratt's user avatar
  • 32k
4 votes
Accepted

Maximizing a Ratio/Percent

CVXPY makes this easy to do, using its disciplined quasiconvex programming (DQCP) capability. An example is provided at https://www.cvxpy.org/examples/dqcp/concave_fractional_function.html . ...
Mark L. Stone's user avatar
4 votes
Accepted

Switching of decision variables to be equal to a certain decision variable according to a binary (indicator) variable

$$ x \le z + M(1-\beta) \\ x \ge z - M(1-\beta) \\ x' \le z + M\beta \\ x' \ge z - M\beta \\ $$ If $\beta=1$, we have $$ x \le z \\ x \ge z \\ x' \le z + M \\ x' \ge z - M \\ $$ which leads to $x=z$ ...
Kuifje's user avatar
  • 13.3k
3 votes

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?

If well understood, w1, w2, w3, and Z are some continuous variables in your mathematical model, while k is a constant. If the functions f1, f2, f3 involved in constraint #2 are continuous and ...
Hexaly's user avatar
  • 2,976
3 votes
Accepted

Linearize piecewise function without big-M constraints

I don't see or remember a way around the big-M constraints. Thankfully they are not that hard to write. Or you may use indicator constraints which are even simpler. We add new binary variables, and ...
Ggouvine's user avatar
  • 1,877
3 votes
Accepted

Min-convex function as constraint

In case $y$ belongs to a finite domain (e.g., if binary), you can split your difficult constraint into multiple simpler (one for each element of the domain) using: $$ Ax \leq \min_y g(x,y) \quad\...
Henrik Alsing Friberg's user avatar
3 votes

Piecewise linear and global optimization

I might be missing something here (and by "might be" I mean "probably am"), but at least for the case of $x_i \in [0,1]$ you might be able to get solutions via "brute force&...
prubin's user avatar
  • 39.1k
3 votes
Accepted

Piecewise linear and global optimization

As far as I can see there is no exact convex reformulation for this, unless someone else can think of a nice trick. Constraint 1 can actually be convexified for certain ranges of $q_i$ as these ...
Nikos Kazazakis's user avatar
2 votes
Accepted

Formulating indicator constraint set

Do you mean $i$ and $j$ instead of $v$ and $v’$? If so, the constraints you want are $\alpha_{i,j}\le A_i$ and $\alpha_{i,j}\le A_j$.
RobPratt's user avatar
  • 32k
2 votes

Change the objective function formula change the complexity of a linear program?

Draw a unit circle around the origin in $\mathbb{R}^2$ and consider the quarter of it in the first (nonnegative) quadrant. Now pick a large number of points on the circle and make them, along with $(0,...
prubin's user avatar
  • 39.1k
2 votes

DCP formulation of sum of nonconvex and convex functions

For all $c>0$ the function of one variable $$g(x)=c^{x/L}\cdot L - \ln(c)\cdot x=\exp(\ln(c)x/L)\cdot L-\ln(c)\cdot x$$ is convex increasing on $x\geq 0$ (derivative check) and DCP representable (...
Michal Adamaszek's user avatar
2 votes

Linearize a product of binary variables

If you do it, you will force a constraint that maybe is not true. Are you sure that constraint ($\displaystyle \sum_{i \in I} x_{ijk}=1, \forall j,k$) is always true? If you are, so it's a correct ...
Judecir's user avatar
  • 21
2 votes
Accepted

Automatic Reformulation Tools For AML Programs

With SAS, for both automated linearization and automated conic transformation, you can use the EXPAND statement in PROC OPTMODEL to see the transformed model. The syntax is: ...
RobPratt's user avatar
  • 32k
1 vote

Converting a function composing of multipe pieces into a linear equation

I assume here that the $\beta_j$ are all nonnegative. You can linearize the definition of $b_1$ as follows: $$b_1 \le \beta_1 x_1$$ $$b_1 \le \beta_1 x_2$$ $$b_1 \ge \beta_1 (x_1 + x_2 - 1).$$ The ...
prubin's user avatar
  • 39.1k
1 vote
Accepted

Change the objective function formula change the complexity of a linear program?

It is not uncommon that with different objective functions, there are different complexity that comes with the specific problem. For example, in the scheduling theory, it is often of interest to ...
A.Omidi's user avatar
  • 8,892
1 vote

Loglog transformation of optimization problem, how can the solution be equal to the nontransformed counterpart?

If you consider only one $t$, you can ignore the positive constant multiplier because optimizing $y_t$ is equivalent to optimizing $k_t y_t$ (or its log) for positive constant $k_t$. But it sounds ...
RobPratt's user avatar
  • 32k
1 vote

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?

If you are willing to take an approximate solution (no guarantee of optimality), it should be fairly easy to apply any of a number of metaheuristics to your problem. It would be helpful if, for fixed $...
prubin's user avatar
  • 39.1k

Only top scored, non community-wiki answers of a minimum length are eligible