# Questions tagged [optimization]

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

1,266 questions
Filter by
Sorted by
Tagged with
45 views

### Polynomial time algorithm for a simple machine scheduling problem

Think about a setting where there are $n$ tasks and $m$ machines. We are interested in task-machine assignment. Let $p_i$ be a non-negative completion time of job $i$. Also, $x_i$ denotes the machine ...
108 views

### Maximize vertex cover weights with bounded edge weights in a connected subgraph

Similar questions were asked elsewhere, but no satisfying answers occurred yet. In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is ...
90 views

### Chromosome length in Genetic Algorithms

In order to find the appropriate length of chromosomes in GA programming, the author of this book states: Suppose six decimal places for the variables' values is desirable. It is clear that to ...
341 views

### Understanding the Polyhedral Model

I am wondering at a high level the mathematics of the Polyhedral Model. The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of ...
50 views

### Has the problem of finding the most profitable transactions given a set of discrete time series been well-studied?

Overview and Problem Description Suppose I have a set of N discrete time-series (represented as a map from time-interval-index to value/utility), and I would like to identify a sequence of actions in ...
26 views

### The optimal way to find leaves in a weighted full binary tree

Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b How do I find optimal paths to all leaves from the root. I don't ...
28 views

### How many optimal alignments can be there for a string of length m with a string of length n?

