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
1
vote
0answers
70 views

Approporiate algorithm for a graph theory problem

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm. The problem is pretty ...
2
votes
1answer
40 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=...
2
votes
0answers
53 views

What algorithm should I use for the following problem?

Suppose we have 2 lists: List $G$: the goal, contains goal items each comes with a specific amount, $$G = \{i_1 \times Item_1, i_2 \times Item_2,\dots, i_n \times Item_n\}$$ List $I$: a list that ...
3
votes
4answers
149 views

How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{...
9
votes
6answers
3k views

Are there variations of the regular runtimes of the Big-O-Notation?

There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically ...
2
votes
0answers
15 views

IPM vs Projected Subgradient Descent

In my theoretical CS class, we learned about Interior Point Methods for convex optimization, but it seems that projected subgradient descent works equally well for constrained optimization. What are ...
1
vote
0answers
95 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

A paper was published recently in Science where the authors minimized the following function: $$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$ where $s_i$ ...
2
votes
3answers
431 views

Can this “double pop” Heapsort variation speed up sorting on average?

For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-...
0
votes
0answers
33 views

Minimization with asymptotic assumption

Given the function $g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with} \left\{\begin{matrix} a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\ b\leq a! \\ c\leq (n-a)! \\ \end{matrix}\right. \Big\}...
2
votes
0answers
48 views

Algorithm to optimize redistribution of balls amongst urns [closed]

Here is the question: Say we have k urns with 1 ball in each urn. At each iteration of the game, I pick one urn and redistribute its contents amongst other urns and each urn can receive at most one ...
2
votes
0answers
168 views

Optimizing AVL Tree operations for sequential data

I'm working on an implementation of a data structure that needs a tree-like data structure for accelerating look-ups. The interesting part about this data structure is that the only operations on the ...
3
votes
2answers
77 views

League and Divisions problem (np-hard)

There is a League. And there are Divisions, that are the disjoint subsets of this League. There are n teams (unique locations are given, let's assume it's x and y for simplicity reasons). Every team ...
0
votes
1answer
63 views

Loop Invariant Code Motion - am I missing something?

I've been implementing LICM for a project, and came upon a strange observation. Let's say we have a loop int i = 10; while (i > 0) { a = 2; i--; } ...
1
vote
1answer
383 views

Dynamic programming - maximize sum of functions subject to constraints

Let $\{f_i\}_{i=1}^{k}:[0,k]\to\mathbb{Z}$. The problem: Maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le k$ I think we suppose to come up with a ...
0
votes
1answer
213 views

MILP problem NP-hard proof [closed]

Since a MILP problem is not necessarily NP hard. How could I demonstrate that a MILP problem is actually NP hard? There exists some smart and easy method to do that? Many thanks!
0
votes
1answer
63 views

How do you compute the Pareto Front of a set?

I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst ...
1
vote
0answers
50 views

Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?

A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply ...
4
votes
1answer
43 views

Why does it take so long to prove optimality when warm-starting from optimal solution

So I'm solving bigger instances of some binary-linear-program using cplex. The formulations of the problem I am using is integer friendly, meaning nearly all of my instances can be solved at the root ...
1
vote
0answers
172 views

Morphing Hypercubes, Token Sliding and Odd Permutations

