Questions tagged [combinatorial-optimization]

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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
175 views

Generating all possible subsets in order of sum

Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it ...
Ood's user avatar
  • 121
4 votes
0 answers
214 views

Optimal colorings

If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$. For any coloring $c:V(G) \...
Dominic van der Zypen's user avatar
1 vote
2 answers
372 views

What is the proper name for this "tersest path" problem in Infinite Craft?

The web game Infinite Craft gives you a starting set of elements $V_0\subset V$ and a mapping $E$ of type $V\times V\rightarrow V$. In fact, $F$ is commutative: $E(v_a,v_b) = E(v_b,v_a)$. So another ...
Quuxplusone's user avatar
3 votes
2 answers
166 views

Is there a closed-form solution for $\max_D \operatorname{Tr}(ADBD)$

Is there a closed-form solution for $$\max_D \operatorname{Tr}(ADBD)$$ where $D$ is a $N\times N$ diagonal matrix with $m<N$ number of $1$'s and the rest are $0$'s, and $A$ and $B$ are real ...
CWC's user avatar
  • 359
1 vote
0 answers
140 views

Optimal covering trails for every $k$-dimensional cubic lattice $\mathbb{N}^k := \{(x_1, x_2, \dots, x_n) : x_i \in \mathbb{N} \wedge n \geq 3\}$

After a dozen years spent investigating this particular class of problems, I finally give up and I wish to ask you if any improvement is achievable from here on. The general problem is as follows: Let ...
Marco Ripà's user avatar
  • 1,119
2 votes
1 answer
200 views

Is matrix B obtained from matrix A?

Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
eternity's user avatar
2 votes
1 answer
135 views

First known proof of the $2 \cdot n-2$ Theorem for the planar generalization of the Nine dots problem

Reading the Wikipedia page about the well-know Nine dots puzzle, I have just seen that the planar generalization of this problem would have been proven in 1956 (see Wikipedia: Nine dots puzzle), while ...
Marco Ripà's user avatar
  • 1,119
1 vote
0 answers
44 views

Two index formulation for capacitated vehicle routing problem [closed]

I'm trying to model the capacitated vehicle routing problem with two index in the case of two fleets with respective capacity $q_1$ and $q_2$. I tried several versions for many months and now I have a ...
MAYA's user avatar
  • 111
0 votes
0 answers
33 views

ILPs with square constraint matrix

Given the Integer Linear Programming ($\text{ILP}$) problem \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to}& \mathbf{A}^T x \ge b \\ \text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
Manfred Weis's user avatar
  • 12.6k
0 votes
0 answers
13 views

Complexity of finding single source paths with capacity constraints and length constraints

Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...
Yossi Peretz's user avatar
0 votes
0 answers
24 views

Monotony of enforced subtour merging

Is it true that for a symmetric TSP instance in the sequence of edges generated by successively: calculating the optimal 2-factor adding cardinality constraints on the edgesets of the 2-factor's ...
Manfred Weis's user avatar
  • 12.6k
0 votes
0 answers
50 views

Alternatives to McCormick Envelope

I have an optimization problem for which I have the optimal solution obtained by the ILP. However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
LyLa's user avatar
  • 3
4 votes
0 answers
257 views

Place colored balls in boxes that makes it hard to pick few boxes that contains large proportion of each color

There are $n$ boxes filled with red, blue and yellow balls. A box can be empty and it can also contain more than one color. For example, a box can have three red balls, ten blue balls and one yellow ...
Peter Simon's user avatar
2 votes
1 answer
189 views

Electricity division and bin packing

In the electricity division problem, there is a powerhouse that supplies $s$ kilowatt of electricity. There are $n$ households. The connection size of household $i$ is $d_i$. The problem is that $s &...
Erel Segal-Halevi's user avatar
2 votes
0 answers
164 views

How to prove this weighted sum inequality with non-increasing sequences?

