# Tagged Questions

**0**

votes

**0**answers

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

**1**

vote

**0**answers

41 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

33 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

101 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

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

**4**

votes

**2**answers

332 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

235 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

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

**1**

vote

**2**answers

93 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

325 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**

votes

**1**answer

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

162 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

**0**answers

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

**1**

vote

**2**answers

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

**2**

votes

**0**answers

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

**3**

votes

**1**answer

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

**4**

votes

**1**answer

217 views

### Symmetry of the integer gap

Are there results that bound the asymmetry of the duality gap of an integer program? That is to say, if the difference between the LP solution and the IP (primal) solution is $a$, is there a function ...

**1**

vote

**3**answers

1k views

### How to solve Linear Programming problem with tighter Integer Programming constraints

I want to learn a bit about Linear Programming.
After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...

**4**

votes

**1**answer

2k views

### Proving that a binary matrix is totally unimodular

I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...

**1**

vote

**1**answer

426 views

### When is a triangular matrix totally unimodular?

I have an {0,1}, invertible, triangular matrix, that I would like to show to be totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?