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
0
votes
1answer
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, ...
0
votes
1answer
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 ...
5
votes
1answer
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\}$,...
3
votes
1answer
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.
1
vote
2answers
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 ...
0
votes
0answers
21 views

What are the reasons behind using constraints in convex optimization?

We use the following notation to describe a minimum convex optimization problem: ...
1
vote
0answers
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$ ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
6
votes
1answer
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 ...
4
votes
2answers
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 ...
1
vote
1answer
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$ ...
2
votes
0answers
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), ...
1
vote
1answer
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$ ...
1
vote
0answers
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 ...
-1
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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,...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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: ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
6
votes
1answer
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 ...
9
votes
1answer
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)$ ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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?
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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: ...
3
votes
1answer
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 ...
1
vote
2answers
308 views

INOI 2017 Problem 2 - Training

INOI 2017, Problem 2, Training Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order. ...
2
votes
0answers
121 views

Find a permutation that maximizes $\sum_i a_{i-1}a_ia_{i+1}$

I want to solve the following problem: You have a list of numbers, for example [10, 33, 7, 7, 12]. The goal is to find the permutation of this list that maximizes the function $\sum_i a_{i-1} ...

1 6 7 8 9 10 26