# Questions tagged [discrete-optimization]

For questions about discrete optimization, which is a branch of optimization with discrete variables, opposed to continuous optimization in applied mathematics and computer science.

1,184 questions
Filter by
Sorted by
Tagged with
1 vote
29 views

### Subset of index that minimizes a sum of real values

Given a series of real numbers $c_1, \ldots, c_n$ with $n \in \mathbb{N}$, is there an algorithm or method to find the subset of indices such that the absolute value of the sum of the values within ...
• 1,070
11 views

### Removing vertices from rooted tree to make it balanced

The question says, what is the least number of vertices that must be deleted from T to yield a balanced tree. The correct answer is 1. But how, i see the graph is already balanced and doesn’t need ...
• 11
1 vote
58 views

### Generate Max Number of Sequences Separated by Hamming Distance of 3

I'm interested in whether there is an algorithm for generating the maximum possible number of DNA sequences that are $7$ nucleotides long that differ by at least $3$...
23 views

### Variance of asymptotic Travelling Salesperson Problem

Consider N realisations of a uniform distribution on a bounded area in R^2 (e.g., the circle (0,1)). I know that when N is large, the length of a TSP visiting all of those points becomes "...
1k views

### Combinatoric Problem in Stardew Valley about Keg Layout

I will first give the mathmatical description of the problem, which I think is a good problem for high school MOers. Given positive integers $m, n \geq 3$, where $m$ is an odd number, consider a ...
• 507
23 views

### Finding a new MST for $G(V,E)$ after connecting a new vertex

Let $G(V, E)$ be an undirected, connected, graph. We have a weight function $w: E \to R$, and let $T$ be an MST of $G$. Suppose we connect a vertex $v$ to $G$ with at least one edge, and let's call ...
• 391
84 views

### An Optimization Problem With Permutation Function [closed]

When I tried to solve an one-to-one assignment problem, I constructed it as the following optimization problem, which is a min-max optimization problem with the optimization objective being functions. ...
27 views

### How to extend the $p \Rightarrow q$ constraint with logical AND within the $p$ statement for Big-M method?

I am a network engineer who is currently doing some network optimization problem. In my application, there is a requirement for the network delay to be bounded in some interval once some boolean flag ...
32 views

### Vertex packing for higher path lengths

I have an undirected, connected graph $G$, and I want to choose $k$ vertices so that I maximize the minimal path length between any pair. Intuitively, imagine that the $k$ vertices repel each other, ...
1 vote
145 views

### A hard optimization problem

Consider the following function, for $1\leq j \leq N$ $$\tag{1} y_j=\sum_{k=0}^{M} \frac{e^{-\sum_{|i|\leq k}(k-|i|)x_{j+i}/v}-e^{-\sum_{|i|\leq k}(k+1-|i|)x_{j+i}/v}}{\sum_{|i|\leq k} x_{j+i}}$$ for ...
• 3,435
1 vote
45 views

### Lattice width of $conv(0,ne_1,\cdots,n e_n)$

Given a subset $K \subseteq \mathbb{R}^n$ we define the lattice width of $K$ : $$\omega(K) = \min_{d\in \mathbb{Z}^n - \{0\}} \max_{x,y \in K} d^t(x-y)$$ With $K = conv(0,ne_1,\cdots,n e_n)$ how to ...
• 5,164
1 vote
51 views

### Determine the minimal tiling, allowing for both overhang and overlap, from a small shape to a larger one.

Context of Concrete Problem: While I have run into similar problems in other games, this specific one is for the game Stardew Valley. You would like to make a farm involving a scarecrow and the lowest ...
• 39
1 vote
37 views

• 453
1 vote
31 views

### How to formulate piecewise quadratic function optimization without introducing binary variables?

I have a problem with logical constraints (either-or constraints). I know that it can be solved by either big-M or complementary formulations. However, i do not want to convert it into mixed-integer ...
43 views

27 views

### MST vs SPT for a 2 vertex graph

I have a graph with 2 vertices. They each have a directed weighed edge towards the other vertex. One of the weights is higher than the other. Would this graph count as a graph that has a different ...
30 views

### Proving that $\chi(Q_n) = n$ where $n$ is the Queen's graph and $\gcd(n, 6) = 1$.

Let $Q_n$ be the Queen's graph with $n^2$ vertices. I was asked to show that $\chi(Q_n) = n$ whenever $6$ and $n$ are coprime. I have failed to provide a coloring that proves this for the general case....
• 3,468
73 views

### Irrigation problem as a graph coloring problem

I am trying to solve an interesting problem in graph coloring which I believe is related to the vertex cover problem. The graph is a $12 \times 12$ grid, representing a field. The field needs to be ...
24 views

### Using Outer Products and Matrix Multiplication to Compute Tour Weight in Traveling Salesman Problems

Set up Let $G$ be a complete, weighted, and directed graph with $N$ vertices as in the asymmetric Traveling Salesman Problem (TSP). Without loss of generality, let the the vertex set $V$ of $G$ be ...
64 views

### Find minimum number of moves between two squares for a chess knight

I have asked this question once before, but I forgot about it and it's been a long time since then. Also, I have learned new things since then so my approach has changed. Therefore I am creating a new ...
• 508
42 views

• 147
### Determining the location number of a graph $G$
Consider the following graph, $G$. I want to determine the location number of $G$. From the source I am using to learn graph theory, an ordered set $S=\{w_1, w_2, ..., w_k\}$ of vertices in a ...