Problem I have two non-increasing sequences, $X = (x_1, x_3, x_5, \ldots, x_{n-1})$ and $Y = (y_1, y_3, y_5, \ldots, y_{n -1})$, $n$ is an even integer. I want to prove this inequality: $$ \sum_{i=1}^{...
birdlpy's user avatar
  • 29
6 votes
1 answer
347 views

Maximizing a sum minus its maximal summand

This is a followup to a question that appeared on m.SE: Maximize $\displaystyle f(\pi)=\left(\sum_{i=1}^{n}{i\pi_i}\right)-\max_{1\le i\le n}{(i\pi_i)}$ over permutations $\pi\in S_n$. The problem ...
Alexander Burstein's user avatar
1 vote
0 answers
64 views

Maximum trace of powers of symmetric $\{0,1\}$-valued matrix with fixed row and column sums

Maximize $\operatorname{tr}(A^k)$ over binary symmetric $n$ by $n$ matrices subject to $$a_{ii}=0, \sum_{j=1}^n a_{ij}=d, \sum_{i=1}^na_{ij}=d,$$ where $d,k$ are fixed positive integers. I am having ...
ComfySofa's user avatar
0 votes
0 answers
71 views

An $n$-dimensional generalized Hoffman’s circulation theorem?

For a directed graph $G$, a 1-dimensional circulation is a function $f:E(G)\rightarrow \mathbb{R}$ such that for every $v\in V(G)$, $$\sum_{uv\in E(G)}f(uv)=\sum_{vw\in E(G)}f(vw),$$ where $uv$ is an ...
Connor's user avatar
  • 251
0 votes
1 answer
87 views

Graph vertices selection for paths sum minimalization

Let $G = (V, E)$ be a simple, finite, weighted, undirected, connected graph. Let $P = \{p_{ij}, p_{kl}, p_{il}, ... \}$ be a set of paths, where $p_{ij}$ is a path from $i$-th to $j$-th vertex. Is ...
Tomasz Rybotycki's user avatar
1 vote
0 answers
47 views

Hardness of an optimization problem when some variables are fixed

Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed. With the two (related) examples, it is clear that ...
Ro. Cohof's user avatar
2 votes
0 answers
46 views

Size of set of positive integers no sum of two distinct elements giving square

Question: find the size of a maximal subset $A$ of $[n]=\{1,\cdots,n\}$ satisfying that for any distinct elements $x,y\in A$, $x+y$ is not a perfect square. Consider a graph with $n$ vertices: $x$ and ...
Haoran Chen's user avatar
2 votes
1 answer
141 views

Optimization over permutation

The Problem This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
Honglian's user avatar
0 votes
0 answers
59 views

Optimal top-k column subset

Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\...
Eli Bixby's user avatar
  • 101
2 votes
1 answer
149 views

Can we say this nonlinear integer programming problem is NP-hard?

I was wondering if the following nonlinear integer programming problem is NP-hard or not. $$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$ such that $\sum_{i=1}^{n}...
Anson's user avatar
  • 21
2 votes
1 answer
170 views

Discrete maximization of geometric mean - reference request

This is a follow-up to my previous MO question: A discrete optimization problem related to the AM-GM inequality Let $n,k$ be integers such that $1\le k\le n$. Define the quantity $$ P(n,k):=\max\ a_1\...
Abdelmalek Abdesselam's user avatar
0 votes
1 answer
70 views

Optimality of a "shopping" heuristic

Suppose the following situation: we have to buy $n$ goods $g_1,\,\dots,\,g_n$ starting at day 1 and we can't buy more than one good per day. On day $d$ the prices are $p_1^d,\,\dots,\,p_n^d;\quad p_i^...
Manfred Weis's user avatar
  • 12.6k
6 votes
1 answer
341 views

Desargues ten point configuration $D_{10}$ in LaTeX

I want to draw the Desargues configuration $10_3$ in LaTeX using the standard picture environment, which allows only lines with the slopes $n:m$ where $\max\{|n|,|m|\}\le 6$. Is it possible? If not, ...
Taras Banakh's user avatar
  • 40.8k
2 votes
2 answers
91 views

Real-world datasets for testing the maximum edge bi-clique problem

We have proposed a new approach to solve the maximum edge bi-clique problem, however, we couldn't succeed to find real-world datasets (graph or bipartite graph datasets) to test our approach. Does ...
Salma Omer's user avatar
2 votes
0 answers
67 views

What is an efficient non-adaptive group testing scheme if the number of defectives, $d$, grows proportionally to the number of items, $n$?

Suppose that for some $p \in \left(0, 1\right)$ and some $n \in \mathbb{N}$, we have $n$ independent Bernoulli random variables, $X_{1}, X_{2}, \dots, X_{n}$, each with mean $p$. We shall call $X_{1}, ...
Matthew Barber's user avatar
3 votes
1 answer
130 views

How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?

For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut norms are given by $$\|M\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} m_{i, j} x_i y_j, \qquad \|M\|_{\square} :=...
Display name's user avatar
0 votes
0 answers
20 views

LP formulation of $k$-opt moves

Question: what is known about formulating $k$-opt moves that strive for improving the length of Hamilton cycles by means of exchanging $k$ of the tour edges with $k$ non-tour edges? Specifically: are ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
100 views

