Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
0answers
173 views

Its just one point… How do I find it?

Okay so here is the deal... I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$) and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$ where $0 \le ...
1
vote
1answer
153 views

Characterization of Subset Sum via Linear Programming

I have a sample subset sum problem. Given numbers $x_1, x_2... x_N$ and a target value to sum to $x_S$ Minimize $x_S - x_1y_1 - x_2y_2 - x_3y_3 ... x_Ny_N$ such that 0 <= $y_1$ <= 1 0 <= ...
1
vote
1answer
142 views

Integer linear programming, energy constrained max-flow problem, column generation

We have graph $(V,A)$, $V$ is teh set of nodes, $A$ is the set of arcs. There is a source node $s \in V$ and a sink $t \in V$. Each node $i$ has a battery with capacity $E_i$. Sending flow on arc ...
0
votes
1answer
244 views

Integer Linear Programming (ILP): NP-hard vs. NP-complete?

I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind. It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
3
votes
3answers
93 views

How do one solve a nonlinear combinatoric problem?

I am an undergraduate CS student and I am struggling with a problem. $Qx = b$ where $Q$ is a constant $m \times n$ matrix (with $m>n$), $x$ is a $n \times 1$ vector and $b$ is a $m\times 1$ ...
1
vote
1answer
950 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
86 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 ...
0
votes
1answer
107 views

Partial linear relaxation yields an integer solution

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
3
votes
2answers
189 views

How many solutions are there to $abc+def=ghi$, where $a,b,\ldots, h,i$ are distinct non-zero digits?

I saw this problem posted by Google. Those posting in the comments found solutions using computer programming. I would like to know if there is an easier solution than trying every single combination. ...
1
vote
1answer
206 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
1answer
160 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
1k 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
62 views

Finding a solution for quadratic inequality

Given $r$ and $t$, Is there a way to find the maximum positive integer $N$ such that: $$2 N^2 + (2r+3)N + (2r+1) \leq t$$ I want to write a program to solve that inequality without brute-force. At ...
1
vote
1answer
86 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 ...
4
votes
1answer
279 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 ...
2
votes
0answers
90 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 ...
4
votes
0answers
86 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 ...
1
vote
1answer
157 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 ...
2
votes
1answer
434 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 ...
3
votes
5answers
57 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 ...
1
vote
1answer
66 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
votes
1answer
141 views

Finding sum of all integral parts

Given two numbers $M$ and $N$, Let $q_i$ be the integer part of $\frac{iN}{M}$. What is $$ \sum_{i=0}^{M-1} q_i? $$ The Sum is obviously can be calculated in $O(M)$. Can this be done in less time, ...
0
votes
1answer
64 views

Cutting plane in IP system

I am doing branch-and-bound for 5 decision binary variables. so Decision would be 0 and 1. and I found sub-problem node Q with optimal value 5.4 (0.3, 0.2, 1, 0.5, 0.1) my IP constraints are ...
1
vote
1answer
151 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 ...
0
votes
3answers
385 views

Binary Programming with nonlinear constraints

i have the following type of problem i'm interested to solve: Minimize the objective function: $f(x_1,\ldots, x_8) = \sum_{i=1}^8 a_i x_i$ with $a_i \in [0, \infty)$ and $x_i \in \{0,1\}$ and given ...
2
votes
1answer
397 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 ...
3
votes
0answers
114 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
238 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 ...
0
votes
1answer
237 views

Integrating the step-wise integer function 1/[x]

I'm trying to find the integral, respective to $x$, of a function that utilizes the step-wise integer (or floor) function. $$\displaystyle z = \int {1 \over [[x]*1.1^{[y]}]+1}$$ It's for modelling a ...
0
votes
1answer
115 views

integer programming formulation problem

Consider a problem with three variables: $u$, $\sigma_l$, and $\sigma_w$ where $\sigma_w > \sigma_l$. I want to represent the following relationship using integer programming. \begin{equation} u = ...
2
votes
3answers
190 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 ...
3
votes
1answer
93 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 ...
4
votes
1answer
301 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} ...
2
votes
1answer
247 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? ...
1
vote
1answer
172 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 < ...
4
votes
0answers
155 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$. ...
1
vote
1answer
64 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
0answers
94 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 ...
1
vote
4answers
83 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 ...
2
votes
1answer
303 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
1
vote
1answer
85 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 ...
7
votes
5answers
3k 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 ...
0
votes
1answer
89 views

Converting loop to a closed form expression? [duplicate]

Possible Duplicate: How to convert this loop into a closed form expression? I have the following code in Python ...
2
votes
2answers
268 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. ...
0
votes
1answer
26 views

Finding the solutions of $ax+by\le D$

Given parameters $a,b,D$, all integers, I want to find all the integer solutions $(x,y)$ of $ax+by\le D$ Or at least a nice way to characterize them. Also, for a given $R$, it is actually enough for ...
2
votes
1answer
291 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 ...
0
votes
0answers
50 views

How to formulate or statment in integer programming

I need to formulate below statement in integer linear programming. if x+y=2 then (a+b<c or c+g<a) Can you help me please?
7
votes
2answers
274 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 ...
0
votes
1answer
111 views

Approximate rational number of radical combination

Suppose that there is a radical combination $a\sqrt{b}+c\sqrt{d}$ where a,b,c,d are natural. Each term part $\sqrt{b}$ cannot be transformed into the form of $s\sqrt{q}$. The question is, 1) Suppose ...
1
vote
1answer
154 views

way of converting an approximate rational number of radical combination into original form

Suppose that there is a radical combination $a\sqrt{b}+c\sqrt{d} ...$. where $a,b,c,d\in \mathbb{N}$, for which each term part $\sqrt{b}$ cannot be transformed into the form of $s\sqrt{q}$. The ...