Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
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 ...
mcmat23's user avatar
  • 1,070
0 votes
0 answers
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 ...
kic srx's user avatar
  • 11
1 vote
1 answer
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$...
Reed Trende's user avatar
0 votes
0 answers
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 "...
Andres Fielbaum's user avatar
12 votes
3 answers
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 ...
EggTart's user avatar
  • 507
0 votes
1 answer
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 ...
FNB's user avatar
  • 391
-1 votes
3 answers
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. ...
Jiayu Zou's user avatar
0 votes
1 answer
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 ...
Tuong Nguyen Minh's user avatar
0 votes
1 answer
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, ...
Daniel Longenecker's user avatar
1 vote
1 answer
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 ...
sam wolfe's user avatar
  • 3,435
1 vote
1 answer
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 ...
jacopoburelli's user avatar
1 vote
1 answer
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 ...
Noaline's user avatar
  • 39
1 vote
1 answer
37 views

Optimal ordering of a collection of gambles

An item is to be obtained at the minimum possible expected price. It can be obtained by paying a fixed price $F$, or by buying some gambles $G_i=(P_i,q_i)$ from a collection of offers $O=\{G_i|i\in\{0....
MarioVX's user avatar
  • 191
0 votes
1 answer
25 views

Consecutive binary block in MIP modeling with variable length

I'm currently modeling a MIP and face a problem on how to tackle consecutive binarys. I have a integer variable $A_v$ which marks the start time and a integer processing time $P_v$. I want to model ...
A C's user avatar
  • 5
0 votes
1 answer
27 views

Finding the set of solution to a linear sums problem

I have a set of fixed prices $P_1, \dots, P_{50}$, and a corresponding set of fixed caps $C_1, \dots, C_{50}$. I also have a limit of $L$. All are positive natural numbers ($1, \dots $). In addition, ...
Avi's user avatar
  • 225
0 votes
0 answers
13 views

Distributed newton optimization algorithm for m x n dimension

newton optimization algorithm to find the local minimum x∗ of a non-linear function f(x) with iteration sequence of x0→x1→x2...→x∗ all ∇2f(x_{k}). considering the x has m, and n with an index of i ...
Zahraoui Younes's user avatar
1 vote
1 answer
31 views

Partition algorithm for minimal summation

Assume 2 sets of integer $A=\{a_1,...,a_n\},B=\{b_1,...,b_m\}$ I need to find a target $n$ partition of $B$, denote $B_1,...,B_n$ such that the maximum of $a_i+\sum_{b\in B_i}b$ is minimal. I came up ...
Shore's user avatar
  • 343
1 vote
0 answers
49 views

Decomposing a graph into the minimum number of edge-disjoint trees

Given a graph $G = (V,E)$, what is the minimum number of edge-disjoint trees needed to cover $G$? How can we find such a decomposition? I've seen similar problems studied before (such as the ...
Catalyxx's user avatar
2 votes
0 answers
50 views

How is this function piece-wise linear?

I encountered this lemma in a research paper related to End-to-End inventory management model. Please note that $d_{[t_1,t_2]} = \sum_{t=t_1}^{t_2} d_t$, where $d_t$ denotes demand at time instance t. ...
Abhilash Mishra's user avatar
1 vote
1 answer
70 views

How to prove that this binary optimization problem can be decomposed into two subproblems?

I am an engineer who is currently working with some network placement problem and currently I am running into a strange situation. My original optimization problem has the following form: \begin{array}...
Tuong Nguyen Minh's user avatar
3 votes
3 answers
170 views

Maximizing GCD of a variable set of numbers

Is there a systematic method of selecting a set of numbers (which add up to a constant total) in such a fashion as to maximizing their collective GCD? One example: select 5 different integers (greater ...
Steve237's user avatar
  • 187
0 votes
0 answers
17 views

Predicting simulated data for a known curve

I am a newbie here seeking advice on a mathematical problem I am currently having in my research. I have a pre-existing curve created by extrapolating known fitted experimental data. As shown below, ...
SSh's user avatar
  • 1
1 vote
1 answer
35 views

Is there any algorithm to calculate this ranking method quickly?

I want to rank the 20 teams in the English Premier League. Say that each team are assigned to the number 1 through 20, defining their ranking, no ties. There would be $20!$ number of permutations for ...
Germaniac's user avatar
1 vote
1 answer
37 views

Question about a property of the integer-hull

If I have a convex set $Q\subseteq \mathbb{R}^n$ and a cone $E\subseteq \mathbb{R}^n$. Let $Q_I = conv\{Q \cap \mathbb{Z}^n\}$ and $E_I$ respectively. Is it in general the case that $Q_I + E_I \...
Sen90's user avatar
  • 453
1 vote
0 answers
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 ...
Surya Venkatesh's user avatar
0 votes
1 answer
43 views

Correctly understand the implication of approximation ratio for the set cover problem?

I am currently reading this wikipedia article about the set cover problem and it said here that "it cannot be approximated to $\left[ {1 - o\left( 1 \right)} \right]\ln \left( n \right)$ unless $...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
53 views

Is it possible or practical to just solve integer optimization problem by penalizing?

I am an engineer who is currently working in network optimization problem. I have finised my master degree a long time ago. During my studies I have learnt about the penalty technique to turn a ...
Tuong Nguyen Minh's user avatar
0 votes
0 answers
8 views

set partitioning formulation for directed vprtw

This assignment is courtesy of Roberto Roberti. The Vehicle Routing Problem with Time Windows (VRPTW) is a generalization of the Capacitated Vehicle Routing Problem (CVRP), where each customer must be ...
khadijatul kubra Nujhat's user avatar
0 votes
1 answer
42 views

How to find subgraph with maximum total edge weight

Let G be a undirected graph with weighted edges (The edge weight can be positive or negative). I want to remove some nodes from G, so that the sum of edge weights among remaining nodes is maximum.
Lorry's user avatar
  • 3
1 vote
0 answers
24 views

Dalton-Llewellyn method

I need to solve the discrete linear programming problem using the Dalton-Llewellyn method: $$ L(x)=-x_1+4x_2+2x_4-x_5\to max, $$ $$ x_1-5x_2+x_3=5, $$ $$ -x_1+x_2+x_4=4, $$ $$ x_1+x_2+8x_5=8, $$ $$ ...
ghartless's user avatar
-1 votes
2 answers
71 views

How do I solve a discrete log using pen paper for exam without bruteforcing it? [closed]

I have my Network Security finals. In elgamal cryptosystem, I am often encountering these equations like this 3 = (10^XA) mod 19 now everywhere I am finding only ...
Pragyan's user avatar
  • 111
1 vote
0 answers
70 views

Optimization over space of discrete functions on a graph [closed]

I recently stumbled upon a problem of the following kind. Problem: Let $G=(V,E)$ be a finite undirected graph, where $V=\{v_1, \dots, v_K\}$ is the set of vertices. Let $L = \{l_1, \dots, l_N\}$ be a ...
Onil90's user avatar
  • 2,733
0 votes
1 answer
36 views

Discrete Convexity of a Function

Let $Y \mid p \sim \text{Binomial}(x, p)$ and $Z \sim \text{Uniform}\{a, b\}$, where $a$, $b$, $x$ are non-negative integers and $a < b$. I am trying to prove that for any fixed probability $p$, $\...
Md Hishamur Rahman's user avatar
1 vote
0 answers
21 views

NP-Hardness of a Modified Multiple Knapsack Problem

I have $n$ knapsacks, each with a distinct volume capacity denoted as $c_j$. Additionally, there are $m$ items, each with a specified volume $v_i$, where the volume of an item is also equal to its ...
graphtheory123's user avatar
1 vote
1 answer
39 views

The minimum time to evaluate an arithmetic expression.

I have an arithmetic expression and I want to find the minimum time to compute this expression knowing the delay of each operator. The operators are addition, subtraction, multiplication, and ...
Robert's user avatar
  • 31
0 votes
1 answer
38 views

Maximize happiness in seating plan with cliques

Parameters of the problem: There are $x$ tables with capacity 8, $y$ tables with capacity 6, and $z$ tables with capacity 4. There are $8x+6y+4z$ people to seat. There exist cliques that wish to ...
Bryan K.'s user avatar
1 vote
1 answer
74 views

Generate superset with maximum overlap

I have a set $S$ with a total of 20000 items. I am also given a list $L$ of 0.5 million sets, with each set having 1-20 elements from the original set. I am given an integer $n$. Now I need a new set $...
Tarique's user avatar
  • 129
3 votes
0 answers
53 views

For what integers does this inequality hold true?

For what integers $a_{j},b_{j}\geq 2$, $j=1,\dots,n$, is the following inequality true: $$\min\left\{\min_{1\leq j\leq n}{\frac{a_{j}}{b_{j}}}, \min_{1\leq j\leq n}{\frac{b_{j}}{a_{j}}}\right\}\leq \...
Medo's user avatar
  • 3,144
-1 votes
2 answers
57 views

Identify optimal product size configuration based on historical data and some constraints [closed]

We have historical data for the demand of a product. Product can be demanded in any quantity between 0-1000g and the historical data show the distribution of previous request sizes. We can only pack ...
user896201's user avatar
0 votes
1 answer
27 views

Choosing k elements with multiple weights maximizing the minimum weight

Consider the following optimisation problem. Given a set $S$ with $q$ weight functions $w_1, \ldots, w_q: S\rightarrow \mathbb{R}_+$ and a constant $1\leq k\leq |S|-1$. Find an $X\subset S, |X|=k$ ...
Bence's user avatar
  • 31
3 votes
0 answers
126 views

When does an optimal input sequence for a discrete-time system exist?

Suppose an LTI discrete-time system is given by the equations $$ x_{k+1} = Ax_k + Bu_k,\\ y_{k} = Cx_k + Du_k $$ with $x_k\in\mathbb{R}^{m}$, $y_k\in\mathbb{R}^{n}$ and $u_k\in\mathbb{R}^{p}$ and $\...
Benjamin Tennyson's user avatar
0 votes
0 answers
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 ...
cyphic's user avatar
  • 1
0 votes
0 answers
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....
lafinur's user avatar
  • 3,468
0 votes
1 answer
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 ...
Binyamin Riahi's user avatar
0 votes
1 answer
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 ...
NonDairyNeutrino's user avatar
2 votes
0 answers
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 ...
Alice's user avatar
  • 508
0 votes
2 answers
42 views

Algorithm for allocating numbers into groups such that the maximum number of elements in the groups is minimized

Suppose there is a set of arrays $S= [A_1, A_2, ..., A_k] $, where $A_i$ is a finite subset of $\mathbb{Z}$. Given a positive integer $g$, I want to build $g$ sets $G_1,G_2,\dots,G_g$ such that $\...
Qcer's user avatar
  • 49
1 vote
1 answer
88 views

Proof Needed: Minimum # of coins needed to make a given sum

We have infinite supply of these 5 coins: $1, 3, 6, 10, 15$ Find the minimum number of these coins required such that their total value sums up to exactly $n$. Example: For $n = 425$, answer is $29$. ...
rachitiitr's user avatar
1 vote
0 answers
18 views

Maximum number of local minima in k-means

Suppose $\mathcal{Z} = \{z_1, \dots, z_n\}$ is the set of points in $d$-dimensional Euclidean space. The aim is to partition the dataset into $(K\leq n)$ distinct clusters $R_1,\dots, R_K$ where $R_i\...
entropy's user avatar
  • 147
0 votes
1 answer
38 views

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 ...
J. Ross's user avatar
  • 113

1
2 3 4 5
24