Questions on optimization constrained to integer variables.
0
votes
1answer
36 views
Shortest path problem: dual formulation and proof of total unimodularity
The IP formulation of the shortest path problem looks as follows:
\begin{align*}
\min & \sum_{u,v \in A} c_{uv} x_{uv}\\
\text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
30 views
Almost linear programming problem
I have a problem that is almost the typical in linear programming, but not quite. All variables take real non-negative values. Certain simple linear inequalities and equalities should hold. But what ...
0
votes
1answer
49 views
Minimize the following function with integer values with the given constraint. [closed]
$$f(b_1,b_2,\ldots,b_m)=(b_1)^2+(b_2)^2+\cdots+(b_m)^2$$
such that
$$
b_1+b_2+\cdots+b_m=l$$
m is fixed and
all values are positive integers including zero. We want to minimize this function with ...
0
votes
1answer
19 views
Disjunction of conjunction in linear programming
I'm trying to get my model working with less variable/constraints possible. I want the binary variable $R$ to store the result of this Boolean expression:
R = (a1 and b1) or (a2 and b2) or (a3 and ...
2
votes
3answers
221 views
Combinatorial optimization - Bijections between duplicated numbers
English is not my native language: sorry for my mistakes. Thank you in advance for your answers.
Two Bijections and an Array...
Here is a 2D array (in this particular example: rows: 1 to 4; ...
0
votes
0answers
20 views
Finding integer vectors in the column space of a matrix
Consider a given set $S \subset Z$. $S$ is a finite set. Matrix $A \in S^{N \times M}$ is also given.
Does there exist an algorithm to find all the vectors belonging to the space Col$(A)\cap S^N$
...
6
votes
1answer
33 views
Integer programming feasibility is NP-what
What is the complexity class of the general problem of integer programming feasibility?
The sources I've looked at are, in my opinion, very confusing. Some say NP-hard, some say NP-complete. Some ...
1
vote
2answers
260 views
Optimization problem: Maximize the sum of minimum.
Given positive integers $L$ and a set of non-negative integers $N$.
Find maximum of:
$$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$
with $c \in \{1, 2,\dots ...
0
votes
0answers
17 views
Name search for special Linear Mixed Integer Programm
I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
...
0
votes
0answers
12 views
Good MIP formulation of a timetabling problem
I am trying to formulate a university timetabling problem as a mixed-integer program. The choice variables are binary variables of the form $x(c,s,r)$ which is $1$ if a class of course $c$ is held in ...
0
votes
0answers
31 views
Finding the largest $3^k$ number less than the natural number
Given the natural number $N$ in binary representation (computer memory). How to obtain the representation of the $N\rightarrow\sum^{M}_{k=0}(a_k\cdot(3^k+1))$ form or, at least, how to find the $M$?
...
0
votes
0answers
2 views
Multiplying separately the different units,(other multiplication methods)
Is there any technique that performs multiplications taking into account the units separately?
For example when you have to multiply 15*13 how can you process the tens separately?
In general are there ...
3
votes
1answer
36 views
XORing consecutive integers has an interesting property. Does anyone know why?
I hesitated to post on StackOverflow but I think the problem has little to do with programming and more to do with mathematics. So, here it is:
I wanted to compute the function $ f(n) = 0 \oplus 1 ...
0
votes
1answer
43 views
Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?
Consider the assignment problem:
$$ Z = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik} $$
s.t.
$$ \sum_i x_{ij} = 1 \quad\forall j $$
$$ a \leq \sum_j x_{ij} \leq b \quad\forall i $$
$$ ...
0
votes
0answers
31 views
Mixed Interprogramm remodeling
for example i have the following problem
min z
5 x_1a + 6 x_1b - 3 x_2a + 0 x_2b <= z
-3 x_1a + 0 x_1b - 1 x_2a + 2 x_2b <= z
x_1a + x_1b = 1 (Constraint say of this group only one variable ...
1
vote
0answers
36 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
41 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
39 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
27 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
47 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
29 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
40 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
27 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
52 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
27 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
34 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
37 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
53 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
40 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
49 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
22 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
62 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
60 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
47 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
67 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
74 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
46 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
30 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
42 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
89 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
157 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
80 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
21 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
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
29 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. ...
