# Tag Info

47

This scenario can be linearized by introducing a new binary variable $z$ which represents the value of $x y$. Notice that the product of $x$ and $y$ can only be non-zero if both of them equal one, thus $x = 0$ and/or $y = 0$ implies that $z$ must equal zero. $$z \leq x\\z \leq y$$ The only thing left is to force $z$ to equal one if the product of $x$ and $... 31 Suppose we can give a finite upper bound for$y$called$M$. Then this constraint can easily be linearized by using the so-called big$M$method. We introduce a new variable$z$that should take the same value as the product$x y$. Notice that the product which we model by$z$equals zero if$x = 0$but$z$can take any value between$0$and$M$if$x = 1$. ... 21 (I'm going to change$c$to$x$in my answer, since$c$is usually used for cost coefficients, not decision variables.) We want a set of constraints that enforces$X = \max\{x_1,x_2\}$. Define a new binary decision variable$y$, which will equal 1 if$x_1 > x_2$, will equal 0 if$x_1 < x_2$, and could equal either if$x_1 = x_2$. Let$M$be a constant ... 20 Alternatively, by observing that$|c \cdot x|= \max \{c^T x, -c^T x\}$, $$\min_x |c\cdot x| \text{ subject to } Ax \le b$$ can be rewritten as $$\min_x \max \{c^T x, -c^T x\} \text{ subject to } Ax \le b$$ which is equivalent to $$\min_{x, z} z$$ subject to $$z \ge c^Tx$$ $$z \ge -c^Tx$$ $$Ax \le b$$ which is a linear program. This ... 20 This can be handled as an MISOCP, Mixed-Integer Second Order Cone problem. The leading commercial MILP solvers can also handle MISOCP. Specifically, due to$x_{ij}$being binary,$x_{ij}^2 = x_{ij}$. Therefore, the left-hand side is the two-norm of the vector over$i \in I$having elements$\sqrt{a_{ij}} x_{ij}$. I don't know whether this is the best way ... 19 It is not possible to model the floor function as a constraint without modeling strict inequality. To prove this, I will show how the floor function can be used to model strict inequalities. Thanks to @Rob Pratt for showing a cleaner formulation that does not need a possibly large M. Suppose we can model the constraint$y=\lfloor x\rfloorfor any real ... 19 It is worth noting that this formulation can be derived somewhat automatically by writing the logical proposition in conjunctive normal form: \begin{align*} & z \iff x \wedge y \\ & \left(z \implies (x \wedge y)\right) \bigwedge \left((x \wedge y) \implies z\right) \\ & \left(\neg z \vee (x \wedge y)\right) \bigwedge \left(\neg(x \wedge y) \vee z\... 17 Here is a nice, succinct,and easy to understand reference for how to do all this and more. Answers to many future questions can be handled by referencing the appropriate section number in this document and then addressing any particular difficulties or concerns the questioner may have. FICO MIP formulations and linearizations Quick reference at https://www.... 16 Option 1: Submit as is to a solver which can globally optimize MIQPs having non-convex objective, and which might reformulate to a linearized MILP model under the hood. Such solvers include CPLEX, Gurobi 9.x, and BARON, among others. Option 2: Step 1 Linearize the products of binary variables, per How to linearize the product of two binary variables? . <... 16 First, some special cases: IfS=\{c\}$, fix$x=c$. If$S=\{0,1\}$, declare$x$to be binary. If$S=\{a,b\}\not=\{0,1\}$, introduce binary variable$y$and impose linear constraint$x=a(1-y)+by$. If$S=\{a,a+c,a+2c,\dots,a+kc\}$, introduce integer variable$y\in[0,k]$and impose linear constraint$x=a+cy$. (The previous bullet is the special case$c=b-a... 14 Maybe I am missing something but it looks like there is no need for a library: \begin{align} \sum_i \sum_j \sum_k x_{ji} y_{kj} cost(i,k)&=\sum_i \sum_j x_{ji} \sum_k y_{kj} cost(i,k) \end{align} Now since\sum_k y_{kj}=1$, exactly one row is 1, the others zero. We pick the best one: $$=\sum_i \sum_j x_{ji} \max_k cost(i,k)$$ Since$\sum_j x_{ji}=1$we ... 13 A rigorous way to look at this problem is to consider the polyhedra corresponding to your constraints (I linearized the 'max' for the second one): $$P_1 = \left\{(x_t,x_{t-1},y_{t-1},z_{t-1}): x_t = x_{t-1}+y_{t-1}-z_{t-1}, x_t \geq 0 \right\}$$ and $$P_2 = \left\{(x_t,x_{t-1},y_{t-1},z_{t-1}): x_t \geq x_{t-1}+y_{t-1}-z_{t-1}, x_t \geq 0 \right\}.$$ In ... 12 Unlike cases where one or both of the$x$and$y$are binary, you won't be able to truly (i.e. exactly) linearize this. https://stackoverflow.com/questions/49021401/how-to-linearize-the-product-of-two-float-variables goes through the approximation approach to this issue. 11 Basically the condition is saying,$z$must be between$x$and$y$, regardless of whether$x \le y$or$y \le x$. Here's a method that involves a new binary variable and a big-$M$. Let$w$a binary variable that equals 1 if$x < y: \begin{align} y - x & \le Mw \\ x - y & \le M(1-w) \end{align} So, ifx < y$then$w$must equal 1; if$...

11

I recommend Formulating Integer Linear Programs: A Rogues' Gallery: The article[1] is very accessible, clear, and has multiple examples of using binary variables to achieve logical constraints. Full citation below. [1] Gerald G. Brown, Robert F. Dell, (2007) Formulating Integer Linear Programs: A Rogues' Gallery. INFORMS Transactions on Education. 7(2):...

11

I recommend a third approach, similar to yours but linear: \begin{align} x + 1 - y &\le M_1 z \tag1 \\ y + 1 - x &\le M_2 (1-z) \tag2 \\ \end{align} Constraint $(1)$ enforces $z=0 \implies x + 1 \le y$. Constraint $(2)$ enforces $z=1 \implies y + 1 \le x$. This idea goes back at least to Manne, On the Job-Shop Scheduling Problem (1960). In some ...

11

You can model the logical implication $$Cx < d \implies \bigvee_{i=1}^m \left(a_i^T x \ge b_i\right)$$ by introducing $m+1$ binary variables $y_i$, where $i\in\{0,\dots,m\}$, and linear constraints \begin{align} d - Cx &\le M_0 y_0 \tag1\\ \sum_{i=1}^m y_i &\ge y_0 \tag2 \\ b_i - a_i^T x &\le M_i (1-y_i) &&\text{for $i\in\{1,\dots,m\}$}...

10

For real $x\in[l,u]$ and binary $b\in\{0,1\}$ the McCormick envelope gives you bounds on $w=xy$ \begin{align} lb & \leq w \leq ub,\\ ub+x-u& \leq w\leq x+lb-l. \end{align} By case analysis you can see that this is equal to $w=xb$, so you will indeed solve the problem.

10

The bigger the big-M is, more likely the numerical issues will happen with solvers. If you have right hand sides around $10^{10}$ and objective function coefficients in the range of $10^{-2}$, then solvers will have hard time dealing with such big range of values. And big-M's are the usual suspects in such situations. So smaller the big-M, tighter and ...

10

Welcome to OR.SE! If you're looking to enforce $$\max\limits_{pcj}X_{pwcj} \leq L_{wk}, \ \forall w,k$$ then simply using the constraint $$X_{pwcj} \leq L_{wk}, \ \forall p,w,c,j,k$$ will do the trick. This will ensure every value (including the maximum) will be at most $L_{wk}$. (If there's another dynamic you're looking to enforce, e.g., within a set of ...

10

You can solve the LP relaxation and round the resulting solution $x^*$, being careful to preserve the equality constraint. Then take $t=\max_c |\sum_n B_{n,c} x_n - d_c|$. There are lots of choices for rounding methods, but two natural choices are: Let $x = \lfloor x^* \rfloor$ and $R=M-\sum_n x_n$. In descending order of $x^*_n$, let $x_n = x_n+1$ for ...

10

Assuming that the $c_i$ and $q$ are all positive you may add one binary variable $y_i$ for every $i=1,\cdots,n$ then you may do \begin{align}c_i x_i &\geq q y_i \quad\forall i\\\sum_i y_i &\geq 1\end{align}

10

You can do this with no new variables. Let $S=\{k:c_k \ge q\}$ and add the constraint $\sum_{k\in S}x_k \ge 1$.

10

1. Your suggested approach : quadratic program Here are the details of your suggested approach. It results in a quadratic objective. Let binary variable $y_{i,b}$ indicate whether $A_i$ is in bucket $b$, where $b\in\{1,2,3\}$. Let $M_i$ be a (small) upper bound on $A_i$. The constraints are: \begin{align} \sum_{b=1}^3 y_{i,b} &= 1\\ 10 y_{i,1} + 8 y_{i,2}...

10

They are equivalent except when $x_{i,g}=x_{j,g}=0$, in which case the second linearization incorrectly contributes $-d_{ij}$ to the objective. Assuming $d_{ij} \ge 0$, I recommend a third linearization (relaxing $z$ and omitting two constraints from linearization 1): \begin{align} z_{ijg}&\ge x_{ig}+x_{jg}-1 \\ z_{ijg}&\ge 0 \end{align}

9

I often see people set $M$ to something like $10^{12}$, when the rest of the model is on the order of $10^2$, because they got the message that $M$ should be "a large constant". Reducing $M$ to something several orders of magnitude smaller then does have a noticeable impact on the run time. My point is: Once you know that you should should be careful about ...

9

As far as I know, there is no true way to linearize such constraints, as also stated in the answer given by Michael Trick. Let us therefore consider a piecewise linear approximation of the constraint $x_1 x_2 \geq b$ where $x_1, x_2 \in \mathbb R$ and $b$ is a given constant. The method discussed in this answer is introduced in the AIMMS Modelling Guide in ...

9

This is possible by introducing 2 new variables, $t_1,t_2$, and adding a few constraints: \begin{align} \min t_1+t_2 \quad \text{s.t.} \quad t_1-t_2 &= c\cdot x\\ t_1&\geq 0 \\ t_2&\geq 0 \\ Ax&\leq b \end{align} Why does this work? The main idea is that an optimal solution must set at least one of $t_1,t_2$ to $0$. First suppose $c\cdot ... 9 What about Mixed Integer Linear Programming Formulation Techniques, J.P. Vielma, SIAM Rev., 57(1), 3–57, 2015? 9 One common$c(x)$function is a "cost per distance unit (mile/km)" like$2/mile, which is just distance-dependent. My 2 cents for more realistic cost functions: For distance-dependent costs: Use a different distance function. If you are using linear distance (Euclidean or Manhattan), replace it with a better approximation like Haversine distance ...

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