9
This can not be formulated as a linear programming problem. We need extra binary variables and end up with a MIP.
First we do:
$$ a > b \Longleftrightarrow \delta = 1$$
This can be formulated as:
$$\begin{align}
&a \ge b + 0.001 - M(1-\delta)\\
&a \le b + M\delta\\
&\delta \in \{0,1\}
\end{align}$$
(in practice I would drop the $0....
5
Yes, one way is to introduce two new variables $t_1$and $t_2$ and maximize $t_1+t_2$with the constraints $f_1(x,y) \geq t_1$ and $f_2(x,z) \geq t_2$. Now multiply with denominators and you will have polynomials of $x,y$ and $t$ in your constraints.
These nonlinear constraints can all be linearized using standard strategies. For instance, $ab$ where $a$ ...
4
CVXGEN only addresses LPs and convex QPs. So I am guessing you are interested in convex Mixed Integer QPs (MIQPs), or perhaps MILPs. Those are addressed, by among others, GUROBI, CPLEX, and MOSEK, all of which also handle the more general Mixed Integer Second Order Cone Problems (MISOCPs).
Once you get into the mixed integer realm, all bets are off ...
3
Internally, a solver is probably going to treat each of your SOS1 constraints a lot like a binary variable -- basically, branch on $w_i$ and, in the $w_i = 1$ branch, force $v_i = 0$. The good news is that you avoid $M$; the bad news is that I don't think the solver has much information with which to assess which SOS1 constraint to branch on at a given node.
...
3
Note that
$$\begin{array}{rl} x_1 = 0 \lor x_1 \geq 10 &\equiv (x_1 \geq 0 \land x_1 \leq 0) \lor x_1 \geq 10\\\\ &\equiv x_1 \geq 0 \land (x_1 \leq 0 \lor x_1 \geq 10)\end{array}$$
We can handle the disjunction $x_1 \leq 0 \lor x_1 \geq 10$ using the Big M method. We introduce binary variables $z_1, z_2 \in \{0,1\}$ such that $z_1 + z_2 = 1$, i.e.,...
3
Using an extra binary variable $\delta$ we can write:
\begin{align} & 10 \delta \le x_1 \le 300 \delta \\
&\delta \in \{0,1\}
\end{align}
$x_1$ is called a semi-continuous variable and some solvers support this directly without the need for extra binary variables.
3
Here are some hints:
Linearize $z_{i,j}=x_i y_j$ and you can solve this as a standard MIP (Mixed Integer Programming) problem.
If the problem is convex use a standard MIQP (Mixed Integer Quadratic Programming) solver (e.g. Cplex, Gurobi)
If the problem is non-convex use a global solver (Cplex has a global MIQP solver, some other global MINLP solvers are ...
3
$$\begin{align} & 350 \cdot \delta \le x \le 349.99 + \delta\cdot (U-349.99)\\
&\delta \in \{0,1\}\\
& 0 \le x \le U
\end{align} $$
3
Yes, from the generic $x^TR^TRx \leq c^Tc+b$ being SOCP representable as $\left|\left|\begin{matrix}2Rx\\1-(c^Tx+b)\end{matrix}\right|\right|\leq 1+c^Tx+b$
3
When I implemented the model (using AMPL/CPLEX), I got the same results as you did.
However, note that the given solution is not feasible for the given model. E.g., for the first constraint ($gt_1+gt_2+def+ghu = 1200$), the sum of the variables from the given solution is $388$, not $1200$ as required. This tells us that either the given model is wrong or ...
3
I gave that talk. The term "slice" for iterating over a subset of indicies based on an outer set of indicies was originally invented by Robert Fourer for AMPL (AFAIK). I believe this term appears in the AMPL documentation, and I'll swear on a stack of Bibles that I've heard it used this way both by Bob himself and by senior Gurobi people. At any rate, the ...
3
Your problem is called $P\mid\text{prec}\mid C_\text{max}$ in the notation of Graham et al. (1979). You can find MIP models and some computational results in Wang, Parallel machine scheduling with precedence constraints.
2
Again, it is in my opinion impossible to do this as an LP. However we can try a MIP formulation.
Let's use the following notation:
$x_{i,t} \in \{0,1\}$ is assigning person $i$ to weekend $t$
$y_{i,j,t} \in \{0,1\}$ is assigning pair $(i,j)$ to weekend $t$. There are 36 pairs possible and that also dictates our planning window $t$.
The obvious constraints ...
2
Let $z*$ be the optimal solution of the integer problem, $z_{Lin}$ be the solution of the linear relaxation, and $z_{Lag}$ be the solution of the Lagrangian relaxation. For a minimization problem, the following inequalities hold:
$$
z*\ge z_{Lag} \ge z_{Lin}
$$
In other words, the Lagrangian relaxation is tighter than the Linear relaxation. $z_{Lag}$ and $...
2
Yes, it can easily be cast as a mixed-integer quadratic program (assuming you know how to model implications with binary variables)
Introduce a binary $\delta_i$to represent if $y_i$ has same sign as $X_i \beta$, and variable $z_i$ to represent the cost for the residual.
You then add implications that $\delta_i$ implies $X_i \beta \geq 0$ if $y_i\geq 0$ or ...
2
If you are asking whether additional equation constraints increase difficulty (as opposed to whether equations are any better or worse than inequalities), the answer is a resounding "maybe". On the one hand, more equations may mean more rows in the constraint matrix, which may make decomposition of the matrix, updates to the basis matrix etc. slower due to ...
2
First question would be "Unique w.r.t. to the continuous variables or the discrete variables?".
We can fix the discrete variables and then look at the problem as an LP. Look at the reduced cost and duals to see if there is dual degeneracy. (In practice that means resolving as an LP as the MIP duals are no good: bounds have changed in the branch-and-bound ...
2
The condition $$x \in [a,b] \Rightarrow z=1$$
can be reformulated as:
$$z=0 \Rightarrow x<a \text{ or } x>b$$
This can be linearized using standard tools:
$$\begin{align}
& x \le a - 0.001 + M\delta + Mz\\
& x \ge b + 0.001 - M(1-\delta) - Mz\\
&\delta \in \{0,1\}
\end{align}
$$
2
The key is that $W$ is a possible set of all "parents" (sources linked to) $u$. So the "parent sets" of nodes 1 through 4 are, respectively, {4, 5} (parents of 1), {1, 6}, {2, 7}, and {3, 8}. For the set $C = \{1,\dots,4\}$, no node in $C$ has a parent set disjoint from $C$; so for each $u\in C$ the inner summand is over an empty set of terms, and hence is ...
2
Effectively $y_i$ implies $q_i \leq a$, which is $q_i \leq a \cdot y_i + M(1-y_i)$ where $M$ is your favorite sufficiently-large small-M constant (i.e, what normally but dangerously is called a big-M constant).
2
I'm not sure that "equivalence" between optimization models is all that well defined. If we think of a problem instance as the combination of a model (with symbolic parameters) and values for the parameters (data), then one might say two models are equivalent for a problem if, given the same data, any optimal solution to either model is also optimal in the ...
2
Make a variable change $y_i = x_i^{-1}$. You now have a model with linear constraints, but with an objective which is a sum of squared inverses $y_i^{-2}$. To handle these, introduce a new variable $z_i$ with $y_i^{-1} \leq z_i$ which you model as SOCPs using the answer in your other post, and your objective will be a function of $z_i^2$. At that point, ...
2
You didn't specify whether or not it is allowed for vessel to visit several bases in a round before returning to the main base. I assumed this was probably not the case. Otherwise, some minor modifications have to be made to the answer.
Let $d_j$ denote the distance from base $j$ to the main base. Moreover, let $p_{ijk}$ denote the number of people taken ...
2
You can always avoid the dual subproblem being infeasible by adding bounds to the primal variables (which, if you’re modeling something realistic, is always possible).
Suppose you have the LP
$$
\begin{array}{rl}
\max\ & c^Tx \\
\text{s.t.}\ & Ax\leqslant{b}
\end{array}
$$
with corresponding dual
$$
\begin{array}{rl}
\min\ & b^Ty \\
\text{s.t....
2
A slightly better answer to this (better in the sense is that it gives the convex hull) is to use the 8 inequalities:
$$ h \leq z$$
$$h \leq T x$$
$$h \leq Ty$$
$$x \leq 1$$
$$y \leq 1$$
$$z \leq T$$
$$h \geq Tx + Ty + z - 2T$$
$$h \geq 0$$
2
I suppose your model is not correct. Solving the model with an LP-solver yields the solution $x=75000$ and $y=25000$. I assume, however, that for every frame you also need a shaft. Hence, you need to add the following constraint:
$$x=y$$
Solving the problem with the additional constraint yields the solution $x=y=45000$. Please note that luckily the number ...
2
It's really not surprising that adding even one constraint can make a problem much harder. Consider a problem with nonnegative variables where $(0,\ldots,0)$ is feasible and the objective (to be minimized) has positive coefficients. Then
$(0,\ldots,0)$ is the unique optimal solution, and your MIP solver should find it
almost instantly. But add the ...
2
The problem you describe is a non-convex binary program. The non-convexity comes from the first and second set of constraints: In $x_i \le \sum_{j,k} a_{ijk} x_j y_k\ $ two decision variables $x_j$ and $y_k$ are multiplied by each other. This will make the problem very hard to solve for most solvers. However, there is a way to turn your problem into a convex ...
2
I found a valid answer:
Introduce new decision variables $y_1,...,y_{10}$ with the constraints:
$y_1,...,y_{10}$ are binary decision variables
$x_i \geq 10,000*y_i, i = 1,2,...,10$
Rewrite divestment constraint as $x_i \leq 25,000*y_i, i = 1,2,...,10$
2
With the MATLAB Toolbox YALMIP (disclaimer, developed by me), it would be
x = sdpvar(n,1);
z = sdpvar(m,1);
y = binvar(n,1);
Model = [-z <= A*x-b <= z, sum(x) == 1, x >= 0, sum(y)==5, 0<=x<=y];
Objective = sum(z);
optimize(Model,objective)
value(x)
If you have an integer solver installed, such as intlinprog, it will automatically be used. If ...
Only top voted, non community-wiki answers of a minimum length are eligible
