The combinatorial-optimizatio tag has no wiki summary.
7
votes
1answer
240 views
Quickly finding optimal subset of pairs of numerator and denominator terms for special objective functions
Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the ...
-1
votes
1answer
32 views
Effect of a Specific Restriction on the Integrality of Min-cost Flow Solutions
I want to model the following situation: there is one production site (modelled by the source), a collection of depots (modelled by nodes without demand) and, of course many more customers (modelled ...
2
votes
0answers
39 views
Optimization over a variable domain defined as a convex hull of given points [closed]
I have an optimization problem:
$\max_{\bf{x}} Z(\bf{x})$,
s.t. $\bf{x} \in conv(\bf{S})$
where $\bf{x}$ is an $n$-dimensional vector, $Z(\bf{x})$ is a non-linear function. The domain of $\bf{x}$ ...
1
vote
1answer
86 views
Deducing Linear Inequalities
Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
2
votes
1answer
118 views
Optimization problem - maximizing number of satisfied linear inequalities subject to a quadratic constraint
I am wondering what is known about optimization problems of the following type.
Our control x is a unit vector in $\mathbb{R}^n$. We are given a finite number of linear inequalities
$$Az≥b,$$
and we ...
1
vote
1answer
59 views
Finding a sub-matrix from a fat matrix with the best condition number.
Given a m-by-n matrix with $n>>m$ and with a known rank of $k\leq m$, what would be a computationally effective way of finding out $k$ columns, such that the matrix formed using these $k$ ...
6
votes
1answer
226 views
Inverse of a totally unimodular matrix
A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$.
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...
2
votes
1answer
122 views
Maximizing supermodular functions
I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k .
I am wondering if anyone can give me more information about a ...
0
votes
0answers
37 views
Approximation for accumulative set cover
Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\{1,\ldots,m\}$, I want to maximize the quantity
\begin{equation}
...
0
votes
0answers
56 views
Laplacian using SDP
Is there any suggestion about how could one construct a model that uses semidefinite programming that minimizes sum of k smallest eigenvalues of Laplacian matrix?
I found two papers that have done ...
0
votes
0answers
114 views
Chinese Postman problem in bidirected graph
I need to find a Chinese postman circuit in a bidirected graph.
Bidirected graph here is not the symmetric directed graph, but the graph introduced by Edmonds & Johnson in 1970.
I found few ...
4
votes
3answers
313 views
Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums
I have an optimization problem where I need to select $k$ integers over the interval $[0, N]$ s.t. I maximize the minimum difference between any pairwise sum of the $k$ integers (where we also include ...
1
vote
2answers
140 views
sorting two paired lists of real numbers to minimize consecutive absolute differences
Consider a set of $n$ real-valued number pairs: $(x_1,y_1), (x_2,y_2), \dots, (x_n,y_n)$. I want to find a permutation $p$ of the indices which minimizes the sum of consecutive absolute differences: ...
0
votes
0answers
94 views
What is known about this constrained maximum s-t-cut problem?
What is known about the following problem?
Problem: Given an undirected, connected, planar graph $(V,E)$ with positive edge weights $q: E \to \mathbb{R}_0^+$, and given two distinct vertices $s, t ...
0
votes
0answers
23 views
Maximizing the cutnorm for matrices with low rank
Given an $m \times n$ matrix $A$ with positive and negative entries, consider the problem of maximizing the expression $\sum_{i,j} x_i y_j a_{ij}$
subject to the constraints $x_i, \, y_j = \pm 1$. It ...
