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,104
questions
0
votes
0
answers
51
views
Allocating one source to each islanded subgraph
Suppose $G$ is a graph. $E(G)$ and $V(G)$ denote the sets of the edges and nodes (vertices) of $G$, respectively. Below is shown a graph with 9 nodes and 12 edges, which I will use as an example.
<...
0
votes
1
answer
65
views
Minimum amount of required chits to award player points
There is a board game for up to four players that has 7 rounds and at the end of each round the game awards the first player 3 points, the second 2, the third 1 and the fourth 0 points.
The points are ...
- 135
5
votes
1
answer
184
views
Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?
Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory".
6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. ...
- 1,978
6
votes
1
answer
166
views
When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?
Now also posted to MathOverflow.
Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will refer to such a set as a triplet. Consider now the problem of ...
2
votes
1
answer
117
views
Time complexity analysis of Kruskal's Algorithm
Hello I have a doubt about the time complexity of Kruskal's Algorithm.
Symbols:
$E \implies$ Total number of edges in the graph
$V \implies$ Total number of vertices in the graph
$O \implies$ Big $O$ ...
0
votes
0
answers
31
views
How to prove: An extreme point of a face of a convex set $K \subseteq \mathbb{R}^n$ is also an extreme point of $K$ [closed]
How do I prove that An extreme point of a face of a convex set $K \subseteq \mathbb{R}^n$ is also an extreme point of $K$
- 11
-1
votes
2
answers
75
views
given a binary point, design a quadratic which is minimized at that point!
Given a binary vector $x$, I need to efficiently construct a matrix $A$ such that $x$ is a global minimizer of $z^TAz$ over binary $z$'s. I need the diagonal elements to be positive.
- 258
0
votes
0
answers
8
views
Discrete Fast Radon Transform Transpose for Optimization Algorithm
The radon transform of an image $f(x,y)$ can be written as:
\begin{equation}
p(\alpha,s)=\int_{-\infty}^{\infty}f(x(z),y(z))dz \\
= \int_{-\infty}^{\infty}f(z\sin\alpha+s\cos \alpha , -z\cos \alpha + ...
- 101
2
votes
0
answers
39
views
Optimizing a packing of $n$ cliques into $K_n$
In a now-deleted question (previously here), user Lục Trường Phát posted what I thought was an interesting problem from a math competition at their school. To be clear, I don't know anything about ...
- 1,403
0
votes
0
answers
24
views
A Friendly Students Puzzle: Covering $K_{n^2}$ with King's Graphs
The following Question was posed here several years ago:
There are 25 students in a class who sit in five rows of five. Each week they sit in a different order.
After a number of weeks every student ...
- 1,403
1
vote
0
answers
109
views
minimizing a quadratic function with binary decision variables
Suppose that I have a simple quadratic function $f=x^TAx$ and the decision variable $x$ is binary, consider $$\min_x \ f(x) \quad s.t. \quad x \ \text{is binary}.$$
Under what conditions on $A$, a ...
- 258
0
votes
0
answers
13
views
Optimal Mass Distribution Minimizing Average 2-Wasserstein Distance to a Set of Mass Distributions
Given a fixed set of $n$ points in 2D (Earth Movers distance Prpblem), $P = \{p_1, p_2, ..., p_n\}$, I am trying to find the mass distribution $\bar{M}$ that minimizes the average 2-Wasserstein ...
- 595
11
votes
2
answers
567
views
Maximise $\left( \sum_{i=1}^{n} p_i \cdot i \right) - \left( \max_{j=1}^{n} p_j \cdot j \right)$ with $p$ permutation of size $n$
I'm trying to maximise the following value:
$\left( \sum_{i=1}^{n} p_i \cdot i \right) - \left( \max_{j=1}^{n} p_j \cdot j \right)$
where $p$ is an array consisting of $n$ distinct integers from $1$ ...
0
votes
0
answers
50
views
Is this discrete optimization problem NP-complete?
Consider a finite set $A \subseteq \mathbb{N} \times \mathbb{N} \times \mathbb{R}$.
Minimize
$$\sum_n \left( \max_{(n',i,a) \in A, n=n'} (a + x_i) + \max_{(n',i,a) \in A, n=n'} (-a - x_i) \right)$$
...
0
votes
0
answers
28
views
Maximisation with a Leontief function as constraint
Can anyone help me figure out how to maximise this problem knowing that the constraint is a leontief function?
$$
\max_{WS,W,S}\pi_{WS} = p_{WS}.WS - (p_W . W + p_S.S)\\
\text{subject to } WS = \min\...
- 1
1
vote
0
answers
31
views
Minimum cost tree.
I want an algorithm for the following problem. I have not find anything useful so far.
Given a undirected graph with costs assigned to the nodes, a positive number $n$ and a subset $S$ of the nodes, ...
- 11
0
votes
1
answer
230
views
An integer quadratic optimization problem
Suppose that $m \ge 1$ is a given positive integer, and $n \ge 1$ is a given even integer.
Let $R$ be the set of vectors $\vec{r} = (r_1, r_2, \cdots, r_n)$ such that
every coordinate $r_i$ is a non-...
- 1,289
0
votes
0
answers
19
views
Incorporating logistic function as a constraint in optimization problem
I have learned a sigmoid function $\sigma(\theta^Tx)$ using logistic regression. Where, $\theta \in R_+^n$ are the weights and $x \in R_+^n$ is a feature vector. How can I incorporate a linear or ...
0
votes
0
answers
16
views
Equivalence of set of minimizers of different optimization problems
Let $N = \{1,2,\ldots,n\}$ denote a set of items, $s \in \mathbb N^N$ the size of each item, $x \in \{0, 1\}^N$ a decision variable indicating whether item $i \in N$ is part of a package and $C > 0$...
- 747
1
vote
1
answer
37
views
Integer programming cuttings plane: code to find and explain strong cuts
My question has to do with integer programming and having a code that helps a researcher derive cutting planes.
Has anyone written some code, potentially interactive, to generate and explain cutting ...
2
votes
2
answers
88
views
Counterfeit coin with payments for weighting
I came across this recreational mathematics problem :
You have $100$ coins , one of which is counterfeit. You need to find the false one. To do so , you can give a jeweller some of your coins and he ...
- 173
1
vote
1
answer
63
views
When do two integer linear programs yield the same solution?
This question was cross-posted to operations research stack exchange
An illustrative example
Consider an integer linear program $\min -2x_1 + x_2$ subject to $x_1 - x_2 \leq 3$ and $x_1 + x_2 \leq 10$ ...
- 199
3
votes
2
answers
109
views
Minimum size of set intersection
There was a survey about 5 kinds of common diseases and 100 people took the survey. 72 people have the first kind of disease, and 68, 66, 59, 82 for other 4 diseases respectively. People with at least ...
- 31
1
vote
1
answer
32
views
Modeling AND of implication in integer/binary linear programming
Problem statement
Let $\beta \in \{0, 1\}$ for brevity. A set of $K$ numbers $M_k$, represented as individual bits $B_{ik} \in β $, must be distributed to a set of $ J \le K$ pairs $F_j = (c_{ij} \in ...
- 131
0
votes
1
answer
44
views
Closed form solution to linear optimization problem
Given integers $m$ and $n$, and a vector $\mathbf{v} \in \mathbb{Z}^n \setminus \{ \mathbf{0}_n \}$,
$$ \begin{array}{ll} \underset {\mathbf{w} \in \mathbb{N}^n} {\text{minimize}} & \sum\limits_{i=...
0
votes
0
answers
223
views
Static Vs. Dynamic Optimization?
I am beginner to optimization and my question is fundamental. We all know that Static optimization means the design variables/objective function does not vary with respect to time. Dynamic ...
- 23
0
votes
0
answers
20
views
Assignmentproblem with multiple precedence constraints
Crossposted at Operations Research SE
The objective is to load as many passenger vehicles as possible on an auto-train.
The train has two levels and both are constrained in terms of length (sum of ...
- 11
1
vote
1
answer
100
views
how to minimize $sum(sum(\mod(A^T X A,2)))$ [closed]
I have a constant binary matrix A (entries 0 or 1) and an unknown matrix X which is also binary. I'd like to find $X$ that minimizes $sum(sum(mod(A^T X A,2)))$; that is the number of 1's in $\mod(A^T ...
- 918
0
votes
1
answer
36
views
how to minimize trace(mod(A*X,2)) for A ,X matrices
I have a constant binary matrix $A$ (entries $0$ or $1$) and an unknown matrix $X$ which is also binary. I'd like to find $X$ that minimizes $trace(mod(A*X),2))$. So basically I do a matrix multiply ...
- 918
2
votes
1
answer
41
views
Binary program that maximizes ratio of quadratic forms
I'd like to solve the following optimization problem. Given $\mathbf a, \mathbf b \in (0, \infty)^n$, find $\mathbf x \in \{0, 1\}^n$ which maximizes
$$ f (\mathbf x) = \frac{\left( \sum\limits_{i=1}^...
- 4,877
1
vote
1
answer
194
views
Optimizing Cookie Clicker garden mutation layout
In cookie clicker there is a farming mini game. You can place plants on a grid. To unlock new plants, you have to place 2 plants you already have and on places adjacent to them (3x3 grid) there is a ...
- 113
1
vote
0
answers
25
views
Which canonical optimization problem is this: "Allocate items to people (with different costs to each person) and min maximum cost on a person?
I'm solving a min-max problem, which to me seems like it must be some sort of canonical problem. However, I cannot figure out which problem it resembles in the literature.
Description:
Given people (...
- 61
2
votes
1
answer
126
views
Lower bound on smallest diagonal element
Let $\bf R$ be an $m \times m$ matrix with non-negative integer elements $r_{i,j}$, $0\leq r_{i,j} \leq n$ and $n=km$ (k is a positive integer), with the property $\sum_ir_{i,j}=\sum_jr_{i,j}=n$, i.e.,...
- 23
0
votes
1
answer
83
views
Maximal spectral norm of balanced $\pm 1$ matrix [closed]
Suppose that we have a square matrix $A = [a_{ij}] \in {\Bbb R}^{n \times n}$ whose entries are $\pm 1$ and whose columns are balanced, i.e., $\sum_{i=1}^n a_{ij}=0$. How large can the spectral norm ...
- 341
3
votes
0
answers
94
views
The maximum value of $\det(A)$ where $A$ is a $4\times 4$ matrix made by the elements $-1$ and $1$ only is
The maximum value of $\det(A)$ where $A$ is a $4\times 4$ matrix made by the elements $-1$ and $1$ only is (A) 8 $\qquad$ (B) 16 $\qquad$(C) 32 $\qquad$ (D) 28
My Attempt
For a $1\times 1$ ...
- 8,344
2
votes
2
answers
106
views
How to arrange numbers on grid to satisfy a minimum condition?
Take an $N \times M$ rectangular grid and arrange the integers from $1$ to $ N M$ so that all grid point gets an assignment without repetition, and let the integer number on location (grid point) $n,m$...
- 731
0
votes
1
answer
35
views
Is this a maximum leaf spanning tree?
This is non-oriented weightless graph. I need to find the maximum leaf spanning tree for this graph. Am I made a correct maximum leaf spanning tree like in this pic , or not? Thank you for the answers....
Liuzili
0
votes
1
answer
44
views
Precedence constraints in assignment problem
I am struggling to model my problem correctly since multiple days.
Maybe someone can give me a hint.
I have two levels, both with a fixed number of slots (i.e. 200 each).
The items I want to put on ...
- 11
0
votes
1
answer
35
views
Forbid Flow to Split in Flow Network
Is it possible to somehow assert that flows are not allowed to split in flow networks by design? Assume you have a sink $s$ and a incoming flow value of 10. Furthermore you have 3 nodes $v_1, v_2, v_3$...
- 9
0
votes
2
answers
48
views
Minimize Variances of multiple depending datasets
Let $A=(a_{i,j})$ be a $(n \times m)$ Matrix. I'm looking for values $C_1,..., C_m > 0$ such that the variances, meaning $\sum_j (a_{ij}-$(Average of row i)$)^2$, of each row of the matrix A are ...
- 1
3
votes
1
answer
33
views
In general, will the ILP be solved faster if the number of variables is smaller?
This question might be a little bit vague. Suppose I have a variable $x$ in an ILP formulation such that $x$ can choose $\{0,1,2,3,4\}$. Now I use four binary variables to replace $x$, ($x_1+x_2+x_3+...
- 525
0
votes
1
answer
45
views
Graph Optimization Problems
I'm having a bit of trouble finding any references in the literature about optimizing functions defined on the set of graphs, i.e. in particular where the number of vertices is not fixed. For example, ...
- 431
1
vote
1
answer
48
views
Finding the maximal possible value of an expression
given the following expression:
$V =\frac{a}{a+x}+\frac{b}{b+y}+\frac{c}{c+z}$
and the following conditions:
$\\~\\a+b+c=30, a\neq 0
\\~\\x+y+z=15$
I am supposed to find the maximum possible value of ...
- 11
2
votes
2
answers
79
views
Math Grouping Optimization
I have roughly 10 employees assigned a random cost (for this example, lets say $0-$500). I'm trying to optimize grouping the employees into 3 groups. Every employee in the group must be paid the same ...
- 23
0
votes
0
answers
51
views
Give 1-approximation algorithm $Z-Tree$
$G$ = ($V$,$E$) is a complete graph, $X$ is a subset of $V$, and every edge satisfies the triangle inequality property. $X$-spanning tree is a sub-graph of $G$ that is a tree whose vertex set is ...
- 33
0
votes
0
answers
68
views
How to minimize this set function?
I'm considering a very interesting problem. For a graph $G=(V,E)$, either directed or undirected, if we define
\begin{equation}
\rho(G)=\max\{|\lambda|\;|\;\lambda\text{ eigenvalue of $G$'s adjacency ...
- 41
0
votes
0
answers
31
views
Graph optimization into a tree graph with an optimization formula
Assuming that we have a graph where all nodes have at least one edge connected to others and an optimization formula based on multiple factors, what optimization solutions there are to create a tree ...
0
votes
1
answer
86
views
Integrality Gap and Linear Relaxation vs. Binary Problem
For the following problem, can we say that its linear relaxation is equivalent to the binary problem?
Problem 1 ($y_j$ and $u_j$ are $0-1$ parameters.):
Given that $u_j=0$ the problem becomes (as $z_{...
- 123
4
votes
0
answers
84
views
Finding the optimal adjacency matrix [closed]
Notation: Let $\mathbf{A} \in \{0,1\}^{n \times n}$ be the adjacency matrix of an undirected graph. Let $\mathbf{D}$ be the degree matrix of this graph and let $\mathbf{L} = \mathbf{D} - \mathbf{A}$ ...
- 41
0
votes
0
answers
41
views
Which kind of optimization problem on integers is the following?
I'm not asking for a solution, I would just need to know what type of optimization is the following problem? Find $\mathbf{m}$ that minimizes:
$$
\sum_{k=1}^{N}\left|\frac{1}{\sin^{m}\left(\frac{k}{N}\...
