# Tagged Questions

**0**

votes

**1**answer

40 views

### maximization of harmonic mean

Suppose x is a vector of size N with positive real elements sorted in decreasing order. Is it possible to find the analytical solution (no iterative solution) to the optimum value of M (1<= M ...

**2**

votes

**1**answer

148 views

### programming to compute kernel quotient image of a $\mathbb{Z}$-module endomorphism

Let the integers $n\geq 2$, $k\geq 1$, $v=0$ or $1$ and $n_1,\cdots,n_k\geq 1$ such that
$$
\sum_{i=1}^k n_i+v=n.
$$
Define $P_a^b=0$ if both $a,b$ are odd and $P_a^b={{[a/2]}\choose {[(a+b)/2]}}$ ...

**3**

votes

**0**answers

113 views

### Lenstra's integer programming algorithm: Finding a lattice point “near the center”

I have already posted this question on the mathematics forum, but I suspect the question needs more detailed knowledge than most users have; please excuse the duplicate post. Any help is greatly ...

**0**

votes

**0**answers

18 views

### Is there a standard technique for overdetermined homogeneous integer programming?

Given $M\in\Bbb Z^{n\times n}$ of $\mathsf{rank}(M)=r\leq n$ consider $MX=\mathsf0_n$ where $X\in\Bbb Z^{n\times 1}$ holds. We also have a $\mathsf{rank}(N)=m\leq n$ matrix $N\in\Bbb R^{m\times n}$ ...

**6**

votes

**1**answer

93 views

### Algorithm that solves every Mixed Integer Linear Program (to optimality)?

Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically?
I know that you usually ...

**2**

votes

**0**answers

21 views

### Pcross-like, nonogram-like in near-linear time [closed]

I have a problem with a puzzle game like pcross in which I have a nxn square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that ...

**8**

votes

**1**answer

123 views

### On linear integer inequalities with infinitely many solutions

Suppose that a linear system of inequalities $Ax \le b$, where $A\in Z^{m\times n}$ and $b\in Z^m$ have integral coefficients, has an infinite number of integral solutions $x$.
Can one conclude that ...

**0**

votes

**2**answers

200 views

### Minimal solution of simultaneous congruences

I would to determine the set of values $\lbrace a_1,a_2,a_3,\ldots,a_n \rbrace$ that minimizes the value of $x$ such that:
$$x\equiv a_1\mod p_1$$
$$\vdots$$
$$x\equiv a_n\mod p_n$$
where every ...

**3**

votes

**0**answers

54 views

### Reference request: how to find the k'th best solution to the 1-0 knapsack problem?

How do I find the k'th best solution to the 1-0 knapsack problem without finding the Top-k solutions? Is there any mathematical research that deals with the k'th best solutions to the mixed integer ...

**1**

vote

**0**answers

151 views

### System of congruences

I have a system of $n$ congruences.
the generic $m$_th congruence of the system ($m = 1,\dots,n$) is in the form:
$(p_n\#)^2(\displaystyle\sum_{\substack{i=1\\i\neq ...

**2**

votes

**0**answers

76 views

### Listing all Lattice Points in a Box

Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...

**2**

votes

**0**answers

33 views

### About the partial expectation polynomials in the Interlacing-I paper and perfect matchings

I am thinking of the polynomials $f_{s_1,s_2,..,s_k}$ as in the definition 4.3 in this paper http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf
In the use of these ...

**1**

vote

**0**answers

43 views

### The column generation technique on a Train Unit Assignment Problem [Linear Programming]

I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...

**4**

votes

**0**answers

62 views

### Is a Parametric Integer Linear Programming Problem eventually quasi-polynomial?

I will consider a family of Integer Linear Programs parametrized by a positive integer $t$.
Let $\mathbf{x} = (x_1, \ldots, x_n)$ be the indeterminates.
Let $A$ an $m$ by $n$ matrix whose elements ...

**2**

votes

**1**answer

99 views

### Sufficient condition for solvability of linear diophantine system

I would like to know under what conditions does an integer solution exist to the under-determined linear system:
Ax = b. (without constraints)
Where A is m x n matrix with positive integers entries ...

**1**

vote

**0**answers

97 views

### Complexity :: Integer Programming :: Non-Poly Example [closed]

When learning about computational complexity I find that when discussing the NP-Complete problems authors always give examples of such problems that can in fact be solved in poly time.
I understand ...

**1**

vote

**1**answer

162 views

### basis of the lattice generated by the integer points inside a subspace of R^L

Consider $K$ linearly independent vectors $\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K \in \mathbb{Z}^L$, where $1 \leq K<L $. Hence, the span of $\lbrace\mathbf{a}_1, \mathbf{a}_2, ..., ...

**5**

votes

**1**answer

336 views

### Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...

**1**

vote

**2**answers

155 views

### Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity.
...

**0**

votes

**1**answer

86 views

### Generalized assignment problem with no integrality gap

Suppose I am solving the generalized assignment problem, so that I
am given matrices $U$ and $W$ and a vector $c$ (all three of which
have, say, positive entries), and I want to solve
...

**6**

votes

**1**answer

263 views

### Speed up Linear programming

I have a linear programming problem like this:
minimize $c^t X$
under the constraint that $AX \ge b$.
I will need to solve this linear programming problem online many times. I need it to be as fast ...

**2**

votes

**1**answer

92 views

### Find base of kernel with as many 0 as possible

I have a 400x132 rectangular matrix with only 0 and 1.
I am looking for the linear combinations of the columns of the matrix that sum to 0.
For example C1 + C2 - C3 = 0.
I want to find the linear ...

**2**

votes

**0**answers

57 views

### Reference request: Edmond's Algorithm for integer hull

I'm looking for a good reference for the algorithm (supposedly by Edmonds) to compute the integer hull of a polytope, not by cutting plane methods but by starting with a set of integer points and then ...

**1**

vote

**0**answers

163 views

### Both NP-hard but different [closed]

What's the fundamental difference between the Knapsack problem and the travelling salesman (TSP) problem both of which are NP-hard, while the reality is that TSP could be solved much much faster?

**0**

votes

**2**answers

305 views

### Mixed integer programming formulation for Ising model

I want to implement a minimisation on a 2D spin Ising model with 30x30 grid. The spin variables is 0,1 and the objective is to minimize the sum of products of spins. For simplicity, I only include NN ...

**4**

votes

**0**answers

63 views

+50

### What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial
is a bivariate polynomial with positive integer coefficient which is a graph
invariant and can be defined recursively.
Evaluating it is $\#P$-complete even when restricted to ...

**0**

votes

**2**answers

217 views

### Approximate solution to large mixed integer programming problem

What are the available approaches to find an approximate solution to a large mixed integer programming problem?
I ran my problem in the Gurobi MIP solver.
It can find a feasible solution in ...

**3**

votes

**0**answers

89 views

### Choice of MIP (mixed integer programming) solver

I would start using MIP solver for the research on the tiling.
I know (heard of) the open source solver jump:
https://github.com/JuliaOpt/JuMP.jl
and also the gold standard solver from IBM cplex.
...

**3**

votes

**1**answer

330 views

### Name search for special Linear Integer Program

I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
...

**1**

vote

**0**answers

73 views

### integrality of a linear program — binary equality constaints

Consider the following linear program:
$\left\{
\begin{array}{l}
\underset{x}{max} \;\;c^Tx\\
[I, \;B]x = \mathbf{1}\\
x\geq 0
\end{array}
\right.$
where $c$ is a vector ...

**3**

votes

**2**answers

522 views

### Finding closest point to a set of circles

My requirement is to find the point closest to three circles. So lets say the three circles are C1, C2, C3. I want to find the point in the space such that the SUM of its distance from C1, C2 and C3 ...

**0**

votes

**0**answers

91 views

### Linear system with many solutions from a finite set

Basically I am looking for a linear system with
many solutions from a finite set.
Choose a finite set of rationals $S$ and fix
positive integer $k$.
Let $A$ be a linear system with $n$ variables ...

**1**

vote

**0**answers

64 views

### Are there any known bounds on the value of solutions of linear integer programming?

Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints?
...

**2**

votes

**2**answers

117 views

### Find the optimal set of subsets

Consider a set of $N$ individuals and let their distance be given by $R$, a $N\times N$ matrix. In that, $R(1,2)$ is the distance between individual 1 and 2. Now lets say that I want to separate the ...

**2**

votes

**2**answers

280 views

### Finding the maximum of a multivariate polynomial of degree one

I need to find the global maximum of the function
\begin{align}
f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\
&+\ldots \\
&+ p_n ...

**1**

vote

**0**answers

172 views

### Complexity of Nested Linear Optimization

My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
...

**1**

vote

**0**answers

403 views

### Subtour Elimination in Travelling Salesman Problem using MTZ

I am trying to formulation a problem similar to a Traveling Salesman with Time Window constraints.
To eliminate subtours, I need to use some constraint similar to a generalization of MTZ constraints ...

**4**

votes

**2**answers

525 views

### Simplified knapsack problem

There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...

**2**

votes

**1**answer

545 views

### Finding integer points inside of a parallelogram

Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...

**2**

votes

**0**answers

139 views

### existence of lattice point in polytope

This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...

**3**

votes

**0**answers

234 views

### Beating Kadane's Algorithm

I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...

**2**

votes

**2**answers

99 views

### LP constraint enconding

I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...

**1**

vote

**1**answer

122 views

### Separation of Anti-Hole Inequality

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent.
An induced subgraph $H$ of $G$ is called an odd-antihole ...

**1**

vote

**0**answers

59 views

### What is the solution to \min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}

(I've posted this question at Math.SE but got no answer, so I hope I can get a solution here.)
This problem looks familiar, but I don't remember its solution:
$$ \min_k \ \ \frac{b^k/n}{\lfloor ...

**5**

votes

**2**answers

498 views

### Area of a lattice polygon in terms of its width

Let $M$ be a lattice polygon on a plane (i.e. its vertices are integer points $(i,j)\in\mathbb Z^2$).
Let us define lattice width in a direction $v=(m,n)\in\mathbb Z^2$ as $w_v(M)=\max\limits_{x,y\in ...

**1**

vote

**1**answer

402 views

### Reference Request for Integer factorization with LP/ILP

Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...

**1**

vote

**2**answers

294 views

### Brute force lattice problems

What are the easiest brute force algorithms for solving closest and shortest vector problems?
I want to find an arbitrary, but small ($\lesssim 20$) number of lattice vectors closest to a given ...

**0**

votes

**1**answer

3k views

### If then condition on mixed linear integer programming [closed]

Hi all. Let $a$ and $b$ be two real variables such that $0 \le a \le a_{max}$ and $0 \le b \le b_{max}$. I must write the following if-then-else condition with linear inequalities:
if $a < ...

**0**

votes

**0**answers

235 views

### LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...

**0**

votes

**1**answer

319 views

### $\ell_o$ Minimization (Minimizing the support of a vector)

I have been looking into the problem
$\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...