1
vote
1answer
24 views

Number of Integer solutions for this optimization problem

What is the number of integer solutions to the problem $$\sum_{i=1}^{i=k}x_i = n$$ subject to $\forall_i\ \ x_i \ge 0 $ note This should hold for both cases $k < n$ and $k \ge n$
1
vote
0answers
63 views

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
4answers
279 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
24 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$ ...
0
votes
0answers
21 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 ...
2
votes
1answer
70 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
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
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
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
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.
3
votes
3answers
93 views

How do one solve a nonlinear combinatoric problem?

I am an undergraduate CS student and I am struggling with a problem. $Qx = b$ where $Q$ is a constant $m \times n$ matrix (with $m>n$), $x$ is a $n \times 1$ vector and $b$ is a $m\times 1$ ...
3
votes
2answers
189 views

How many solutions are there to $abc+def=ghi$, where $a,b,\ldots, h,i$ are distinct non-zero digits?

I saw this problem posted by Google. Those posting in the comments found solutions using computer programming. I would like to know if there is an easier solution than trying every single combination. ...
1
vote
1answer
64 views

$ A = x + y + z$, number of solutions in $Z$ if $x, y, z$ are bounded in intervals

For the equation $x + y = A$, it's easy, when you notice that when iterating over all possible $x$, the number of solutions for $y$ is $0$ at the beginning, then increases by $1$, then stays constant, ...
7
votes
2answers
274 views

Mean and Median in a Classic River Crossing Problem

Consider the following classic problem: Four people on the west side of a river wish to use their single boat to get to the east side of a river. Each boat ride can hold at most two people, and the ...
0
votes
1answer
102 views

How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?

Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such ...
2
votes
0answers
118 views

An optimization problem involving Latin Squares

Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write ...
1
vote
2answers
188 views

Looking for a closed form to determine whether a symbol is part of the ith combination nCr

Hi I'm new to this, feel free to correct or edit anything if I haven't done something properly. This is a programming problem I'm having and finding a closed form instead of looping would help a lot. ...
1
vote
1answer
191 views

Combinatorial Optimization Problem (can I/how do I solve this with integer programming?)

Inputs: 1) A set of M x N matrices, {A,B,C...N} containing only integers. 2) A single 1 x N matrix of floats, W (weights). I need to pull one row from each input matrix and sum values for each ...