All Questions
8 questions
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
1
vote
0
answers
37
views
Fast certficate of negativity for objective value of mixed-integer linear program
Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP)
$$
\begin{split}
f^* = &\max \; ...
- 6,853
1
vote
1
answer
330
views
How good is the LP relaxation?
Consider the optimization problem
\begin{align}
\max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i
\end{align}where $c,b\in\mathbb{R}_{+}^n$ and $A\in\mathbb{R}_{+}^{n\times n}$...
- 1,421
2
votes
0
answers
120
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 ...
- 127
1
vote
0
answers
75
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?
...
- 111