Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
0answers
43 views

How to express coprimality as a constraint in an optimization problem over integers?

I am currently working with an optimization problem that is defined over a a set of $D$-dimensional integer vectors where each component is bounded by $M$. Let us refer to this optimization problem ...
0
votes
1answer
30 views

Sufficient conditions for relaxed integer programs to have integer solutions.

Suppose we are given an integer program and we remove the integrality constraints to get a relaxed linear program. Are there a set of sufficient conditions on the form of the linear program, (e.g. ...
1
vote
1answer
25 views

Is a finite integer subset of a convex real set convex?

Specifically, can I take a convex real set, show that the definition of convexity holds for it, and then make claims based on that definition of convexity for an integer subset? I know that the ...
6
votes
3answers
233 views

Integer Programming problem

I have an integer programming problem with $L$ variables $x_1, x_2, x_{L}$ which all assume integer values and the following constraints must stand: $x_i \geq 0$ $x_1 = 10$ $x_2 + x_3 + ... + x_{L} ...
0
votes
0answers
47 views

Integer programming with pairwise relaxations: optimality?

In David Sontag's thesis [1] (page 11, 3rd paragraph from the end), it is mentioned that "Most previous linear programming approaches to approximate inference optimize over the pairwise LP ...
0
votes
0answers
73 views

Formulating a bilinear optimization problem as an integer linear program

In my work, I came across the following problem: Given a similarity matrix D, where $d_{i,j} \in \Re$ represents the similarity between objects $i$ and $j$, I would like to select $k$ objects, for $k ...
1
vote
2answers
75 views

Why do Integer Relation Algorithms (e.g. PSLQ) not solve the subset sum problem?

I'm trying to understand what mistake I'm making or what incorrect information I fail to recognize as such. The subset sum problem (given distinct $a_i$ and $A$, does any subset of ${ a_i }$ sum to ...
0
votes
1answer
57 views

Integer Programming

I've been having trouble getting started with this problem. Suppose $x_1,x_2,x_3$ are integers $\geq 0$, satisfying $$21.7x_1-18.2x_2-19.4x_3=5.3$$ Then show $$7x_1+8x_2+6x_3=3+10z_1$$. ...
0
votes
1answer
199 views

general formula for an orthogonal projection of a point onto a line

Could someone confirm this or correct the mistakes because this seems somehow wrong although I doublechecked it. Mx,My are coordinates of a point and Px,Py,Kx,Ky are coordinates of a line on a ...
2
votes
2answers
100 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
37 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
105 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
167 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
91 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
38 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
89 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
138 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
167 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
50 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
938 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
424 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
83 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
65 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
13 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
46 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 ...
0
votes
0answers
43 views

Difficulty finding linear expression for my simple table assignment BILP

I'm trying to solve a table seating problem as a binary integer linear program. Suppose $X_{i,j}$ is $1$ if person $i$ sits at table $j$ and zero otherwise, and $p_{i,k}$ is the penalty associated ...
1
vote
1answer
67 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
35 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
123 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
34 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
92 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
50 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
32 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
324 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
56 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
64 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
52 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 ...
2
votes
1answer
68 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
28 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
1k 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
280 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
80 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
171 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
144 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
138 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
238 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
715 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
77 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 ...