All Questions
59 questions
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
0
votes
0
answers
22
views
Alignment of unit vectors under graph-neighbor constraints with a global vector
Statement
Let $G = (V, E)$ be a connected, unweighted, and undirected graph with $n$ nodes, represented by its adjacency matrix $A$. Suppose each node $i$ is associated with a unit vector $ \mathbf{v}...
0
votes
1
answer
236
views
Solving a 0-1 quadratic matrix inequality
I am working on a binary optimization problem. So far I have derived the following constraint functions.
\begin{align}
\begin{bmatrix} \left( P + \sum_{i=1}^n (\sum_{j=1}^n x_{i, j} \alpha_j) e_i e_i^...
- 11
8
votes
2
answers
270
views
Equal segmentation of a series of numbers
How can a series of real numbers be split into subsets in a way that the sum of the real numbers within each subset is as equal as possible?
Coming across from StackOverflow this is the first time, I'...
- 83
3
votes
1
answer
208
views
Approximation of Poset
Let $(X,\leq)$ be a poset, $X=\{x_1,x_2,...,x_n\}$. Preference matrix $\textbf{P}=[p_{ij}]$ (which is known and fixed), satisfies $p_{ij}=1-p_{ji},p_{ii}=\frac{1}{2}$, and
$$\forall i \neq j, x_i \leq ...
- 61
0
votes
0
answers
64
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 ...
- 3
0
votes
0
answers
68
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)(\...
- 101
2
votes
1
answer
274
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}...
- 21
3
votes
1
answer
149
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} :=...
- 745
2
votes
0
answers
120
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}) - \...
- 175
4
votes
1
answer
139
views
How to find an optimal sequence of merging operations?
Given a set of items, each characterized by a quality $q_i\in(0,1)$. We can merge two items of quality $q_i$ and $q_j$ to a single item $k$ of quality $q_k=f(q_i,q_j)$, where $f$ is increasing in $q_i$...
- 367
6
votes
0
answers
74
views
Roundest polyhedra: how well can we bound the edge count of their faces?
By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...
- 3,612
2
votes
0
answers
119
views
Modified quadratic assignment problem
Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that
$$\left\Vert Y^{T}...
- 133
0
votes
1
answer
540
views
Best algorithm for meeting scheduling optimization so that total number of held meetings is minimized
Problem Description
I want to hold meetings where some given number of people will participate.
They have some vacant dates respectively but they don't have the same date on which all of them can ...
- 11
2
votes
0
answers
56
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
- 2,772
0
votes
0
answers
96
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
- 29
15
votes
2
answers
974
views
n sets, each is large, the intersection of every three is small, what is the size of the union?
Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that:
(1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$;
(2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...
- 373
2
votes
1
answer
71
views
What's the meaning of this inequality in the lot-sizing and scheduling problem
I learned about the MILP models proposed by Pochet and Wolsey. Here are the formulations of one of these models(MILP3).
So the decision variables and the primary formulation are as following:
Based ...
- 21
0
votes
1
answer
54
views
Relation of 1-trees to optimal tours
Question:
given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ ...
- 13.2k
3
votes
0
answers
121
views
Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$
Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix).
Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...
- 205
0
votes
1
answer
76
views
A question on graph partitioning
Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
- 1,216
1
vote
1
answer
86
views
Complexity of calculating the optimal amalgamation of an optimal cycle-cover
Let $G(V,E)$ be a complete symmetric graph with positive edge weights and let further $\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$ be the minimum-weight vertex-disjoint cycle cover.
The set $E$ of ...
- 13.2k
1
vote
0
answers
96
views
Relationship between Wasserstein projections and metric projections in a linear space
Let $(X,d)$ be a metric space, $x\in X$, and $Y\subset X$ is a closed set. Assume that $X$ is also a real vector space, so that we can form linear combinations over $\mathbb{R}$, but I do not assume ...
- 13
6
votes
2
answers
426
views
Snake algorithm that minimizes straight lines
How can I find the non-self-intersecting loop that uses the least amount of straight lines (curves left/right as often as possible every turn) and still loops back on itself?
Here's an example we have ...
- 61
1
vote
1
answer
94
views
Weak submodularity for consecutive indices
Let $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ be defined by $f(x,y) = \frac{x^2}{y}$. Let $X = \left\lbrace x_1, \dots, x_n\right\rbrace \subseteq \mathbf{R}$, $Y = \left\lbrace ...
8
votes
3
answers
296
views
Shrinking subset and product
Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that maximizes $|...
- 1,209
1
vote
1
answer
117
views
Shrinking subset with disjoint unions
Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be disjoint finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that ...
- 1,209
0
votes
0
answers
127
views
Maximizing a vector after a series of matrix multiplications
Problem Statement
Let's say we have a set of $n\times n$ matrices $X=\{M_1,\ldots,M_r\}$ and weights of these matrices $\{w_1,\ldots,w_r\}$ along with a set of "initial vectors" $\{v_1,\...
- 509
3
votes
1
answer
269
views
Optimal rule for multiple stopping times for defect finding
Suppose a quality inspector is inspecting $b$ black amongst which $d_B$ are known to be defective and $w$ white gadgets amongst which $d_W$ are known to be defective. The gadgets come down along an ...
- 2,239
1
vote
0
answers
38
views
Structural properties of polytopes for mainstream integer or linear programs
Are there any papers/textbooks/monographs that describe distinguishing properties of the polytopes that arise when solving the linear relaxation of well-known integer programs? For example, it is ...
- 4,049
2
votes
1
answer
240
views
Basis pursuit algorithms for exponentially large matrices?
Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is
$$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...
- 21
0
votes
1
answer
221
views
Minimize overlap penalty between paths in graph
Suppose we have a weighted undirected graph $G(V,E)$. We are given the information that $V_a \cap V_b = \emptyset$ and $V_a,V_b \subset V$.
We want to find paths from all vertices in $V_a$ to all ...
- 25
1
vote
1
answer
444
views
Looking for an efficient way of maximising 'pair scores' for subset of 30 selected from 50 to 10 000 objects
Context: I have a tiling program that uses a directed breadth first search algorithm. It is 'directed' by what I call 'pair scoring'. There are $N$ polyforms (pieces) used in the tiling. I have an $N\...
- 613
3
votes
2
answers
287
views
Probability that the solution to a combinatorial optimization problem changes after random modifications
Given a combinatorial optimization problem, say the Traveling Salesman Problem, the optimal solution is a set of elements (edges in this case) that satisfy certain constraints (constituting to a ...
- 13.2k
2
votes
1
answer
329
views
Worst case performance of heuristic for the non-Eulerian windy postman problem
The windy postman problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in ...
- 13.2k
0
votes
1
answer
61
views
Variant of the linear programming problem
Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....
- 193
2
votes
1
answer
710
views
$0$-"norm" minimization with least-squares regularization
I have the following optimization problem in $\mathbf{x} \in \mathbb{R}^{K \times 1}$
$$\min_{\mathbf{x}>0} \quad \|\mathbf{A}\mathbf{x}\|_0 + \alpha \|\mathbf{B}\mathbf{x}-\mathbf{c}\|_2^2$$
...
1
vote
1
answer
91
views
Rational combinatorial optimization problem
What is the complexity of and how to go about solving the following task?
Given $a, b \in \mathbb{R}_+^n$ and $n \ge k\in\mathbb{N}$, find
$$ x_{\min} := \arg \min_{x \in \lbrace 0,1 \rbrace^n, x^T ...
- 13.2k
2
votes
0
answers
81
views
Solving Mixed-Integer Non-Linear Optimization Problem
I would like to solve the following optimization problem:
\begin{array}{ll}
\underset{x_{i}\geq0,\, \pi_{i}\in\{0,1\}}{\text{minimize}} & \displaystyle\sum_{i=1}^n x_i\\
\text{subject to} & ...
- 21
1
vote
0
answers
37
views
Asymptotics for a random set cover problem
Suppose you are given a positive integer $k$ and a probability distribution $f$ on the positive reals. I am interested in the limiting behavior of the following process as $n\to\infty$:
Create an ...
- 4,049
5
votes
1
answer
432
views
Optimizing a multivariate symmetric (permutation-invariant) function
Let $\ell$ and $d$ be two integers such that $\ell \le d$.
I would like to find the global maxima of the following symmetric function $f\colon (0,1]^n \to \mathbb{R}$,
$$f(x_1, \ldots, x_n) := \sum_{\...
- 381
4
votes
2
answers
754
views
A structural optimization problem
I have $n$ objects $O_i$, each of them having $3$ values, $O_i = (A_i, B_i, C_i)$. I am trying to group them into $k$ groups $P_u$ such as $P_u =(A_u, B_u, C_u)$ such that
$$\text{minimize} \quad \...
5
votes
1
answer
109
views
Improved estimates of $n$ quantities via $n$ measurements
$\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\epsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\la}{\lambda}
\newcommand{\si}{\sigma}
\newcommand{\Si}{\...
- 128k
0
votes
1
answer
212
views
Is an exact violated inequality constraint met as equal constraint in optimal solution?
We have a solution which does not satisfied exactly one inequality constraint in linear program. The corresponding dual solution is also feasible. Is it correct this constraint is in equal form in the ...
- 25
4
votes
0
answers
539
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
- 391
12
votes
1
answer
214
views
The angles subtended in a TSP tour
If I sample a large number of uniform points in the unit square and take a traveling salesman tour of them, is there anything at all that can be said/is known about the distribution of angles at each ...
- 4,049
2
votes
1
answer
171
views
Parametric minimum spanning tree
I look for a simple algorithm for parametric minimum spanning tree where the weight of the edge e is $a_e + \lambda b_e $. Can we simplify the algorithm in case $b_e=1$ for all edges?
- 25
2
votes
0
answers
46
views
What is known about the relation of the multiple salesman problem and the travelling saelsman problem?
The travelling salesman problem (TSP) is well known (https://en.wikipedia.org/wiki/Travelling_salesman_problem). Let us look at the Euclidean TSP throughout this question.
There is a generalization ...
- 61
4
votes
3
answers
837
views
What is known about worst-case point sets for the travelling salesman problem?
The travelling salesman problem (TSP) is well-known, see e.g. https://en.wikipedia.org/wiki/Travelling_salesman_problem.
Let us consider the Euclidean version of the TSP within the unit square.
This ...
- 61
0
votes
0
answers
68
views
Under which conditions discrete versions of convex\concave function are submodular/supermodular?
I have $f(x)$ with $x \in [0,1]$ and $f(x)$ is convex, then, under which conditions discrete function which is defined as $f(x_h)$ on discrete subset of $[0,1]$, for example, $x_h \in \{0, h, 2h, \...
- 355