Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
0answers
12 views

How is the upper bound of a minimisation IP determined during branch-and-bound?

When using the branch-and-bound algorithm to solve an Integer Programming (IP) problem, the entire enumeration tree doesn't need to be evaluated and that's where the speed-up is achieved. Suppose the ...
1
vote
1answer
32 views

Why optimization problems cannot be solved by simple derivative?

Let $f(\cdot)$ be a linear function. $f:\mathbb{R}^n\rightarrow\mathbb{R}$ $\;\quad\;\mathbf{x}\;\rightarrow f(\mathbf{x})$. Let $\mathbf{A}$ be a matrix in $\mathbb{R}^{m\times ...
0
votes
0answers
14 views

integer programming variable linearization

I have the following problem, two binary variables X1 and X2. I want that a third binary variable Z is equal to 1 if and only if X1=a and X2=b while it must be 0 otherwise, where a and b are given ...
0
votes
0answers
23 views

Mixed Integer Non Linear Problem for Relaxation Approach

I have the following problem. I have meat markets$(\mathcal{T}_1)$ and vegetable markets$(\mathcal{T}_2)$. $(\mathcal{T}_1) \cup (\mathcal{T}_2) = T$ and $(\mathcal{M}) \cap (\mathcal{V}) = ...
1
vote
0answers
24 views

Is there such a thing as a bounded integer lattice?

I am currently working on a project where I have to minimize a function $f$ over a discrete set: $$ P = \Bigg\{\sum_{i=1}^N{\lambda_i x_i}~\Big |~ x_m \in \mathbb{R^m} \text{ and } \lambda_i \in ...
2
votes
0answers
26 views

Find bounded integers $x, y$ minimizing $| t - x * y |$

How do I find the integers $x$ and $y$ minimizing $| t - x \cdot y |$ with $1 \leq x < N$ and $1 \leq y < M$ ? Background: A clock signal is divided by two hardware prescalers (with a limited ...
0
votes
1answer
21 views

Symbol or notation for quotient operator

I'm trying to describe an algorithm in pseudocode where I've used the integer division operator. In VB.NET, the language I'm using, the operator used is "\", but I don't know if this is unambiguous to ...
0
votes
2answers
17 views

Minimize error function with integer constraints

Much time has passed since I studied any form of math so I wanted to take this cheap shot of asking someone else to think for me. I need to write some software that, for any given real number ...
0
votes
1answer
44 views

primal and dual lp optimal?

I have a simple assignment problem. I have four tasks that can be assigned to two persons. It is possible that not every task is assigned to a person due to capacity limitations. Each task requires: ...
0
votes
0answers
25 views

Why is integer programming in fixed dimension easier than in general?

When the dimension is an a priori fixed constant, then integer programming feasibility (the existence of an integer point in a polyhedron) can be decided in polynomial time. If the dimension is not ...
0
votes
2answers
25 views

how to impose binarity constraint in a vector

This is part of a homework problem. In an optimization problem, I need to have a K dimensional vector S, such that each entry of the vector is either 0 or 1, and $l_1$ norm of S is <= K. I can't ...
1
vote
1answer
27 views

Given the sum of a geometric progression and the number of terms, can we recover the progression?

Consider a set of numbers which are in geometric progression: $n, nd, nd^2, \ldots ,nd^{M-1}$ Their sum is $S=\frac{n(d^M-1)}{d-1}$. Now if we know the values of $S$ and $M$, can we find values of ...
0
votes
0answers
36 views

Calculate $\lceil \frac{n}{log_2k} \rceil; n \geqslant 1, k \geqslant 2$ with only integer functions

How to calculate following expression with only integer fuctions? $$\lceil \frac{n}{log_2k} \rceil; n \geqslant 1, k \geqslant 2$$ I mean with using of only integer division, integer log with base ...
1
vote
0answers
35 views

Help solving this linear (?) programming problem with odd integer constraints.

I would like some help writing the following linear (integer? quadratic?) programming problem in matrix form including the application of the constraints. I am drawing a dashed line around the ...
1
vote
0answers
30 views

How to minimise an objective function which is not a direct function of the decision variable?

I have a problem with partitioning a water network by closing some pipes. I use some graph theory techniques to find some candidate pipes to close; but to select which pipes among them to close (my ...
0
votes
0answers
38 views

Optimization - Integer programming Problem

The city of Shamut has called for bids for construction of its new town hall. The call for bids lists five parts of the total job: F - Foundation S - Structure P - Plumbing and heating E - ...
1
vote
0answers
21 views

Highest (lowest) index of positive time-indexed variable

I have a simple problem involving a variable $x_{it}$ representing the amount of a resource allotted to a task $i$ in time $t$. The quantity of the (renewable) resource is constrained at a value $R$ ...
1
vote
0answers
48 views

Is 0-1 integer programming always NP-hard?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ ...
1
vote
0answers
50 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book ...
0
votes
0answers
44 views

Find all $a_i$ such that $(x_{a_1} - x_{a_2} + x_{a_3}) +\ldots + x_{a_{3k}}$ min

Given $n$ numbers $x_1, x_2, \ldots,x_n \in \mathbb{Z}$ and an integer $k \le\frac n 3$. Find $a_i$ $(i = \overline{1,2,3,\dots,3k}),\ 0 < a_i < a_{i+1} \le n$ such that: $$M = (x_{a_1} - ...
2
votes
1answer
63 views

Non 0-1 integer programming

Many interesting combinatorial problems - graph coloring, maximal matching, set cover, and knapsack among others - can be reformulated as integer linear programs. One thing that all of these ...
0
votes
1answer
46 views

How to enforce a constraint that a decision variable can only take 1 of $k$ integer values?

How would you enforce the constraint that $x$, a decision variable, can only take values -3, 7, or 19? I think I probably need to introduce a binary variable here but not sure where to start. Thanks. ...
0
votes
1answer
39 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
28 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
27 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
27 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
0answers
11 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
14 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
87 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
24 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
132 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
64 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
17 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
39 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
23 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
23 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
218 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
42 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
59 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
1answer
48 views

Why do Integer Relation Algorithms (e.g. PSLQ) not solve the knapsack 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
54 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
143 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
79 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
35 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
328 views

Shortest path problem dual formulation

For the shortest path problem, I know that the IP formulation is this: And now I am given that the corresponding dual problem is this: I tried to derive the dual formulation myself, the way I ...
0
votes
1answer
97 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
122 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
78 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
37 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
67 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: ...