Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
1answer
50 views

Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements ...
1
vote
0answers
31 views

integer programming with bounded dimension

We know that integer programming with bounded dimension or fixed number of variables can be solved in polynomial time by Lenstra's result(from results of the LLL algorithm). After heavy foraging i ...
0
votes
1answer
49 views

Mixed integer programming with quadratic obj and quadratic constraints?

I was trying to use cplex for matlab to solve my optimization problem. However, It seemed to me that cplex was only able to solve PURE integer programming problem with quadratic objective function and ...
1
vote
1answer
30 views

organizing rectangles on top of each other

We have some rectangles that should be organized in a number of columns. Each column height should be in the range of $[H, H+d]$ in which $d$ is a small number relative to the height of the ...
0
votes
1answer
15 views

Global consistency of constraints in a MIP program

How does a Mixed Integer Programming (MIP) solver ensure global consistency of constraints while adding an additional constraint (during branch and bound). A naive method would be to add the ...
1
vote
0answers
17 views

Internals of a MIP Solver

I would like to learn about the internals of a Mixed Integer Programming (MIP) solver. Which concepts shall I read about? Are there a couple of standard books which can be a good start?
2
votes
1answer
92 views

Find known number of missing natural numbers

Given a set $S$ of distinct natural numbers, we know that a subset $T$ that is $S$ with at most $k$ number of elements missing. Let $M_k := \big\{m_j\big|d_j = \sum_{i\in T}i^j, j\in ...
0
votes
0answers
28 views

Algorithm Request, choosing rows from a sparse table of integers to sum to a minimum row value

I'm writing some software, and one part of the software needs to be able to solve this problem as well as possible. Consider a table of integers and goal, for example: $$T = \begin{array} ...
1
vote
0answers
169 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
0
votes
0answers
89 views

Minimum cost problem

I have been given $n$ points on a $2d$ plane. In terms of their $(x,y)$ coordinates. Now suppose I have to set, say firms, at these positions and the cost for building the first one is zero. For every ...
0
votes
0answers
22 views

Binary IP - Binari-zed result of negative value to 0, and positive value to 1

I have a set of variables $T_i = \{22, 23.6, 24, 24.2, 25\}$ and a constant value $C=24$. Given $$ a =T_i - C $$ I'd like to turn the result of subtraction a to binary value $\{0,1\}$, such that if ...
1
vote
0answers
44 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
34 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
28 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
234 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
50 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
1answer
87 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
80 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
58 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
233 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
105 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
39 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
106 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
186 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
97 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
105 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
148 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
173 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
1k 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
463 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
92 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
67 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
49 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
69 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
124 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
35 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
99 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
337 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
57 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
66 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
53 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
71 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
30 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. ...