Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
0answers
41 views

Prove this statement about inequalities

Can someone help to prove this. For $n$ and $\{a_{11},\dots,a_{nn}\}$, if we know that $a_{ij}$ is either $0$ or $1$ or $-1$, and further assume that the following inequality system on $\{b_n|b_n\in ...
1
vote
0answers
57 views

Minimising waste in a cutting problem.

I have three possible board sizes: $8$, $10$ and $12$ feet long. I want to make some number of cuts to these, say, $3, 2,1,1,1,6,5,3,4,2,1$ feet cuts and I want to minimize waste. I've done a quick ...
1
vote
0answers
43 views

Program for Handling Huge Primes

I am trying to run a program with really large primes (around the $10^{20}$th prime), but Mathematica seems to only be able to handle around the first $10^{12}$ primes. Is there any software that can ...
2
votes
1answer
36 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
65 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 ...
2
votes
0answers
40 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
154 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
54 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
86 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
35 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
33 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
46 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
40 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
115 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
83 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 ...
1
vote
0answers
30 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
109 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
91 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 ...
2
votes
1answer
76 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
114 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
57 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
35 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
91 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
38 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
16 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
20 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
95 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 ...
1
vote
0answers
303 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
28 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
49 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
54 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
36 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
253 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
1answer
131 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
127 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
61 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
375 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 double checked it. $(m_x,m_y)$ are coordinates of a point , $(p_x,p_y),(k_x,k_y)$ are coordinates of a ...
2
votes
2answers
151 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
153 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
296 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
138 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
39 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
185 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
204 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
213 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
617 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
113 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 ...