**1**

vote

**0**answers

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

**0**

votes

**0**answers

74 views

### Global and local maxima in a weighted sum of logarithms of linear functionals?

Constrained Optimization Problem
Is is possible to describe, and locate efficiently, the maxima of the function $f$, as described below in the parameters $\mathbf{x} = (x_1,...,x_m)$. The constraints ...

**0**

votes

**0**answers

36 views

### Least square problems with binary variables

I want to solve the heat equation $T_t(x,t) = - L_x . T(x,t) + F(x,t)$ in an edge-weighted graph where $L_x = \sum_i x_i e_{ij}$ is weighted Laplacian matrix of the graph. Then I conclude to the ...

**1**

vote

**1**answer

122 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

177 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

145 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

72 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

190 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

77 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

49 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

161 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

293 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

41 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

136 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

77 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

261 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

64 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

339 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

89 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

62 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

104 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

193 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

126 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

271 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

447 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

417 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

132 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

206 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

97 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

116 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

484 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

368 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

257 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

195 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

208 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

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

986 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

225 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

297 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

451 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

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

828 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

796 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

120 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

272 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

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

**5**

votes

**1**answer

762 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

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