Questions tagged [optimization]

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

3
votes
0answers
22 views

Non-linear optimization of a family of functions

I'd like some advice about the following problem (resolution methods, problem category, etc.). The context is about the coregistration of several images all-in-once ($n$ images, $f_{i,j}$ the ...
0
votes
0answers
8 views

Obtaining the dual variables of an optimisation problem with second order cone constraints solved using Gurobi

I'm solving an optimisation problem with linear and second order cone constraints, in other words the problem is convex and should have dual variables. I'm using Julia with JuMP to formulate the ...
0
votes
1answer
37 views

What are the benefits of languages that are not Turing complete?

Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization? ...
0
votes
0answers
43 views

Is Travelling salesman problem with dikstra's algorithm the optimal solution?

I've tried solving the travelling salesman problem using dynamic programming and Dijkstra's algorithm to find the optimal solution in Dijkstra's algorithm is always correct(in the test data i used). ...
1
vote
0answers
14 views

Can graph execution be better optimized than imperative programs?

I've been reading about Google's TensorFlow, and the way it represents calculations with graphs that are then executed by an engine. While the concept is interesting, I would like to understand why ...
0
votes
1answer
25 views

Algorithm for selecting a sample that's as spread out as possible?

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as ...
0
votes
0answers
14 views

Is there an algorithm that provides the highest possible “sum of satisfaction” for a priority based distribution problem?

Let's say we have n (e.g. 6) children and a box of candy. The box has k (e.g. 8) different flavours, and m (e.g. 4) piece of candy in each flavour. This question is specifically about the cases where ...
0
votes
0answers
9 views

Is it possible to compute a whole convolution layer at once?

I have an input of 32×32×3 and I want to feed it to a convolution layer that output 32×32×16 feature maps. I know that I can compute a single feature map as matrix multiplication. But my question is, ...
1
vote
0answers
23 views

Find the m-th largest separation

The m-th largest number in a list of n numbers can be found in $O(m \log n)$ using a max-heap. This avoids sorting. Suppose I'm interested not in the actual numbers, but separation between adjacent ...
1
vote
0answers
19 views

Is there an algorithm to partition a set of points into two disjoint polytopes far away from the origin?

Suppose I have a finite point set $P = \{p_1,\ldots, p_K\} \subset \mathbb R^D$ and all $p_i \ne 0$. What I would like to do is partition $P$ into two disjoint pieces $A \cup B$ so the convex hulls $\...
1
vote
0answers
21 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
2
votes
1answer
37 views

Why is the usual simulated annealing algorithm using a Boltzmann probability?

I've coded a personal version for the simulated annealing problem, and I was wondering why, (other than by analogy to the physics), the probability is $$ p = e^{-\dfrac{\Delta \text{length}}{T}}$$ (...
1
vote
1answer
89 views

combinatoric grouping optimization problem based on time interval overlap, weight constraint, and distance minimization

Let each element be an individual. Consider that an individual is defined such that each individual has a time range, weight, and location. The goal is to group together individuals whose time ranges ...
1
vote
0answers
8 views

How to improve convergence to an equilibrium value, & damp oscillation?

I am developing a program which seeks strategies for the players A, B in any of a family of simple 2-player gambling-games. The program iterates, using a genetic algorithm to determine, from the ...
1
vote
3answers
51 views

How to solve the optimization of bin packing using the decision version

Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins. ...
0
votes
0answers
34 views

What kind of standard deviation must be used in optimization algorithms?

I would like to ask about the standard deviation of objective function value. There are two types of standard deviations: Population standard deviation Sample standard deviation In metaheuristic ...
2
votes
0answers
17 views

How to solve cubing, batching, and routing problem together?

I am working on an order picking project, which requires to cube the items into several totes in a trolley, then batching the totes, followed by parallel aisle picking/routing. The input data has ...
2
votes
2answers
45 views

Maximize number of museums visited in a day

Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day. Suppose that no time is needed in ...
2
votes
0answers
24 views

Linear order minimizing weighted distance from special element

Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)...
0
votes
0answers
13 views

How to model a path in optimization problem? [closed]

I have a question about modeling an optimization problem. I want to model all links in a path between two nodes in a network or graph. Most of the papers are based on modeling only one link between ...
1
vote
0answers
65 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
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=...
2
votes
0answers
52 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
106 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
14 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
82 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 $...
0
votes
1answer
220 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
31 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
39 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
34 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
60 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
35 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
61 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
44 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
40 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
28 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
34 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
158 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
18 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
49 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
91 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
67 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
364 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
37 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
22 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
13 views

The balanced $k-$ partitioning problem : how to design testbeds to compare different metaheuristics methods

I implemented different search metaheuristics methods (local search, Tabu search, and simulated annealing) on the problem of partitioning a non-oriented weighted graph' vertices into k parts of nearly ...
0
votes
0answers
53 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
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 ...
0
votes
0answers
52 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 ...