New answers tagged

0

The cases of identifying the regions separated by the lines (y = constant or x = constant) are too trivial to consider. Hence, we can assume the slanted line is $L : y = mx + c$ with $m \ne 0$. Re-write the equation as $L : x = \dfrac {1}{m}y + d$; where $d = \dfrac {c}{m}$. Let D be another constant such that $D \gt d$. Then, the point $(D, 0)$ is NOT ...


1

The disaggregated cuts $t_i \le \mu_i$ will yield a tighter feasible region (and hence a better lower bound) than the aggregated cut $\sum_i t_i \le \sum_i \mu_i$, but it is worth trying both ways.


0

If $B=[b_1,\ldots,b_m]$ where $b_i$ are the columns of $B$ and $e_i$ are the columns of the identity $I_m$, you can write $$ \|AB-I_m\|_F^2=\sum_{i=1}^m\|Ab_i-e_i\|_2^2, $$ so the Frobenius norm minimization can be turned into $m$ independent minimizations $$ \min_{B}\|AB-I_m\|_F^2=\sum_{i=1}^m\min_{b_i}\|Ab_i-e_i\|_2^2. $$ Now we have $m$ linear least ...


0

Let $x_i$ be a binary variable that takes value $1$ if and only if element $i$ from $X$ is selected, and likewise with $y_j$, $Y$. Let $\hat{x}$ and $\hat{y}$ be the given items. So you are looking for a pair $(x_i,y_j)$ such that $i \times j \le \hat{x} \times \hat{y}$. You can minimize a dummy objective function (e.g., $0$) subject to : $$ ix_ij y_j \...


0

You can do it with one additional binary variable $y$: $$\sum_{i=1}^5 x_i = 1 + 2y.$$


0

It has just occurred to me that I can achieve my goal with a penalty on their product. $$ Penalty = M\cdot(-x_2^- \times x_1^+) $$ Where $M$ is large enough. Doesn't this qualify as a quadratic cost term?


1

The second row is multiplied by 3, then the third row is subtracted from it. This is equally valid.


0

I've managed to resolve the problem with the help of generalized transportation problem: $min \sum c_{i,j}x_{i,j}\\ \sum_{i} x_{i,j}=a_i \\ \sum_{j} x_{i,j}=b_j \\ x_{i,j} \geq 0 $ Where, of course, $\sum_{i} a_i = \sum_{j} b_j\\$. In general case this problem has constraint matrix with rank $2n-1$ where no variables equal to 0, because in this case ...


1

The second part (not returning to base) can be finessed by adding a zero-length arc from every node other than base back to the base node. So wherever you end up last, you return to base at no cost. As for revisiting nodes, if you know in advance how many times each node must be visited, and if there are no time windows or other constraints on when you ...


0

Let $S\subseteq \mathbb{R}[x_1,\ldots,x_n]$ be the set of multilinear polynomials with degree at most $3$ on $n$ variables. To expand on my comment, a polynomial $f\in S$ (or more generally, any multilinear polynomial) is nonnegative (positive) on $[0,1]^n$ if and only if it is nonnegative (positive) on $\{0,1\}^n$, so it suffices to check $2^n$ points. Note ...


0

If we simply solve the initial system of four linear equations in four unknowns, its unique solution is this: $$ x_1 = -10.1019 \\ x_2 = -10.3069 \\ x_3 = 15.7201 \\ x_4 = 5.6887 $$ This solutions is not nonnegative (forgive the use of a double negative!), and so is unsatisfactory. There is a natural 3D geometric interpretation of the system, arising from ...


1

As you have noted, this (implicit) feasibility region on $y$ can be formulated as the projection (via $y=cx$) of an explicit feasibility region in $x$. I had to deal with this problem myself recently. One method, as people have commented, is to obtain the vertices from your half-space representation and then project these down; the convex hull of these ...


1

Firstly we define the variables: $x_1$: Multiple of pancake recipe, $x_2$: Multiple of waffle recipe. We want to maximize the total amount of serves. Therefore the objective function is $$\text{max} \ \ 6x_1+5x_2$$ Next we have several constraints for the ingredients. For instance, that you have 24 cups of Bisquick. The corresponding constraint is $$3x_1+...


0

Suppose $Y$ has upper bound $U$. Introduce binary variables $z_1, z_2, z_3$ and linear constraints: \begin{equation} z_1+z_2+z_3 =1\\ 0z_1+k z_2+(k+1)z_3 \le Y \le (k-1)z_1+k z_2+Uz_3\\ \phi = \beta z_2 \end{equation} To check the correctness, note the three possibilities for $z=(z_1,z_2,z_3)$: If $z=(1,0,0)$ then $0 \le Y \le k-1$ and $\phi=0$. If $z=(0,1,...


1

This blog post demonstrates one approach that uses mixed integer linear programming: https://blogs.sas.com/content/operations/2014/11/10/do-you-have-an-uncle-louie-optimal-wedding-seat-assignments/


1

Hint Since $A$ is a $m \times n$ matrix, with $m<n$, a Singular Values Decomposition of it will represent a first useful step. In particular you can determine the null-space of it, i.e. the set of vectors $v_1, v_2, \cdots, v_{n-m}$ (or more) for which $$ {\bf A}\,{\bf v}_{\,k} = {\bf 0}\quad \Rightarrow \quad {\bf A}\,\sum\limits_k {\lambda _{\,k} } ...


0

If the problem is an actual numerical problem for which you have a matrix A, then you can set this problem up as a semidefinite program (see Convex Optimization by Boyd and Vandenberghe). Such a system can be solved by good convex solvers like cvx, or sedumi and yalmip in Matlab, or Pyopt in python. In this case, since $I$ is the only inequality, this is ...


0

The number of zeros represents indeed the number of dimension of the optimal solution. I had a problem within my resolution of the problem, that's why I got a $$ \lambda \equiv 0 $$ In any other case, that shoudln't be the case, unless the whole initial set is a solution to the problem . E.G. : an optimisation problem where the objective function is $$ \...


1

The following is a proof for the only if side of your problem, which requires a good understanding of the duality theorems in linear programming, espeically the complementary slackness thoerem. Proof$\;$ Suppose $F$ is a face of $P$ defined by $c^Tx\le \delta$, i.e., $F=\{x\in P|c^Tx =\delta\}$. Note that $F$ is the set of optimal solutions for linear ...


2

Z=50x+275y+175z where x,y,z are inventory of the product required by ware house 1,2,3, now coming to equation 5x+8y+4z greater than equal to 100,equation 2 7x+9y+3z greater then equal to 250,equation 3-6x+10y+11z greater than 150 then you can make graph and find the value


Top 50 recent answers are included