Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

2
votes
2answers
153 views

Finding the index such that all partial sums are nonnegative

Given an array a[] of integers of arbitrary size N that sum to 0 (for example, a[] = {-1, 0, 5, 3, -9, 2}), does there always exists an index i ($0\le i\le N-1$) such that each partial sum $S_j = ...
1
vote
0answers
55 views

Regression/compressive sensing with non-linear constrains where the coefficients are assumed to be integer or binary {0,1}

The following regression problem $$ \mathbf{y} = \mathbf{A}\mathbf{x} $$ where $\mathbf{y}$ is a $N\times 1$ column real vector, $\mathbf{A}$ is a $N\times M$ real matrix where each column ...
0
votes
1answer
158 views

Maximize two-variable linear function

How would you maximize the following function (with integer domain) $$f(x,y) = a * x + b * y$$ subject to $$c * x + d * y \leq N$$ $$x \geq 0, y \geq 0$$ the constants $a, b, c, d, N$ are known ...
2
votes
1answer
302 views

Minimize $\|Ax-b\|$ where $x$ is a binary vector

For a software project I'm involved on, I have a situation where I have a large vector that is the sum of some smaller vectors. I know all the possible small vectors, and I know that no two of them ...
1
vote
2answers
141 views

Checking inequality without actually calculating LHS and RHS

How to check whether the following inequality is true or not without actually calculating the values of $x^y $ and $y^x $: $$ x^y > y^x$$ (x and y are integers)
1
vote
0answers
41 views

How to find best set of customers

I've got a problem with getting optimized solution from this task: We have n customers, which buy articles from m suppliers. There are much more customers and suppliers on the market. We've got sales ...
0
votes
2answers
197 views

Simplex and mathematical models: Truncating expresion to 0 if negative

Is there a simplex compatible way to model an expression that "truncates" (sorry for not finding a better word for it) the value to 0 if it turns negative? I have the following restrictions: ...
1
vote
1answer
214 views

Ordered pair of positive integers

One holiday, I gave each of my 3 grandsons x coins and each of my 4 granddaughters y coins. The total number of coins that I gave to my grandchildren will allow for only one ordered pair of positive ...
1
vote
0answers
214 views

Strange but practical Bin packing problem

I am trying to solve the following MILP through LP solve. A link for the original problem is here I am re-iterating the problem as follows: I am trying to write an application that generates drawing ...
1
vote
1answer
53 views

How to schedule different planks to form bridges

Suppose we want to walk from place $A$ to place $B$, but there are several rivers between them. In order to walk from place $A$ to place $B$, we need to build a bridge for each river. We have ...
0
votes
2answers
2k views

Integer Solutions for linear equation

What are the different methods for solving a linear equation with integral Solutions? Which one is preferred over other? What is the best method? For example, 3x + 5y = 12309834576, How do I find ...
1
vote
1answer
633 views

How to evaluate n in nCr when nCr and r known?

Today i was solving a programming problem and got stuck at this position. Value of nCr is given where r = floor((n+1)/2). We will have to find the value of n ? Help, please.
0
votes
1answer
115 views

Intersection of Cartesian product and set - what is the meaning?

I came across the following two definitions in a book about Integer Programming: Definition 1.1 A subset of $R^n$ described by a finite set of linear constraints $P=\{x \in R^n: Ax \leq b \}$ is a ...
1
vote
0answers
80 views

Speeding up solution of a binary integer program

To solve the problem of making a "good" schedule for a tournament between N teams, using memories from my (long gone) student days, I expressed it as a binary integer program. With the current set of ...
0
votes
1answer
14 views

Taking to values and turning them into precentages

I want to basicly take a range of two values so for example 20-40 and then taking a value in between for say 30 and somehow mathematicly make it say that it is 50% between the values. This should work ...
0
votes
1answer
65 views

Checking whether a solution to MIP is optimal

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 ...
1
vote
1answer
79 views

Modal logics and logics with integer or even rational numbers - is that possible?

I am trying to find some research trends (publications, keywords for futher search, etc.) on logics and modal logics whose predicates can containt integer or even rational numbers (like x>2, x^2>3, ...
1
vote
1answer
40 views

Does a linear expression exist for these ILP variables?

I am formulating an integer linear program. Suppose I have a set of binary variables $X_{i,j,k}$ that is $1$ if subject $i \in I$ is taught by lecturer $j \in J$ during timeslot $k \in K$, or $0$ ...
2
votes
3answers
137 views

Finding $a + b + c$ given that $\;a + \frac{1}{b+\large\frac 1c} = \frac{37}{16}$

Please help me to find the needed sum: If $a,b,c$ are positive integers such that $\;a + \dfrac{1}{b+\large \frac 1c} = \dfrac{37}{16},\;$ find the value of $\;(a+b+c)$. Thanks!
1
vote
0answers
40 views

Program to determine the relationship of one variable to several possible variables

Suppose I have a system with several variables a, b, c, d, and x. I am trying to solve for the unknown x. I don't know exactly which of those variables x is dependent on, or exactly how the function ...
1
vote
0answers
120 views

Why these two problems lead to same answers?

Suppose these two problems: Problem 1: $$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad ...
2
votes
2answers
54 views

Can one simplify a $3$-term max function, where one term is comprised of subterms from other two?

Is the expression $\max(a + b, b + c, c + d)$ in its simplest from? Assuming $a,b,c,d$ are positive integers. What I've Tried: I've tried several approaches but they all end up as either: ...
0
votes
1answer
38 views

Converting Maximum TSP to Normal TSP

Consider the Travelling Salesman Problem: Given N cities connected by edges of varying weights. Given a city A what is the shortest path for visiting all the cities exactly once that returns back to ...
1
vote
0answers
510 views

How does Microsoft Excel Solver's Simplex algorithm deal with integers?

I was wondering how the Simplex algorithm in Excel's Solver deals with integers. From what I understand, the Simplex algorithm is meant to be used for linear programming/optimizations only. Yet, Excel ...
2
votes
0answers
58 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 ...
1
vote
1answer
72 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
63 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 ...
3
votes
1answer
91 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
33 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 ...
1
vote
1answer
3k 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. ...
1
vote
1answer
781 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
85 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
174 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
337 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
177 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
372 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 ...
4
votes
3answers
102 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
2k 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
138 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
126 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
301 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
424 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
229 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
2k 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
83 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
104 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
412 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
108 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
87 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
214 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 ...