Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
0answers
46 views
+50

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
2
votes
1answer
281 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
0
votes
1answer
46 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
59 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
35 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
20 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
1answer
225 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
2
votes
3answers
223 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; ...
1
vote
2answers
265 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
23 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 ...
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
votes
1answer
140 views

Finding sum of all integral parts

Given two numbers $M$ and $N$, Let $q_i$ be the integer part of $\frac{iN}{M}$. What is $$ \sum_{i=0}^{M-1} q_i? $$ The Sum is obviously can be calculated in $O(M)$. Can this be done in less time, ...
0
votes
0answers
18 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
15 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$? ...
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
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 ...
1
vote
0answers
37 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 ...
0
votes
1answer
45 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 $$ $$ ...
1
vote
2answers
446 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
3
votes
1answer
37 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
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 ...
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
0answers
42 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
1answer
139 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
2answers
76 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 ...
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 ...
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 ...
1
vote
1answer
427 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
42 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
54 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
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 ...
1
vote
0answers
55 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 ...
3
votes
1answer
219 views

Determining Weights of Columns For A Prioritization Matrix

I'm trying to calculate the weight of various tasks. I have tasks that are daily, weekly, monthly, yearly. As a task gets closer to due date, I'd like it to be more important. For example, a weekly ...
1
vote
0answers
43 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
51 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
63 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
61 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
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
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} - ...
0
votes
1answer
75 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. ...
7
votes
5answers
3k views

Good software for linear/integer programming

I never did any linear/integer programming so I am wondering the following two things What are some efficient free linear programming solvers? What are some efficient commercial linear programming ...