Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

Filter by
Sorted by
Tagged with
3
votes
1answer
94 views

Globally-optimized nearest neighbors lookup

I have a set $\mathcal{A}$ of $\mathcal{m}$ vectors in $\mathbb{R}^a$. I also have a different set $\mathcal{B}$ of $\mathcal{n}$ vectors in $\mathbb{R}^a$. These two sets are disjoint: $\mathcal{A}\...
0
votes
1answer
124 views

how to express an intertemporal implication constraint in integer linear programming (ILP)?

I want to express the following locigal expression in an IP: $$x_{di} \wedge x_{d'j} \Rightarrow \sum_{\substack{d'' \in D\\ i < k <j}} x_{d''k} = \sum_{i<k<j} a_{k} \ \forall \ d, d' \in ...
0
votes
1answer
54 views

Minimum difference of sums

So hey, I've recently found this problem online and I tried hard to solve but couldn't found an efficient solution. The problem statement is: Given and two integers $n$ and $k$ and an array $A$ ...
1
vote
1answer
873 views

Dynamic Programming to Maximize Profit

I have this problem to resolve in dynamic programming: An ice cream shop owner has 4 stores. To meet the demand in the summer he purchased 7 refrigerators for the ice cream. Because the stores are ...
2
votes
1answer
31 views

number of subsegments that contain A[i] as the minimum

I've recently been thinking about this problem. Given an array $A$ containing $n$ integers and an index $i$, find the number of subgements of $A$ containing $A[i]$ as their minimum. To better ...
2
votes
2answers
619 views

Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?

Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions : ...
4
votes
1answer
382 views

Definition of $\alpha$-approximation

I know this question is trivial. But I am looking for a concise formal definition of $\alpha$-approximation. Is it correct to say that "An algorithm is an $\alpha$-approximation to problem $X$, if ...
1
vote
1answer
86 views

Optimal covering of 2D matrix elements given spatial constraints

I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction. I've ...
1
vote
1answer
224 views

What algorithm to use, least waste when sawing wood planks

Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 30cm 50cm and 20cm. Is there an algorithm for calculating the least waste? When using brute force it quickly ...
0
votes
1answer
84 views

Sorting the number sequence

I have $4$ variables $n_1, n_2, n_3, n_4 \in \mathbb N$ that sum to $N$. $4$ positive real constants $c_1 < c_2 < c_3 < c_4$. Given a particular tuple $(k_1,k_2,k_3,k_4)$, how do I find ...
0
votes
2answers
177 views

Maximizing product of list of integers whose sum equals n

Given a positive integer n, find the list of positive integers whose product is the largest among all the list whose sum is n. For example, if n is 4 the desired list is 2,2 because 2x2 = 4 is larger ...
0
votes
1answer
160 views

Ant colony optimization algorithm

if i have an equation like $$f_n = x + y + z + a + b$$ and each variable has a discrete answer like $a = 0, 1 , 3$ . $b = 2 ,4,5$ etc. i want to find the global optimum minimization point....
1
vote
1answer
79 views

Can all optimizations be expressed in source code?

If someone compiled a program with all optimization settings enabled, would it be possible to create source code that, if it was compiled with all optimizations disabled, produced an identical binary? ...
3
votes
2answers
327 views

Find non-overlapping subsets that maximize the sum of their values

Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of non-overlapping subsets that maximizes the total value. Has this ...
3
votes
1answer
117 views

Algorithm to mimimally pair up points in 3D space

Given a set of $n$ points $P$ and a set of $n$ points $Q$ in 3 dimensional space, what's the fastest algorithm to uniquely pair points in $P$ with points in $Q$ so that the sum of the square of the ...
3
votes
1answer
138 views

Number of Pairs in Array

so hey, I've been recently reading about the Two-Pointer algorithm that allows us to find pairs $(i,j)$ such that $a[i] + a[j] = x$ in $O(m+n)$ instead of the trivial $O(mn)$ time. I was wondering ...
1
vote
1answer
100 views

MAX-2-XOR-SAT: Why does the special case work?

I'm a new user so I cannot respond directly to this post here. I'm confused about the answers to the question, namely that MAX-2-XOR-SAT is in $P$ iff each clause is of the form $(x_i \oplus \neg ...
1
vote
1answer
100 views

Finding maximum rectangular frame in array of zeros and ones

I've recently come across a following problem. In a rectangular array of ones and zeros one has to find maximum non-degenerate rectangle whose sides are filled with ones. By "maximum" i mean any ...
3
votes
1answer
57 views

What graph problems are hard to solve even for a small number of verticies?

The only graph problem that I worked with is TSP. It is exponentially hard, but there are tons of heuristics which allows to find near to optimum solution. So I was wondering, is there any graph ...
0
votes
0answers
47 views

Handling eqaulity constraints in genetic algorithms

I am trying to solve an optimization problem with strength pareto algorithm (SPEA2). My decision variable have lower and upper bounds as well as an equality constraint (sum(dp) = 1). I am unable to ...
0
votes
1answer
169 views

Determine the optimal strategy and maximize the reward

Given an array of length n filled with objects which contain 2 ints (size and reward). Now ...
0
votes
1answer
93 views

Multi objective optimization using genetic algorithm

I have an objective function profit = income - expense . I want to solve it using genetic/evolutionary algorithm (strength pareto SPEA2). Since the algorithm is ...
1
vote
2answers
1k views

Devising algorithm for an A.I. to solve the Wumpus game

Background I am currently coding an AI in C++ to solve a game called Hunt the Wumpus. You can try the game out here. My implementation of the game is based on a Graph template which I use to model ...
0
votes
0answers
14 views

Scheduling problem with performance based selection

I would like to solve a scheduling problem where, I am able to maximize the number of consecutive shifts a employee may have, therefore minimizing the likelihood of them not showing up for a single, ...
6
votes
0answers
344 views

Trying to find a human-usable method to figure out optimal round 1 openings for this game

I'm trying to figure out optimal round 1 openings for this game: http://generals.io/. For the purposes of this question, I've simplified some of the rules and mechanics of the game, and I assume that ...
2
votes
1answer
111 views

Best combination of values pulled from a matrix

What is the fastest way to select $n$ values from an $n$ by $n$ matrix such that each value comes from a different row and column and the sum of those n values is minimized? For example, given the ...
1
vote
0answers
65 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-...
3
votes
1answer
46 views

Algorithmic complexity of a Maximum Capacity Representatives variant

I have been trying to find the algorithmic complexity of a problem that I have. I am almost sure it is either NP-hard or NP-complete but I cannot find any proof. Recently, I found that my problem can ...
3
votes
1answer
112 views

Algorithm for shortest continuous line to join N points

I have a set of points in a 2D plane. I'm searching for an algorithm that: Draws a continuous line passing through all the points starting from a random point. Optimizes for the minimum total line ...
2
votes
0answers
59 views

Adding linear constraint to continuos LP to improve performance

Consider a standard LP minimization problem of the form $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & A x = b\\ & x \geq 0\end{array}$$ Should I expect, on average,...
2
votes
0answers
53 views

maximally exclusive paths in a DAG

Suppose we have a DAG $G$ with one source node $s$, ie. it has a path to every node, and target node $t$ which every node has a path to it. For a pair of paths from $s$ to $t$ we can define a distance ...
1
vote
2answers
724 views

Quicksort dual pivot or single

I've seen to explanations for the quick sort algorithm. One in which a pivot is chosen, and put into place, before both sides of the pivot are recursively pivot-sorted. Another involved a more ...
5
votes
3answers
1k views

Why do we try to maximize Lagrangian in SVMs?

I was learning about support vector machines from MIT OpenCourseWare. I figured it out. I understand why we try to minimize $\frac{1}{2} w^2$. I just did not get why we try to maximize Lagrange ...
1
vote
1answer
230 views

Warm starting LP solver at non-basic feasible solution

I'm approaching some continuous optimization problems by considering discrete approximations of them at different resolutions. Those discrete approximations can be solved with linear programming ...
0
votes
0answers
63 views

Debugging the issues on Megiddo's algorithm

I have done code for the algorithm to obtain the Optimal Basis but as I calculate the optimal solution $Xb=B^{-1}b$, I only get the correct value for some of the variables. For some variables, $Xb_i$ ...
5
votes
0answers
133 views

Approximate Weighted Partial Max SAT

Given a Weighted Partial Max SAT problem (WPM-SAT) - are there generally used algorithms or techniques to generate 'approximate' solutions, which are not necessarily optimal, but found faster than ...
1
vote
1answer
117 views

Dynamic programming, coming up with an algorithm

I've been banging my head against the wall for the past two days and can't seem to come up with anything useful. The problem that needs to be solved is the following: I get an array of integers and I ...
1
vote
1answer
210 views

Maximize pairings subject to distance constraint

I have a list of people's locations on a world map and want to pair nearby people up such that the number of pairs is maximized. For example, subject to the constraint that paired people are within ...
4
votes
1answer
44 views

Given a Noisy Curve, Write a Function to Output Likely Slopes

I am training a Variational Autoencoder (type of convolutional neural network), and have been plotting cost over time. The result is a noisy curve, shown here: I would like to write a function that ...
1
vote
1answer
66 views

How to convert two conflicting objective functions into a single objective function

I have two objective functions say f1 where I have to minimize (X+Y) and another function f2 where I have to maximize (A-B). The two functions are conflicting. I need to convert them into a ...
6
votes
0answers
144 views

When does greediness guarantee optimality?

I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution. Here is a motivating example. Suppose you are trying ...
4
votes
2answers
562 views

Approximate subset sum with two-dimensional vectors

Consider the following optimization problem: Given $n\leq 10^3$ vectors $v_i\in\mathbb{R}^2$, all of which are small, i.e., $\|v_i\| \leq 1$, find a subset $S$ of them that minimizes $ \| w + \...
1
vote
1answer
337 views

Approximation of a gaussian function

I want to approximate a Gaussian function as shown below $$ e^{\frac{-\|x-c\|^2}{2\sigma^2}} \approx \sum_{i=1}^{N}\alpha(c,c_i)e^{\frac{-\|x-c_i\|^2}{2\sigma^2}} \forall x $$ Here c, $\sigma$ and $...
2
votes
1answer
47 views

Constrained optimization topics

Given functions $f, p, c$, a matrix $X$, and vectors $C,D,E$. I want to maximize the multivariable function $f(X)$, where $X$ is a $p \times q$ binary matrix ($X_{ij}$ is 0 or 1). So, $p\cdot q$ ...
0
votes
0answers
25 views

Arranging cubes in bins to minimize expected variation ratio

I am working on an optimization problem. Let's say we have a grid of bins where solid metal cubes could be placed. We have a number of colored metal cubes to be arranged in the bins. Each of these ...
0
votes
1answer
79 views

Find hamming codewords in r=2^k dimensions

There is the original problem, and an equivalent problem. The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, ...
1
vote
1answer
62 views

Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function

A boolean-valued function defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$...
1
vote
1answer
28 views

Smaller approximation ratio for larger input size?

Is it possible for an approximation algorithm (for minimization optimization problem) to obtain smaller approximation ratios for inputs of larger size? For example, is $1/n$- or $1/\log n$-APX ...
1
vote
2answers
1k views

Genetic algorithm does not always find the global optima and a higher mutation rate finds a better solution

I wanted to make a tool which minimizes the interference between antennas. Currently, the tool is very limited for prototyping reasons. It can only place an antenna every 1 meters. The available ...
-2
votes
2answers
953 views

Divide N sticks among M boys as evenly as possible

There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is ...