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 …

It certainly depends on both $n$ and $r$. Here are plots of $t^*(n,r)$ for $n\in\{2,3,4,5\}$ and $r\in\{0.01,0.02,\dots,0.99\}$, obtained via mixed integer linear programming. $$n=2$$ $$n=3$$ $$n …

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 $ …

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 …

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 …

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 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- …

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 …

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 …

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 …

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

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 doesn't answer the NP-hardness, but you can solve the problem via integer linear programming as follows. For $(i,j)\in E$, let binary decision variable $x_{i,j}$ represent the flow from $i$ to $ …

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 …

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_{ …