Questions on optimization constrained to integer variables.
1
vote
0answers
28 views
Quadratic Integer Programming
Would anyone mind helping me solve this problem
$$
\min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda
$$
where $x$ is a vector whose entries are positive ...
0
votes
0answers
18 views
Minimizing an expression with linear constraints
Given a system of under-constrained (i.e. infinite solutions) linear equations (all values will be integers, all coefficients will be 0, 1, or -1), I want to pick values for the variables to minimize ...
1
vote
0answers
26 views
Software for Binary Integer Linear Programs
I am aware that there is good software out there to solve integer linear programs (ILPs). However, is there (preferably free or low cost) software I could use to solve large binary integer linear ...
1
vote
0answers
19 views
If the following LP has an integral solution
I know the constraints matrix A of a linear program "Min cx such that Ax>=b" is totally unimodular. So, the program has integral solutions for integral vector b. If this is also the case for the ...
0
votes
1answer
21 views
How to prove the matrix is totally unimodular
Is there any (theoretic) way I can prove the matrix is totally unimodular? I have tested it by Matlab and know it is TU, however I cannot prove it.
...
-3
votes
1answer
54 views
Fortran 90 - Fibonacci squence [on hold]
i need help for this "problem" in fortran 90
-Write a program that displays the first screen 100 terms of this series.
-Find the sum of the first N numbers of succession.
Do? Do While?
Thank you ...
0
votes
1answer
26 views
linear programming constraint for conditional
I having formulating the following (what should be fairly simple) ilp constraint. Basically let $p$ be a binary variable and $s$ be an integer that is greater than or equal to 0.
The constraint is ...
3
votes
2answers
58 views
$ k x^2 +4x = n $, Algorithm or any other method needed
I want to find any $n < 10^{18} $ so that the equation below has at least two pairs of solutions $(k, x)$
$ k x^2 +4 x = n $
constraints: $x > 10^6; \; x > k ; \; k, x \in \mathbb{N}$
I ...
0
votes
0answers
92 views
+50
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
12 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 <= ...
0
votes
0answers
24 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
35 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
81 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
40 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 = ...
0
votes
0answers
27 views
formulate an ip to minimize cost
A car rental company has m branches. the number of cars currently available at branch i is vi. The company re-position its fleet at the beginning of every month to prepare for the demands of upcoming ...
1
vote
1answer
18 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
47 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
82 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
50 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 < ...
0
votes
1answer
32 views
“Location to location” algorithm?
Lets say I have two locations, each one with X, Y, Z, and a int. Each location represents one cube in a 1000 x 1000 world. Lets say I had one location at 500, 343, 284, with an int 1. Another one at ...
0
votes
0answers
28 views
Is round(x/y) equal or approximately equal to (x+y\2)\y?
I need a formula to divide integers with the correct rounding and found this one:
(x+y/2)/y
But will this work even if integer division is used in the ...
1
vote
1answer
52 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
87 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 ...
0
votes
1answer
30 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
0answers
29 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 ...
3
votes
1answer
92 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 ...
0
votes
0answers
33 views
Examples of exp. sized LPs that can be solved in polynomial time by the GLS variant of the ellipsoid method?
The GLS (grötschel lovasz schrijver) variant of the ellipsoid method is a method that can solve LP with exponentially many facets or variables (by considering the dual LP) in polynomial time if the LP ...
0
votes
0answers
42 views
How to represent probability as Integer - Arithmetic coding
I am doing an assignment for a class in college where we have to write an arithmetic encoder / decoder in Java.
In this video, it shows how to set up / define all the variables required for the ...
2
votes
0answers
44 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
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 ...
2
votes
1answer
90 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 ...
0
votes
0answers
21 views
Finding “good” values with regards to split disjunctions
We've been given an assignment in a course on Mixed-Integer Optimization, and one of the questions is about split disjunctions, or more precisely, finding good values for a split disjunction in order ...
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 ...
0
votes
0answers
30 views
How do I find the set of integers solving a system of equations that contain outliers?
I have a system of $s$ equations that should (but won't) all equal some real unknown scalar value, $x$:
$x = v_1*k_1 + a_1*k_1*m = v_2*k_2 + a_2*k_2*m = ... = v_s*k_s + a_s*k_s*m$
where,
$k_i$ are ...
1
vote
1answer
32 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
101 views
Finding sum of all integral parts
Moderator Note: This is a question in a current contest.
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 ...
0
votes
1answer
38 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
52 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
55 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
110 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
0answers
67 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
92 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
106 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
50 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
82 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
58 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
111 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
48 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
57 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 < ...
