Questions on optimization constrained to integer variables.
7
votes
2answers
220 views
Mean and Median in a Classic River Crossing Problem
Consider the following classic problem:
Four people on the west side of a river wish to use their single boat to get to the east side of a river. Each boat ride can hold at most two people, and the ...
5
votes
2answers
109 views
Minimize sum of smallest and largest among integers on the real line.
Suppose there are 3 non-negative integers $x$, $y$ and $z$ on the real line.
We are told that $x + y + z = 300$. Without loss of generality, assume
$x$ to be the smallest integer, and $z$ to be the ...
4
votes
4answers
251 views
Good software for linear/integer programming
I never did any linear/integer programming so I am wondering the following two things
What are some efficient free linear programming solvers?
What are some efficient commercial linear programming ...
4
votes
1answer
105 views
Determining quickly whether this Integer Linear Program has any solution at all
I've got an integer linear program of the form
$$
\begin{aligned}
\text{Minimize}&& c &= x_1 + \cdots + x_m \\
\text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\
\text{where}
...
4
votes
0answers
122 views
On the integer feasibility of polytopes defined by idempotent integer matrices
EDIT: I realized that while writing this question, I was reasoning about orthogonal projections. Thus, I forgot to transpose when forming the projection on to the space orthogonal to the image of $P$. ...
3
votes
2answers
236 views
For a fixed positive integer n, show that the determinant below is divisible by n
For a fixed positive integer n, if
$D = \left|\begin{array}{ccc}
n! & (n + 1)! & (n + 2)! \\
(n + 1)! & (n + 2)! & (n + 3)! \\
(n + 2)! & (n + 3)! & (n + 4)!
...
3
votes
5answers
53 views
Why is my procedure misleading?
Max: $ z = 10( x_1 + x_2)$
subject to constraints:
$$ 2x_1 + 5x_2 \leq 16 $$
$$ 6x_1 + 5x_2 \leq 30 $$
$$ x_1, x_2 \in \mathbb{Z^+} $$
I have the Integer Programming ...
3
votes
1answer
55 views
A particular ILP where the existence of a relaxed solution implies the existence of an integer solution
This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately.
I am ...
3
votes
2answers
61 views
How does one find the minimum of an equation of integers?
Going through a book of probability problems and am working on the Sock Drawer Problem:
A drawer contains red socks and black socks. When two socks are drawn at random, the probability that both ...
3
votes
1answer
69 views
Is the inverse of an invertible totally unimodular matrix also totally unimodular?
My question is learned from here. Let me restate it as follows:
A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
3
votes
1answer
130 views
Efficiently solving a special integer linear programming with simple structure and known feasible solution
Consider an ILP of the following form:
Minimize $\sum_{k=1}^N s_i$ where
$\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of ...
3
votes
1answer
171 views
Connected graph solution from IP/LP
I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties.
I have problems formulating the connectedness condition in an IP/LP.
The ...
3
votes
0answers
84 views
How to minimize $\min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}$
This problem looks familiar, but I don't remember its solution:
$$ \min_k \ \ \frac{b^k/n}{\lfloor b^k/n \rfloor}k $$
subject to
$$ b^k \ge n \\ b,n,k \in \mathbb{N} $$
Does it have a name? What's ...
2
votes
1answer
78 views
Maximizing the number of non-crossing lines between a number of points
Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross.
Hoping for a polynomial time algorithm, I ...
2
votes
1answer
60 views
Integer solutions to a hyperbola
Is there a way to find all integer solutions to a hyperbola equation? If it helps, I am specifically looking at "square" hyperbolas (i.e. of the form $\frac{x^2}{z} - \frac{y^2}{z}=1$), where z is an ...
2
votes
3answers
77 views
How to formulate Unique value constraint in Integer Programming?
Given the following integer programming formulation, how can I specify that the variables are unique and none of them has the same value as the other one. basically ...
2
votes
2answers
132 views
Prove or disprove a chessboard with diagonal corners removed, cannot be tiled with L shape pieces or size 2
I think this is impossible, but I don't know how to prove an integer solution doesn't exist for a given equation. Here's my approach:
First, observations:
The removed tile will be of the same color. ...
2
votes
1answer
80 views
Unimodular matrix definition?
I'm a bit confused. Based on Wikipedia:
In mathematics, a unimodular matrix M is a square integer matrix
having determinant +1, 0 or −1. Equivalently, it is an integer matrix that is invertible ...
2
votes
1answer
181 views
Solving a knapsack-type problem
I'd like a good way to solve an optimization problem I came across. It's a constrained knapsack problem: I want to find integers
$$1=a_1\le a_2\le\cdots\le a_t$$
$$a_1+a_2+\cdots+a_t=N$$
with $t$ ...
2
votes
1answer
92 views
Linear programming problem with no objective function
I have a binary integer programming problem for which I only need a solution that meets all the constraints. I do not have an objective function that I am trying to minimize or maximize.
I've been ...
2
votes
1answer
141 views
Is there a formula for nCr that considers a min/max range? (restricted composition estimation)
I'm bad at math and hope I explain this right(please don't be upset if I don't, I'm not trying to be lazy or a jerk, I really don't understand what information is sometimes required and focus on the ...
2
votes
3answers
133 views
Linear inequalities to make a specific solution infeasible
Say we have a binary linear programming problem:
\begin{equation*}
\begin{aligned}
& \underset{\mathbf{x}}{\text{minimize}}
& & c\cdot\mathbf{x} \\
& \text{subject to}
& ...
2
votes
0answers
41 views
Clarification of variable values in Arithmetic Coding algorithm
I have been trying to follow this video to implement my own Arithmetic Coding algorithm in Java. I am having a bit of trouble figuring out what some of the variables in the video should be.
For ...
2
votes
0answers
64 views
Binary optimization
Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows:
There are ...
2
votes
1answer
34 views
Linear Programming: Breaking Variables Product
Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables?
...
2
votes
1answer
110 views
Determining Weights of Columns For A Prioritization Matrix
I'm trying to calculate the weight of various tasks. I have tasks that are daily, weekly, monthly, yearly. As a task gets closer to due date, I'd like it to be more important. For example, a weekly ...
2
votes
0answers
71 views
Branch-and-Price algorithms for IP/MIP
I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
2
votes
0answers
94 views
An optimization problem involving Latin Squares
Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write ...
1
vote
3answers
808 views
Double summation
I'm currently solving some Operations Research exercises related to Integer Programming. In one of the solutions of the exercises the author uses the following formula for the objective function:
...
1
vote
1answer
39 views
Linear programming: expressing the fact that precisely $k$ variables are nonzero
Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero?
I suspect this would already be enough to simulate ...
1
vote
1answer
202 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 ...
1
vote
1answer
68 views
Linear Programming for Integer Solutions
Connsider the linear programming problem Max $z = 5x_1 + 6x_2$ st. $10x_1 + 3x_2 \leq 52,2x_1 + 3x_2 \leq 18$ and $x_1, x_2 \geq 0$ and integer.
How would one manipulate the resources so that the ...
1
vote
1answer
45 views
Are there 0-1-matrices that are not unimodular?
I am just wondering if there are matrices that only consists of $0$s and a few $1$s that are not totally unimodular (TU)? I cannot come up with an example but I am not very experienced with this ...
1
vote
1answer
138 views
Combinatorial Optimization Problem (can I/how do I solve this with integer programming?)
Inputs:
1) A set of M x N matrices, {A,B,C...N} containing only integers.
2) A single 1 x N matrix of floats, W (weights).
I need to pull one row from each input matrix and sum values for each ...
1
vote
1answer
27 views
HINT for summing digits of a large power
I recently started working through the Project Euler challenges, but I've got stuck on #16 (http://projecteuler.net/problem=16)
$2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = ...
1
vote
1answer
41 views
How tell if a polyhedron contains a lattice point
So given a polyhedron
$Ax \le b$
Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point)
I was thinking a couple things:
brute force ...
1
vote
1answer
68 views
Linear programming vs. Integer programming
I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that ...
1
vote
1answer
29 views
Efficient MIP reformulation for binary integer problem
Consider an integer programming model where there is some term $x_ix_j$ where the variables $x_i,x_j \in \{0,1\}$
I want to reformulate this into an efficient mixed-integer programming (MIP) problem.
...
1
vote
1answer
60 views
$ A = x + y + z$, number of solutions in $Z$ if $x, y, z$ are bounded in intervals
For the equation $x + y = A$, it's easy, when you notice that when iterating over all possible $x$, the number of solutions for $y$ is $0$ at the beginning, then increases by $1$, then stays constant, ...
1
vote
4answers
74 views
Procedures to find solution to $a_1x_1+\cdots+a_nx_n = 0$
Suppose that $x_1, \dots,x_n$ are given as an input. Then we want to find $a_1,\ldots,a_n$ that satisfy $a_1x_1 + a_2x_2+a_3x_3 + a_4x_4+\cdots +a_nx_n =0$. (including the case where such $a$ set does ...
1
vote
2answers
47 views
What's the relation between the non-convex sets and the hardness of ILP problems?
If some or all of the unknown variables are required to be integers,
then the problem is called an integer programming (IP) or integer
linear programming (ILP) problem.
If understand ...
1
vote
1answer
144 views
$\ell_0$ 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 has ...
1
vote
1answer
283 views
What are the algorithms for integer programming in which constraints are dependent?
What are some ways to deal with dependent constraints in integer programming?
For example, suppose I want to maximize $x+3y+2z$ subject to (i) $x+y<=3$ and (ii) if $y+z>=2$ then $x+z<=6$.
...
1
vote
1answer
116 views
Looking for a closed form to determine whether a symbol is part of the ith combination nCr
Hi I'm new to this, feel free to correct or edit anything if I haven't done something properly.
This is a programming problem I'm having and finding a closed form instead of looping would help a lot.
...
1
vote
1answer
362 views
Optimizing Nonlinear Constraint Equations with Discrete Variables and Multiple Objective Functions
I have the following constraint functions:
$$g_{i_{min}} \leq y_{i+1}-y_{i} \leq g_{i_{max}}$$
$$y_{i_{max}}-y_{i} \geq h_{i}$$
$$v_{i_{min}} \leq \Biggl[\frac{(y_{i+1}-y_{i})^{3} ...
1
vote
1answer
15 views
Minimizing deviations from threshold value from a given group of numbers
Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed ...
1
vote
1answer
46 views
Strict inequality in MILP
I have a problem with the following constraint. There are 2 variables
$p \in [0,1] \subseteq \mathcal{R}$
$\sigma \in [0,1] \subseteq \mathcal{Z}$
The constraint over the variables is
$c - p < ...
1
vote
0answers
26 views
Integer vector decomposition on a degenerate integer vectors basis
Let's say I have a vector of integer numbers, and I would like to get a decomposition of that vector using a set of "basis" vectors (which are also integers), these vectors are arbitrary, i.e. they ...
1
vote
1answer
48 views
Linear Integer Programming: consecutive/adjacent variables constraint
Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that:
$\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < ...
1
vote
0answers
42 views
Determining if data can be fit by a continuous piecewise integer-valued polynomial
This question concerns the sequence of integers which form the solution to a particular computational problem. See the bottom for the full formulation; basically, for some value n, $G(n)$ is the ...
