# Questions tagged [optimization]

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

1,283 questions
Filter by
Sorted by
Tagged with
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.
262 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: ...
225 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$ ...
91 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 ...
69 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 ...
64 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 ...
61 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$ ...
30 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), ...
64 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$ ...
52 views

### Unknown length of chromosone in genetic algorithm

I've read some about genetic algorithms and the general approach, but I haven't found anything about using it when the length of the solution is unknown. How would the generation of the initial ...
43 views

### Global optimization algorithm based on MapReduce

In the field of the intelligent swarm, there are many algorithms can find global optimization, such as Ant Colony Optimization (ACO), particle swarm optimization (PSO). Is there any optimization ...
169 views

### Lower bounds on regret

In "regret" styled analysis over $T$ steps of an iterative algorithm $\{x_i \in F \}_{i=1}^T$ (where $F$ is some feasible set) being given the sequence of loss functions $\{ f_i\}_{i=1}^T$ one defines ...
304 views

### Are the No Free Lunch theorems useful for anything?

I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here,...
89 views

### long-lived scheduling using max-flow & push/relabel

I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now ...
224 views

### Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
87 views

### Shift Organization algorithms (Constraint Programming + Marriage problem)

I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition: Daily shifts must be covered by workers, who are divided in three groups: ...
45 views

### Is this problem about picking optimal entries of a matrix NP-complete?

I am trying to solve a real-world problem that I was able to reduce to the problem described below. I would like to know the following things: Is there literature about this problem? Is the ...
37 views

### What is a logical approach to developing an algorithm which can find the optimal parameters for a function which make it best fit a given data set?

Consider the highlighted columns in the following table: Starting with 100,000 newborns, $l_{x+2}$ denotes the number of individuals in the sample still alive at age $x+2$. If we consider Makeham's ...
69 views

### Finding the number of ways to partition $\{1,…,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$

I am trying to think of how to optimize the following problem: Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$? I ...
450 views

### How to find the supremum over all the “good” (interior) polytopes for a given set of 3D points?

Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x_0,y_0,z_0)$ be the origin/point of reference. We consider a convex polytope $P$ good / interior if: $P$ is wholly contained ...
272 views

### How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$

I see many algorithmic problems that always reduce to something a long the lines of: You have an integer array $h[1..n]\geq 0$, you need to find $i,j$ such that maximizes $(h[j]-h[i])(j-i)$ in $O(n)$ ...
66 views

### Dynamic path planning and waypoint sorting

Good evening everyone, I have a question that I am having a bit of trouble formulating properly and thus it is making it complicated to look up literature on the subject. What I am looking for is a ...
363 views

### Are there practical methods for solving ILP?

Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms! Is solving an ...
85 views

### Simulated annealing upper bound seems way too high

In a nutshell I found this paper that provides an upper bound for the amount of iterations we expect before visiting the global optimum at least once. (It then uses that number to find a lower bound ...
161 views

### Converting nested absolute value into linear programming

I am having trouble writing the following optimization problem as a linear program (LP) $$\min_{x \in \mathbb R^2} \big| | x_{1} - a_{1} | - | x_{2} - a_{2} | \big|$$ where $a \in \mathbb Z^2$ is ...
34 views

### Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)

I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different. All I managed to think of was the ...
178 views

### Efficient bucketing of numbers

Assume we have a sorted list of n numbers, I want to map those numbers to m buckets or clusters. For each bucket the average of all numbers in that bucket will be computed. The task is to find a ...
34 views

### suggestion for optimization problem with $\ell_{2,1}$ norm and Frobenius norm

Suppose I derive my application problem as the following type of optimization problem: $$\min_X ||X||_{2,1}+||X^\top||_{2,1}+||X-A||_F,$$ where $X$ is a (square) matrix, $A$ is a constant matrix. I ...
74 views

### Maximizing the sum of adjacent pairs of elements

I encountered the following interesting problem on stackoverflow: Given numbers $a(1)<\cdots<a(n)$, find a permutation $\pi$ that maximizes $$\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$ The ...
48 views

### Algorithm to find most efficent partitioning of a set

Given a set $S$ with a finite number of elements, where each $s_i\in S$ is itself a set with a finite number of elements, how do you partition $S$ using as few partitions as possible, such that all ...
49 views

### How to approach homework about graph traversal

I am given a connected, weighted undirected graph. I must obtain minimum possible weight sum of "marked" vertexes in the graph. Vertexes must be marked so that each simple cycle contains at least ...
83 views

### Does big-Oh notation in optimization follow the same convention as in CS?

I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class. Now I am doing a project on optimization. In our optimization class, we ...
32 views

### Minimum fare price on public transportation network

In a public transportation network each stop has an assigned zone. The price of a trip depends on the number of adjacent zones that the user touches during a given trip. If the user touches two ...
13 views

### Relating indexes for parameters and variables

I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help. I have the following ...
1k views

### What is a ridge - Hill climbing

I do not understand what is a ridge for hill climbing. The definition I found is a place where all points appear like a maximum, but how is that different than a plateau?
30 views

### Minimum expected cost through an unconventional graph with probabilities at which edges are selected

I'm having trouble identifying the approach to minimize the cost of reaching a certain state in an optimization problem. I've modeled it here as a game. Problem Structure You buy heroes and send them ...
33 views

### Algorithm to select sets of objects while maximizing number of objects covered

If we have different objects, [A1, A2, A3, B1, B2, B3, B4, B5] Some calculations will be performed to find compatible objects. For example, lets assume following ...
150 views

### Optimization of coefficients by using genetic algorithm

I want to optimization the coefficient of FIR filter using genetic algorithm method. The main data structures in the Genetic Algorithm are: chromosomes (vector) objective function values fitness ...
720 views

### How to construct the objective function for genetic algorithm optimization?

I am trying to optimize a coefficients of filter by minimizing sum-squared error. I want to use a genetic algorithm (GA) optimization wherein the coefficients of filter form the GA's chromosome (a ...
475 views

### How to classify a 3D “Knapsack” problem where the only limitation is space, i.e. there is no weight constraint?

The problem is defined as: pack a 3D space with a given list of 3 types of cuboids which are each assigned a value, trying to either completely fill the space or to achieve the highest total value of ...
445 views

### Finding the shortest sublist that contains all search terms

I've been trying to get better at writing algorithms and came across a problem that was something like this: Given a list of words: ...
66 views

### Buying as many items for as much money

I cant find a way to implement a certain solution. Let me flesh out the problem. Somebody gives you X amount of money and sends you to the shop to buy Y amount of items. You must spend as much money ...