Questions tagged [mathematical-programming]
Using a computer to implement mathematics. For questions about (mathematical) optimization, (also) use the optimization tag.
0
votes
1answer
17 views
How many combinations will be generated if below conditions are put?
I need a generalized formula for a set having size(s) having below restrictions,
for ex. X = 2,7,11,17,26
I want only the first combination 2+7 & ignore all of the combinations that start from 2+...
0
votes
0answers
19 views
counting the integer solutions to 1000a + 100b + 10c + d where 0 < x,y < 20 [on hold]
I am trying to figure out the integer solutions to 1000a + 100b + 10c + d where 0 < x,y < 20. I can print out the solutions by replacing n = n + 1 with 'print(a,b,c,d)' and removing the 'print(n)...
-1
votes
1answer
73 views
Can we find every 216 digit number combination? [closed]
This question popped to my head when I watched Pi where the mathematican told the Jews "Didnt you calculate every 216 digit number allready?"
So I want to find every possible 216 digit number ...
0
votes
0answers
9 views
How to calculate constraint check in BT of 4-Queens problem?
I have seen number of constraint check in paper of CSPs.
The constraint checking is counted as followed: when a value of a variable x is checked against a value of variable y, this is counted as ...
2
votes
1answer
28 views
Linear programming IFF with equality constrain
Is it possible to write the following logical constrain in linear programming?
Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is
$y=...
0
votes
1answer
30 views
How to model equality in Integer Linear Programming
How to implement v=(a==b) using Linear Programming?
$$
v=
\begin{cases}
True, a=b\\
False, a≠b\\
\end{cases}
$$
Until now I tried the big M-Method.
To show a≤b:
$$a-b+Mv≤M$$
$$-a+b-Mv≤-1$$
To show ...
2
votes
0answers
39 views
Maximizing the product of a set of dot products
So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following:
$\prod_{x \in X} b \cdot x$
where the components of $b$ sum to $1$
If it matters the components of ...
2
votes
2answers
974 views
How does a computer interpret real numbers?
I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers.
But I want to know how does ...
3
votes
1answer
91 views
Can this equation be solved in polynomial time?
I came across a more general form of this question.
Can we find the value of variables in polynomial time ?
Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...
6
votes
2answers
148 views
Can this system of polynomial equations be solved in polynomial time?
I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
2
votes
1answer
24 views
Interpolate on a cylic x axes
Let's assume you are in 2D space and you have a set of fix points FIX_POINTS = [(x1, y1), (x2, y2)]. I want to interpolate the y ...
1
vote
0answers
21 views
How can I code an algorithm (concerning networks) [closed]
my question is basic but I want to know how to code algorithms containing maths like this https://web.stanford.edu/~skatti/pubs/sigcomm15-spotfi.pdf , TY for your help !
0
votes
0answers
23 views
Optimize an underdetermined system with quartic constraints
I encountered an optimization problem which does not belong to any well-known category of optimization.
The system has $M$ (typically $M=120$) real variables and $N$ (typically $N=100$) constraints (...
1
vote
0answers
51 views
Sum of long geometric progression [closed]
Finding sum of a geometric progression is simple when we just need to report the sum,
but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me.
I have a ...
0
votes
0answers
32 views
How to generate evenly distributed random numbers from the tics of a Geiger Counter?
How can I generate random numbers from the tics of a Geiger Counter?
Say I have a file with the timestamps for every event.
0
325
456
920
....
The time spans ...
1
vote
0answers
31 views
How much of the x86 instruction set does blender use? [closed]
I'm trying to better understand benchmarks that are commonly used for computer hardware. I've been unable to find an answer to this question. Extra credit if you can provide a breakdown in ...
0
votes
0answers
25 views
Algorithm for placing objects inside a square from outside to inside
I have a map that is 300x300 units. I have to place squares of 20x20 units inside that map from outside to inside. There are 3 different types of square, the space available inside the map needs to be ...
0
votes
1answer
49 views
Counting the number of multiples of number A that perfectly divides the number B
What is the best way of counting the number of multiples of number A that perfectly divides the number B.
This is the sub problem for one of the questions I am solving on codechef.
This is the best I ...
2
votes
1answer
79 views
Mathematically calculating time complexity
This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject.
Also I ...
4
votes
0answers
100 views
Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$
We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$.
The obvious naive way ...
0
votes
1answer
57 views
0
votes
0answers
65 views
What is the time complexity of MATLAB's ode solvers?
Say I have a system that is $n$ differential equations that are all coupled together, over a time interval $[a,b]$ with timestep $t$. Is there a straightforward time complexity for MATLAB's built in ...
2
votes
1answer
42 views
Implementing Gauss–Legendre algorithm using arbitrary-length rationals
I am trying to re-implement SuperPI myself in Rust, but the results I get are not very accurate. SuperPI computes pi using the Gauss-Legendre algorithm.
The Gauss–Legendre algorithm is quite simple, ...
1
vote
1answer
23 views
What is the equation for a spiral path in 3D? [closed]
I am developing games in Unity 3D. Currently, I am trying to place 3D objects in 3D space in a spiral pattern that looks like one of 2 the strands in a pair of the DNA (helix) spiral pattern.
Would ...
0
votes
0answers
26 views
Classify manifolds with neural networks
Can a neural network be used to find the genus of a 2-manifold given for instance as a CW complex?
1
vote
1answer
50 views
Balance groups based on average, element constraints and size
It's a complex situation, where I want to balance groups of numbers based on the average of these numbers, while keeping the group size unchanged and not breaking elements constraints.
Let me explain ...
2
votes
2answers
173 views
Implications of Integral linear program
Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$
Let $(P^*)$ be ...
1
vote
1answer
290 views
Efficient streaming sort
Consider following task: we have an input of N+1 lines, where first line contains N - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id &...
2
votes
1answer
53 views
Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$
Given array $A$ of size $n$, we want to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I ...
1
vote
1answer
17 views
PCA with Bishop's book
I am reading PCA in Bishop's Pattern Recognition and Machine Learning pg. 562, here in Lagrange multiplier but I don't get it in the highlighted: I wonder is it $u_1$ or $u^T_1$?
Your help is ...
0
votes
1answer
60 views
Compute e^x given starting approximation
I have been looking for an algorithm to calculate $e^x$ to arbitrary precision (millions of digits). The best way I know is to use Taylor polynomials. However, the Taylor polynomial algorithm seems ...
1
vote
1answer
22 views
Sum of distances between points on one-dimensional axis
We have given integer array of $n$ points, let it be $A$, showing where it is on the x-axis. For this problem we are working only with the x-axis and the y-axis is not important at all. Now for given ...
3
votes
3answers
164 views
Is it possible to make a language that can build upon itself perfectly?
First of all, note that I'll have to explain my thoughts in a layman's terms.
There are so many high-level programming languages out there that compete with each other. This means we have to build ...
0
votes
2answers
702 views
Is global non-convex optimization NP-complete?
Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision ...
1
vote
1answer
37 views
How do you implement a language with greater capabilities using subordinate languages?
I've heard that C++ and Python where implemented using C. How can someone make an object oriented language out of something that doesn't support objects?
I've read in the book "Math You Can`t Use - ...
1
vote
1answer
133 views
Algorithm for weighted elliptic curve fit
Background:
I was trying to detect a face solely on the bases of features and the confidence of the features found.
I am using a method to identify the features along with the response (confidence). ...
0
votes
1answer
138 views
Is there a poly-time algorithm for expanding out polynomials
so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of
$$
z = (x+y)(x-y) \implies x^2+xy-xy+y^2
$$
...
1
vote
1answer
84 views
Is it possible to evaluate $n!$ in $O(1)$?
I'm working on a formula that'll evaluate the partial sum of the harmonic series from $t_1$ to $t_n$. The problem is that I'm almost certain the final formula will include factorials. But if the ...
1
vote
2answers
173 views
Algorithm for packing various shapes inside of a rectangle
Say I am given a rectangle of width $W$ and length $L$. I now have to fit as many regular shapes of area $A$ into this rectangle as possible. For example, if the shape is a circle, I need to fit as ...
4
votes
2answers
249 views
Is the $x$ in $\frac{\mathrm{d}}{\mathrm{d}x}$ a symbol in the sense of Harper's PFPL?
The role of $x$ in $\frac{\mathrm{d}}{\mathrm{d}x} y$ not only confuses my calculus students, it has also puzzled some well known mathematicians. Questions one might ask are:
Does the $x$ in the ...
0
votes
0answers
51 views
Math behind path tracing
I seem to remember seeing somewhere (many years ago) a writeup of the math behind calculating the outline of Metafont glyphs. The basic idea is you have a "pen" that is a circle or oval, that you ...
1
vote
1answer
104 views
What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number?
I'm talking about functions such as Python's math.frexp() :
math.frexp(x)
Return the mantissa and exponent of x as the pair (m, e). m is a float
and e is an integer such that x == m * 2**e ...
0
votes
0answers
355 views
Derivatives involved in Bilinear interpolation
If we choose a unit square in which the four points where the function $f$ is known are as shown in the diagram the interpolation formula for $f$ is:
\begin{equation}
\begin{split}
f(x+u, y+v)\approx (...
1
vote
1answer
56 views
Algorithm which finds the maxmal solution that satisfies the following constraints
I have $a_1, a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ and an upper bound $U$ and $n$ linear equations of the form:
$k_1 * a_1 + b_1 = x$
$k_2 * a_2 + b_2 = x$
$\dots$
$k_n * a_n + b_n = x$
...
1
vote
0answers
49 views
How to model the constraint of a circle placement problem mathematically?
I have a circle with radius $R$ and $N$ points on a 2D plane with known locations $(x_i,y_i), i=1,2,..N$. I want to place the circle such that it maximizes the number of covered points.
Let $d_i=(x_i-...
0
votes
1answer
59 views
How can I calculate the new quotient if I came to know divisor is increased by one?
If I have two number consider a and b and let their division quotient is c.
I know the value of c but I don't know either value of divided(a) or divisor(b). If I came to know the value of divisor is ...
2
votes
1answer
134 views
How to find the most unique vectors in a set?
A question bridging math and computer science, I have on the order of 10000 vectors each of a equal but high dimension, say 6 or 7 dimensions. I want to find a given number of 'unique' vectors in the ...
2
votes
0answers
120 views
Can cognitive architectures (CLARION, SOAR, ACT-R) be used for creative mathematical reasoning?
Can cognitive architectures (CLARION, SOAR, ACT-R, others) be used for creative mathematical reasoning? As far as I understand, then it is the best to encode formal mathematical knowledge in the ...
1
vote
0answers
62 views
Column Generation - Worst dual bound when adding various columns per iteration
I'm implementing a Column Generation algorithm. The pricing problem, in general, find more than one column with negative reduced costs(the master is a min problem). If i add only the most negative ...
4
votes
1answer
414 views
How did the Logic Theorist proved the Pons Asinorum
I was reading about the Logic Theorist solving many of Whitehead and Russell's Principia's theorems. I cannot however find any technical explanation on how the program proved those theorems and ...