So I was practicing optimal alignment algorithm and I was stuck with this question of finding optimal alignment for a string of length m with a string length n ? Also is it possible to run it in theta(...
53 views

### Spanning tree with equally separated edge weights

I have a fully-connected graph $G=(V,E)$ with edge weights $w(v)\in\mathbb{R};v\in V$ and I need to find a spanning tree $T=(V_t\subseteq V,E_t\subseteq E)$ where the set of edge weights in the tree ...
62 views

### Choose minimum subset of edges in tree that connects all important nodes

Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$. We want to choose subset of edges of the tree such that: For each two important nodes at least one edge ...
23 views

### Following but not intersecting time segments to detect multiple accounts

In some code I'm currently writing, I'm stuck on the following algorithm to implement. The goal is to find real world users using multiple different accounts. I've a List of UserData. This list is ...
38 views

### Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods

When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40. Reference: Here's a reference: https://en....
162 views

### Minimum cost to convert one array to another

Given two arrays $A$ and $B$ of integers, both of size $N$, such that for all $0 \le i \le N-1$, $A[i] \ge B[i]$, we have to convert array $A$ to array $B$. For this we can do only one type of ...
63 views

### Optimise 1D cutting stock problem - maximum waste that can be removed with n cuts

The problem statement can be made as follows. There is a 1D length of raw material that contains "net" and "waste" intervals. Using 2n cuts, sections of material can be removed so that less waste has ...
294 views

### Minimal date interval cover algorithm

The problem involves date intervals filtered by days of week. For example, the filtered interval {2001 APR 1 - 2001 APR 30, 17} corresponds to all Mondays and Sundays between April 1 and April 30. ...
74 views

### Are there Dynamic programming speedups for $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$

I am wondering if there are dynamic programming speedups for the minimization problem $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$. Now I understand that its highly unlikely that such thing would exist for ...
226 views

### Travelling salesman problem with small edge weights

Are there any advantages in finding the shortest tour for the problem if edge weights are much smaller than the number of vertices? Let's say the maximum edge weight is $n$, and the number of ...
53 views

### Best set of orders

I have the ambition to build an application that determents the best set of orders. Let's say I'm an postage-stamp collector. And I have certain postage-stamps on my wish list. On the secondhand-...
47 views

98 views

### Minimum path cover— Disjointed paths with minimum total number of edges

Let $T=(\mathcal{V},\mathcal{E})$ be an udirected acyclic graph and $|\mathcal{V}|=n$. Let $\mathcal{V'}$ be $\mathcal{V'}\subset \mathcal{V}$ where $|\mathcal{V'}|=2m\leq n$. There are $2m \choose 2$ ...
360 views

### Interval scheduling problem with priorities

I have a problem that is similar to the interval scheduling algorithm but it involves priorities. My data sets consist of the following data: Cars with the start and end time of parking, along with ...
62 views

1k 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 ...
42 views

### Finding the maximum of a random forest

If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is ...
94 views

### Local search (Hill Climbing) scope and definition

I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-...
1k views

### Using 2-opt Heuristic in a Genetic Algorithm for TSP

I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (...
66 views

### Appropriate algorithm or heuristic for task scheduling

I'm sure this problem has been addressed before, but I'm unable to find an exact description of it. I have $m$ machines, and $n$ tasks that need processing. Each task takes a variable amount of ...
35 views

29 views

### TSP when cost depends only on location in sequence

I want to change the original TSP problem as follows: the cost to visit a city is not related to the previous city that it visited just now, but only on its position in the sequence. Is the problem of ...
24 views

### How to extract a set $C$ that contains $N$ subsets of a set $B$, covers all elements of an external set $A$, but $N$ is minimal?

Let $A$ denote a set that contains a relatively large number of different strings. Let $S_i$ denote these strings. Let $B$ denote a set of sets such that each subset contains a (relatively small, ...
23 views

### In two sets, identify set of pairs with maximal sum of connections

Given two sets of items $A = { a_1, .., a_N }, B = { b_1, .., b_M },$ and assuming a connection weight $w{_i}_j \ge 0$ between any possible pair $(a_i, b_j)$ that contains one item of each set, how ...
237 views

### Moving an edge in a weighted tree to maximize longest path length

Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$,...
1k views

### Why is integer programming more difficult than (real) linear programming? [duplicate]

Why is integer programming (IP) more difficult than (real) linear programming (LP)? I searched a lot on the web, but I didn't find an answer.
259 views

### ILP runtime seems to be linear?

I have a variation the shortest path problem, formulated as an ILP. The system model is as follows: There is a connected digraph consisting of 20 nodes, with each link having an associated weight ...
21 views

### What are the reasons behind using constraints in convex optimization?

We use the following notation to describe a minimum convex optimization problem: ...
217 views

### solving max cut problem on a huge graph (500 x 500) using Semidefinite Programming with CVXOPT

So I am learning to do SDP relaxation on graph problems, and for this max cut problem I am given a 500*500 graph, and I am using the straightforward relaxation. $W$ is the weight matrix, $X = u u^T$ ...
89 views

### Filling a string with wildcards with minimum cost

You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string. You are allowed to write data to the string in blocks of ...
64 views

### Is it possible to make data structure that will find MEX and support modification queries

Let's say we have given array of $n$ elements, now we want to create data structure that will allow us to get the MEX of its elements, MEX meaning the smallest positive integer that is not present in ...
27 views

### Multi-type max-flow

Suppose you have $m$ sources $s_i$ and $n$ sinks $t_j$, but every source produces a certain type of flow, out of $k$ types, and every sink demands a certain type as well. We would like to know if ...
2k views

### Fitting different rectangles inside a rectangle

I have a fixed rectangle of size X x Y. I also have a bunch of rectangles of different sizes. I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate ...
62 views

### Among $k$ unit vectors, find odd set with sum length less than 1

I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no ...
60 views

### Portfolio allocation with a few twists

A similar question has been asked here, but this one is more complicated and has more constraints. I'm trying to find an algorithm to solve the following (real-life) problem: A customer has $M$ ...
29 views

### Filling a board with maximum number of fixed size tiles

You are given a rectangular board of known size, e.g. 20x20 cm. Some 1x1 cm pieces are missing. Your task is to cover this board with a maximum number of 2x2 cm tiles (an example is attached below), ...
63 views

### What do we call a greedy algorithm that tracks the best $n > 1$ solutions?

A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima. To avoid this problem, we may keep track of the best $n > 1$ ...