A month ago, I asked the following question math.exchange (https://math.stackexchange.com/questions/3127874/morphing-hypercubes-and-odd-permutations), but for completeness, I will include the details ...
0
votes
0answers
22 views

Finding an optimal machine assigning

I have $m$ machines and $n$ jobs. Each machine has a load capacity. Each job can be only handled by either one or two machine, and each job takes some time to finish. After it finished, new jobs can ...
1
vote
0answers
60 views

Given a tree find path that maximizes the median of the costs of edges

We have given tree with $N$ nodes and $N-1$ edges, such that each edges is assigned positive weight. We need to find path of length between $L$ and $R$ inclusively, with maximum cost. Cost of a path ...
0
votes
1answer
141 views

Modified Knapsack Problem

I have a problem with the following optimisation problem: In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $ must be selected for each of these items. The greater $L_i$ is, ...
1
vote
2answers
72 views

Assigning books to boxes

I am trying to model the following problem correctly as a min-cut network flow problem. I have $n$ books and 2 boxes. I also have books that I know must go in one of the two boxes. In addition, each ...
4
votes
2answers
367 views

Linear Path Optimization with Two Dependent Variables

Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best. There are two runners on a line that goes from $x=0$ to $x=100$. The two runners ...
0
votes
1answer
46 views

Modelling of minimal NOR-circuit problem with CP

I'm currently working on a Constraint Programming problem which I find difficult to model. Here 's the definition of the problem : " Given a specification of a Boolean function f(x1, ..., xn) in the ...
0
votes
0answers
24 views

Finding “good” order of elements for the purpose of material minimization

I am working with metallic shapes which are curved and highly irregular. The initial order of them is random and by default they are merely sorted by size, which is simple. However the resulting order ...
0
votes
0answers
297 views

Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming

I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below: Regular chores with a start time and end time (a real-...
2
votes
0answers
65 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 ...
0
votes
0answers
57 views

A scheduling problem on an oriented graph with multiple constraints

The problem is the following : Data An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a ...
3
votes
1answer
63 views

shortest form $s$ to $t$ stopping at $u$

Suppose you want to go from vertex $s$ to vertex $t$ in an unweighted graph $(V, E)$, but you would like to stop by vextex $u$ if it is possible to do so without increasing the length of your path by ...
2
votes
1answer
192 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
6
votes
2answers
169 views

Which algorithm can I use to allocate human resources?

I have to manage shifts of a variable number of people inside several rooms for a week. Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same ...
2
votes
0answers
101 views

Join Order Optimization

Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player What is the optimal join order? Based on the schema on the following picture: I am suppoused (and that's what I tried) to use ...
2
votes
1answer
516 views

Finding the largest possible area covered by M rectangle under a given histogram

Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles ...
2
votes
1answer
125 views

Image registration using gradient descent

I have a target image $f(x,y)$ (where $x \in [0, 250]$ and $y \in [0,300]$), and a source image $g(x,y)$ I want to align $g$ to $f$ using the transformation : $$\Psi(x,y;t_x, t_y, \theta) = \begin{...
9
votes
2answers
220 views

Find an optimal ordering

I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated! Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example, ...
2
votes
2answers
35 views

What does Stroustrup mean by 7/8ths of MIPS being in the vector units?

In his article Software Development for Infrastructure Stroustrup states the following: Hardware improvements make the problems and costs resulting from isolating software from hardware far worse ...
0
votes
1answer
47 views

How to judge the searching precision of Particle Swarm Optimization?

As the title mentioned, how can I judge the searching precision of PSO? Is this depending on the velocity of the particles? I would like to give an example to clarify my question: For a 2-D searching, ...
1
vote
1answer
42 views

Turing Machine where branches are resolved via arbitrary operator

Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is ...
1
vote
1answer
19 views

Selection of dates respecting delay constraints

I encountered an issue at work that can be derived approximatively to this problem. Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) ...
2
votes
0answers
173 views

Sub-optimal and fast solutions to assignment problem

I am looking for a fast solution to the assignment problem for large cost matrices (5000x5000 or larger). The Hungarian algorithm is $O^3$, which is impractical for any moderately large problem. Are ...
1
vote
0answers
32 views

How to optimize the return given the stock price of all time?

There is a list of N stocks. In M days, the stock price is given. Assume that each stock has only 1 price per day. Assume that ...
0
votes
0answers
54 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 (...
2
votes
0answers
64 views

Using exponential penalty functions in constrained nonlinear optimization

Background: penalty functions Penalty functions convert a constrained optimization problem \begin{equation}\begin{split} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) \leq 0 ...
1
vote
0answers
191 views

Travelling Salesman problem using Guided Local Search

I am doing Week_4 of https://www.coursera.org/learn/discrete-optimization/ stuck in solving TSP. As there are a lot of methods to solve this problem, I am currently coding Guided Local Search as ...
1
vote
0answers
41 views

$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost

I have this problem A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
2
votes
2answers
184 views

Recursion to DP Solution

There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
1
vote
0answers
49 views

Finding the best state for chain graph with cycles

I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative)...
2
votes
1answer
41 views

List of algorithm problems in term of ideals

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
0
votes
0answers
70 views

Resource allocation / optimization

At work I stumbled across this problem of allocating resources: We are given a set of objects belonging to one of seven possible classes (multiple objects per class are allowed). We distinguish ...

1
4 5
6
7 8
28