**2**

votes

**0**answers

28 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

130 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

46 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
...

**1**

vote

**1**answer

88 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

73 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

37 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 ...

**2**

votes

**0**answers

150 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

**0**answers

64 views

### polynomial 0,1 integer programming

IS there a mathematical optimization branch that explicitly tries to optimize this (type) problem?
$$\eqalign{
& \min \cr
& \sum\limits_{i = 1}^N {(J*s[i] + {J_1}*s[i]*s[i + 1] + ...

**0**

votes

**2**answers

283 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

35 views

### 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

90 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 ...

**2**

votes

**0**answers

69 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.
...

**2**

votes

**1**answer

190 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

57 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

268 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

87 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

61 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?
...

**0**

votes

**0**answers

46 views

### Multi-objective set-cover optimisation problem

I'm looking for an algorithm to solve the following multi-objective set-cover problem.
We start with a 'universe' (set) of items $\mathcal{U}$, along with a partitioning $P = \{p_0,\ldots,p_m\}$ ...

**2**

votes

**2**answers

99 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

150 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

115 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:
...

**2**

votes

**0**answers

187 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

398 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

349 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

130 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

186 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

94 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

108 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

478 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

352 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

229 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 ...

**-1**

votes

**1**answer

2k 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

174 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

174 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 ...

**2**

votes

**2**answers

853 views

### is there a solution to system of linear Diophantine equations?

I have a matrix A \in Z^{n \by m}, where m > n and a vector b \in Z^n. Then, under what conditions does an integer solution exist to the equation
Ax = b.
Is there a way to bound the norm of the ...

**2**

votes

**1**answer

760 views

### sum of maxima vs the maximum of the sum

Consider the following integer program
$$
\begin{align}
\max &\sum\nolimits_{i}\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\\
\text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant ...

**0**

votes

**0**answers

194 views

### Maximum subset of set of Integers with minimum distance

Hi, i have a set of integers for example: {0,1,3,100,102} and i am looking for a maximum subset in which all elements have a minimum distance to all elements (or the "next" doesnt matter i guess) for ...

**4**

votes

**0**answers

292 views

### Matching a binary matrix

Given a MxN 0-1 matrix D, with the property that
both M and N are odd numbers
its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1).
How do we find M ...

**1**

vote

**2**answers

382 views

### Sherali-Adams relaxation

I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...

**1**

vote

**1**answer

829 views

### Multiple disjoint subset sum problem

Given two sets of nonnegative integer numbers:
$X = {x_1, x_2, ... x_n}$
$Y = {y_1, y_2, ... y_m}$
Need to find partition of $X$ on $m$ disjoint subsets, such as sum of elements in $i$-th subset ...

**3**

votes

**0**answers

696 views

### 0,1 solution to system of linear integer equations.

I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...

**4**

votes

**3**answers

719 views

### Lattice points close to a line

Take a sheet of grid paper and draw a straight line in any direction from the origin. What is the closest non-zero grid point $\boldsymbol{p}\in\mathbb{Z}^2$ within a distance $\epsilon>0$ of the ...

**0**

votes

**0**answers

117 views

### Question on non-linear parametric mixed integer program

I am trying to solve a mixed integer minimization problem, where there are a number of parameters, and there are products of parameters with variables appearing in the objective function. I assume ...

**3**

votes

**1**answer

263 views

### Partially optimal solutions in integer linear programming

Linear programs with a totally unimodular system matrix are known to have an optimal integer point. They are therefore solvable via relaxing the integer constraints to intervals.
An other interesting ...

**5**

votes

**2**answers

461 views

### Some weird “system” of inequalities in nonnegative integers.

Suppose I have a bunch of nonnegative integers $(a_{ijkl})_{1 \leq i \leq j \leq k \leq l \leq 17}$ such that for all 17-tuples nonnegative integers $w_t$ (for $1 \leq t \leq 17$) we have that ...

**4**

votes

**1**answer

707 views

### Minimum distance between adjacent concentric circles that cross integer lattice points

This problem looks simple, but I searched around and couldn't find any similar problems or related resources. Hope someone could provide a clue or at least a hint of what class of prolbems it belongs ...

**1**

vote

**1**answer

208 views

### Representing integer points inside a polytope using a unit hypercube

Let $D\subset\mathbb{Z}\times\mathbb{Z}$ such that $D$ is formed by the points bounded by a convex polytope. Let $f:D\to\mathbb{R}$ defined by $f(x,y)=ax+by+c$, where $a,b,c\in\mathbb{R}$ and ...

**1**

vote

**1**answer

214 views

### Spectral analysis of sparse symmetric integer matrices

Hi all,
A project I'm currently working on requires me to compute the eigenvectors / eigenvalues of sparse symmetric integer matrices. This is needed in the context of Principal Component Analysis. I ...

**0**

votes

**0**answers

140 views

### Knapsack Constraint

I'm trying to implement a recursive algorithm that I came up with that first solves the knapsack for a given objective and then cuts off the solution and then finds the next best solution.
However, I ...