# Tagged Questions

Combinatorial optimization typically deals with optimizing over a finite set of objects that have some combinatorial structure (e.g. trees, matchings, matroids). Approximation algorithms, polyhedral methods, and integer programming are all on topic.

20 views

### Algorithm for Longest Common Subtour

For a new kind of heuristic for the TSP I need to calculate the longest subtour, that is common to a set $T_1,\ ...,\ T_m$ of tours, that are "good" approximations of the optimal tour $T_{opt}$. By a ...
14 views

### Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$. I know about Lovasz extension, but it works in other way: given discrete function ...
20 views

### Is budget-additive function a modular set function?

We know that budget-additive function $$f(S) = \min\{B,\sum_{i \in S}w_i\}$$ where $w_i$ is positive constant and $B \ge 0$ is called additive budget. Is it also a modular set function?
35 views

### max-flow at max-cost

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
79 views

143 views

### Network flows with shared capacities

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as: $$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$ where $f(1, 2)$ denotes the flow through arc $(1, 2)$....
76 views

### Limit shape for oil-shaped stack in the max overhang problem

In the Maximum Overhang paper, the authors mention an oil-shaped configuration (ref. page 19) What is known about the curve that limits this shape?
226 views

### Solution of a linearly constrained quadratic programming problem [closed]

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. \...
373 views

### How to roll a $p$

Let $p$ be a positive integer (which is not a power of $2$), and suppose we want to generate a number uniformly randomly in the set $\{ 0, 1, \dots , p-1 \}$ (to emulate a dice roll). We are given ...
222 views

204 views

86 views

### Nice minimal embeddings of large finite groups into compact Riemannian manifolds

The initial motivation for this question is a very practical problem: I need to find the absolute minimum of a function on a very large symmetric group $\Sigma_N$ (with $N$ 10000 or more). So if ...
237 views

### Can anyone suggest a text on polyhedral theory?

Can anyone suggest a text on polyhedral theory? Particularly on increasing the number of faces under projections. 0,1 polytopes
314 views

### Mixed integer programming formulation for Ising model [closed]

I want to implement a minimisation on a 2D spin Ising model with 30x30 grid. The spin variables is 0,1 and the objective is to minimize the sum of products of spins. For simplicity, I only include NN ...
Is there any useful structure associated with the following instance of the Set Covering problem? Let $G$ be a weighted graph and let $\mathcal{P}$ denote the set of all shortest paths between all ...