The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [optimization]

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

1,227 questions
Filter by
Sorted by
Tagged with
118 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-...
48 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 ...
54 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 ...
15 views

Confused between different Structure from Motion pipelines

What is the difference between Global SfM, Incremental SfM, Sequential SfM, Progressive SfM and VSLAM (Visual Simultaneous Localization and Mapping). Is sequential SfM the same as VSLAM ? I have tried ...
48 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 ...
132 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 ...
143 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 ...
100 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 ...
373 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 ...
57 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{...
175 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, ...
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 ...
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, ...
37 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 ...
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) ...
115 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 ...
28 views

Greedy Approach without constraint and a feasibility function

We know that the Greedy Approach in general, picks an element from a set of candidate elements that satisfies a predefined criteria (selection function) and is added to the solution if it satisfies ...
28 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 ...
27 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 (...
39 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 ...
138 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 ...
35 views

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

I have this problem A ﬁrm 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 ...
80 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 ...
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)...
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 ...
59 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 ...
48 views

Evolutionary optimisation algorithm and graph based search

Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms. Both of these methods entail doing a search on a graph of candidate solutions. Do all other evolutionary ...
76 views

Finding Conflict algorithm doubt

Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time. I have to find an event that conflict with maximum number of other events. Conflicts means interval ...
70 views

Solving the Size-Constrained Weighted Set Cover Problem

I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the ...
122 views

Run-time of Hungarian algorithm - matrix formulation

There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a ...
94 views

Closest Value instead of Max Value in Knapsack problem

I have a problem like the knapsack problem, except instead of finding the max value, I'm trying to find the closest value to a given value. Anyone know where to start, have a name for this problem, ...
129 views

Optimal partitioning of n-tuples

Motivation Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
18 views

Bounds on “well dispersed” sparse matrices

Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is ...
77 views

Finding optimal multiplication order and optimal binary tree

I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree. Consider the following ...
42 views

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached. I thought to run an SCC algorithm to find binding ...
85 views

Maximum flow with constraints

In a flow network, suppose we add constraints of the following type: The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$. Is maximum-flow with such constraints still ...
15 views

Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, ...
58 views

Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa. But which type of repetition is preferable for minimum amount of computational effort and ...
21 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
25 views

what can cause the best-bound to get tighter in the first MIP node?

I'm using gurobi MIP optimization engine for solving a mixed integer linear minimization problem. I see that the engine didn't start the branch and bound stage ...
24 views

Kiln optimization problem

Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings: 102 of A 364 of B 70 of C I can put 50 molds in the kiln at a time. I can have 75 molds made in ...
9 views

Clarification on descending direction in optimization of function

Could someone clarify for me why given $f:\mathbb{R}^n \rightarrow\mathbb{R}$ to optimize an iterative function according to : $p^k=-M\nabla f(x^k)$ for $p^k$ to be descending direction the matrix M ...
7 views

What analysis / algorithm helps stabilizing the fit of correlated parameters (but not colinear)?

I have many curves that I want to fit using a convolution of some functions. These functions include Weibull distributions with 2 parameters lambda and ...
10 views

Most probable inputs assignment in Gaussian process

Given A Guassian process $w(\mu^*,\Sigma^*)$ $n$ observations of the output And $n$ potential inputs. But the assignment of the inputs to the observations is unknown. The goal is to find a inputs-...
14 views

Disk Scheduling for a Fragmented Hard-Drive

Recently In class I have been learning about simple disk scheduling algorithms such as FCFS, STTF, LOOK, LOOK-SCAN etc. From my understanding these algorithms schedule I/O requests depending on which ...
74 views

Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem: Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
29 views

University timetable optimisation - with a twist

I've made a website that helps students at my university optimise their student timetables. Currently, for subjects with not many classes - I can generate and optimise the timetables quite fast. ...
38 views

Optimizing library dimensions

Say I have a library that looks like that: ...
K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) ...