Search Results

You can solve the problem via dynamic programming. For $n\in\{1,\dots,t\}$, let $V(n)$ be the minimum expected number of steps starting from $n$. Then $V(1)=0$ and otherwise $$V(n) = 1+\min\left(\fr …

This problem is a special case of the quadratic traveling salesman problem in which the cost for traversing three consecutive nodes that have no turn is $1$ and the cost is $0$ otherwise. Because you …

This is the transportation problem in a bipartite network, with a supply of $1$ at each $j$ node and a demand of $t_i$ at demand node $i$. The problem can be solved via linear programming, a minimum- …

For binary $P$, we have $\min\{P_{k,i},P_{l,j}\} = P_{k,i} P_{l,j}$. In your linearization, you have introduced $r_{i,k,l,j}$ to represent this product. Because of the linear constraints $$\sum_k P_ …

This idea is the essence of Dantzig-Wolfe decomposition, which is an exact algorithm for solving linear and mixed integer linear programming problems with such block-angular structure. The $\le 0$ co …

The nonlinear constraint $$(L_{ij} - D_{ik})(L_{ik} - D_{ij}) \le 0$$ is a disjunction: $$\left(L_{ij} - D_{ik} \ge 0 \wedge L_{ik} - D_{ij} \le 0\right) \bigvee \left(L_{ij} - D_{ik} \le 0 \wedge L_{ …

As @ManfredWeis noted, the objective is equivalent to minimizing $\sum_{i=1}^K \frac{x_i^2}{y_i}$. You can reformulate this as a (convex) mixed integer second-order cone programming (MISOCP) problem …

Given $n \times n$ matrix $M$, you want to find $A,B,C \subset \{1,\dots,n\}$ to maximize $$\sum\limits_{i \in A, j \in C} m_{ij} - \sum\limits_{i \in B, j \in C} m_{ij}$$ subject to $A < B < C$ and $ …

If $x_j \le u_j$ for some constant $u_j$, you can introduce a binary variable $y_j$, nonnegative variable $z_j$, and linear constraints: \begin{align} x_j &\le u_j y_j \\ d_j x_j + t_j - z_j &\le t_j( …

You can formulate this as a set covering problem. For each circle $j$, define a binary variable $x_j$ that indicates whether circle $j$ is selected. Let $C_i$ be the set of circles that intersect li …

You can formulate this as a multicommodity flow problem and solve it via linear programming. The commodities are $K = V_a \times V_b$. Let $A$ be the arc set, with one arc in each direction for each …

Yes. Search for combinatorial Benders decomposition or logic-based Benders decomposition. In particular, Benders feasibility cuts for a binary master problem are “no-good” cuts of the form $$\sum_{j …

Yes, lower and upper bounds on variables can be enforced via explicit constraints. In practice, however, bounds are handled implicitly because the explicit constraints determine the size of the basis …

You could specialize Dantzig-Wolfe by solving the subproblems (one per $i$) with an oracle other than LP. If the constraint $\mathbf{b}_i^\top \mathbf{x}_i \le 0$ weren't there, you could enumerate t …

Not sure about your conic problem, but for LP you have the roles of $\min$ and $\max$ reversed.