# Tag Info

3

The transformation you want is called node splitting. Replace node $i$ with two nodes $i'$ and $i''$, where all incoming arcs to node $i$ instead arrive at node $i'$ and all outgoing arcs from node $i$ instead leave node $i''$. Also introduce a directed arc from $i'$ to $i''$ with capacity $1$.

5

Your intuition that you need to adjust $b_i$ is correct, but you also need to adjust $u_{i,j}$. To derive the desired MCF, perform a change of variables $y_{i,j}=x_{i,j}-\ell_{i,j}$ (so that the lower bound constraints become $y_{i,j} \ge 0$). That is, replace $x_{i,j}$ with $y_{i,j}+\ell_{i,j}$ throughout your constraints, and rewrite into the form of MCF....

2

You can minimize any convex function $f$ over $X$ using the Frank-Wolfe algorithm. In particular, this will give you valid dual bounds at every iteration. [Note: the FW algorithm assumes that you can minimize any linear function over $X$] Consider the problem \begin{align} Z^{*} = &\min_{x}\quad\|x - r\|^{2}\\ &\text{s.t.} \quad x \in X \end{align} ...

11

No, state of the art LP solvers do not do that. They do bring the problem into a computational form that suits the algorithm used. Note that in the case of simplex algorithms, modern solvers use the revised simplex method with lower and upper bounds that does not require standard form. You can get an idea of the computation forms used from "...

3

Based on their manual, as I understood, Gurobi does not reformat the equality constraint because the equality expression can immediately be added to the list of constraints. They use more clever ways to handle these situations but as a black-box commercial solver, they don't share these approaches with the public and you would never know those techniques. ...

3

If you are interested in a model-and-run approach, maybe you can have a look at LocalSolver. An example model for basic k-means is given here. LocalSolver finds near-optimal solutions in seconds until 10,000 points to be clustered. Instead of the classical Boolean modeling approach, using so-called set variables makes the model natural to read and compact in ...

3

To solve this using a p-center formulation, you could use this base model: \begin{align} P: \min&\quad \sum_{i,j\in I}c_{ij}x_{ij}&\\ \text{s.t.}&\quad \sum_{j\in I} x_{ij} =1 & \forall i\in I\\ &\quad \sum_{i\in I}x_{ii}\leq maxClusters &\\ &\quad x_{ij}\leq x_{jj} &\forall i,j\in I\\ &\quad u\geq \sum_{i\in I}x_{ij} &...

3

I'm not familiar with agglomarative clustering, but in general terms you are dealing with a bicriterion optimization problem. One criterion has to do with the "affinities" of points in a cluster. You may want to maximize (?) something to do with the pairwise weights. That might be the sum of the weights of all pairs sharing a cluster, or the ...

5

Introduce a binary variable $y_{i,j}$ and linear constraints \begin{align} x_{i,j} &\le M y_{i,j} \tag1 \\ y_{i,j} + y_{j,i} &\le 1 \tag2 \end{align} Constraint $(1)$ enforces $x_{i,j} > 0 \implies y_{i,j} = 1$. Constraint $(2)$ enforces $y_{i,j} = 1 \implies y_{j,i} = 0$. Constraint $(1)$ (with the roles of $i$ and $j$ interchanged) enforces $y_{... 6 The following isn't meant to be exhaustive. It usually depends on the structure of the matrix because that impacts the way you choose it. In general there are sparse variants for many of the general matrix decompositions you see LU, QR, SVD and what not. There are also sparse Kyrlov methods such as the shifted Block Lanczos method. If it isn't symmetric then ... 2 coeffs = [120, 600, 800, 200] y_target = 165120 rangeStore = [] bound_dic = {0:[0,15],1:[15,60],2:[60,150],3:[150,300]} model = ConcreteModel() model.ind = set(bound_dic.keys()) def b_rule(model, i): return (bound_dic[i][0], bound_dic[i][1]) model.x = Var(model.ind, bounds = b_rule) model.weight = Constraint(expr = sum(coeffs[i] * model.x[i] for i ... 4 As Sune noted, the$\epsilon$-constraint method is not comparable to what CPLEX does, since it finds all Pareto efficient solutions. In case you were thinking of option 2 as finding a lexicographic optimum by optimizing the highest priority objective, constraining it to be optimal, optimizing the next highest priority objective etc. (similar to but not the ... 5 The augmented$\varepsilon\$-constraint method is designed to generate all non-dominated outcome vectors to a bi-objective (or multi objective) optimization problem, whereas a lexicographic optimization approach is designed to generate one particular non-dominated outcome vector to bi-objective (or multiobjective) problem. So it all depends on what you want ...

2

To Sune's list, I'll add goal programming, in which you set targets for your objectives (possibly more than one target for a single objective), prioritize them, then minimize unfavorable deviations from the target in priority order.

4

Yes. There are plenty of other approaches to handle multiple objectives. First of all, you need to figure out, what you consider an optimal solution (set) to your multi objective optimization problem. To name a few notions of optimality you might consider Pareto optimality Lexicographic optimality (as @Kuifje suggests in a comment to the question) Max-...

Top 50 recent answers are included