On determinant and permanent of certain homotopy defined simple matrices

Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$ $$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$ hold ($per$ refers to permanent). I. What ...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
50 views

Properties of the "girth function" of a matroid

Given an independent set representation of a matroid $M=(E,\mathcal{F})$ its ``rank function'' $r$ defined on the powerset of $E$ is: $$ \forall X \subseteq E, \quad r(X) = \max_{Y \subseteq X}\{|Y|, ...
Felix Goldberg's user avatar
0 votes
1 answer
151 views

A variation of Set Cover

Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to ...
Jackson's user avatar
1 vote
0 answers
55 views

Knotted Traveling Salesperson route

Let us consider fixed points in space, if we apply the well-known Traveling Salesperson Problem algorithm, we get the shortest route. It can give a nontrivial knot in the three-space. The question is ...
knotMJ's user avatar
  • 71
1 vote
0 answers
40 views

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following. Given a graph $G = \{V,E\}$, we have a distance matrix (the ...
Yichuan_Sun's user avatar
2 votes
0 answers
118 views

How to solve $\min_{\mathbf{x}\in \{\pm 1\}^N} \lVert \operatorname{sign}(\mathbf{Wx}) - \mathbf{y} \rVert_2^2$ where $\mathbf{y}\in \{\pm 1\}^N$?

Given the matrix $\mathbf{W} \in \mathbb{R}^{N \times N}$ and the vector $\mathbf{y} \in \{\pm 1\}^N$, how to solve $$\min_{\mathbf{x}\in \{\pm 1\}^N} \left\| \operatorname{sign}(\mathbf{Wx}) - \...
user3750444's user avatar
1 vote
2 answers
116 views

How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?

I am looking for an algorithm to solve the following optimization problem $$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$ where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$. ...
user3750444's user avatar
11 votes
2 answers
600 views

A discrete optimization problem related to the AM-GM inequality

Let $k\in\mathbb{Z}_{>0}$, and $s\in\mathbb{N}$, and for $m_1,\ldots,m_k$ some nonnegative integers, consider the problem of maximizing the product $$ (1+m_1)(1+m_2)\cdots(1+m_k) $$ under the ...
Abdelmalek Abdesselam's user avatar
11 votes
0 answers
434 views

What sequence maximizes the final distance?

This problem was created by professor Ronaldo Garcia from Universidade Federal de Goiás (UFG) and he showed it to me at an event in my university. This problem has a lot of history and he told me he ...
Arthur Queiroz Moura's user avatar
5 votes
0 answers
225 views

What does the best die look like?

Intransitive dice have attracted a lot of attention - especially in the context of recreational math - since their introduction by Efron in the 1960s. More recently, there has been work studying ...
Sam Hopkins's user avatar
  • 22.7k
0 votes
0 answers
122 views

On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph

Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
shahulhameed's user avatar
0 votes
0 answers
54 views

Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph

This is about graph theory. Define an h-dimensional hyperedge as a set that contains h vertices. A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...
TanG's user avatar
  • 23
1 vote
0 answers
56 views

A multi-layer version of Menger's theorem

Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more ...
Agelos's user avatar
  • 1,844
2 votes
1 answer
171 views

Can information theory characterise a (topological) space?

Consider an objective function f: $\mathbb{R}^n\rightarrow\mathbb{R}$, with a vector of variables $\theta$, i.e. $f(\theta)$, $\theta \in \mathbb{R}^n$. Depending on $f$, there can be interesting ...
Tessa van der Heiden's user avatar
2 votes
1 answer
96 views

How to prove the local search algorithm can find the maximum weight independent set in a matroid with cardinality constraint?

I am trying to prove a simple local search algorithm could solve exactly this problem: $\underset{S \in I(M), |S|=k}{max} c(S)$ where $M$ is a matroid, and $ I(M)$ is the set of all independent set, $...
Honglian's user avatar
1 vote
1 answer
92 views

Minimum set of numbers which covers all the values of all digits

Introduction Let's consider binary numbers for simplification and let's consider 4 bits numbers. Sets which answer my problem are: ...
user496620's user avatar
0 votes
1 answer
115 views

Traveling salesperson problem algorithm [closed]

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...
Ehsan Javanbakht's user avatar
3 votes
1 answer
302 views

How to find the maximum of a sum of squares of sums?

Is there any better than a brute force method for finding the maximum $$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$...
user avatar
3 votes
0 answers
102 views

The matrix representation of an interval graph

It is well-known that many classes of graphs have matrix representations that can be written concisely. For example, The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...
Tom Solberg's user avatar
  • 3,929

1
2 3 4 5
9