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
1
vote
1answer
26 views

Algorithm for maximizing the number of same-sized groups

Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the ...
1
vote
1answer
28 views

Find maximal subset with interesting weight function

You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th ...
1
vote
1answer
27 views

How important is initial state for local search optimisation?

I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation. I'm wondering how important the ...
1
vote
1answer
23 views

Search for range in continuous function satisfying some condition

I am attempting to define an optimization for the following problem: given a graph find the largest interval(s) where S > S_th (the narrower the interval the ...
1
vote
0answers
18 views

Variant of ridge regression loss function

We can create variants of the loss function, especially of ridge regression by adding more regularizer terms. One of the variants I saw in a book is given below $min_{w \in \mathbf{R}^d} \ \ \alpha....
0
votes
0answers
51 views

Is it possible to form this as a linear program?

My problem is as follows: I have some number $n\in \mathbb{N}$ of items all of size $s\in \mathbb{N}$ that need to be fit into a distributed storage of sizes $[b_1, b_2, ..., b_m], \forall i, b_i \in \...
2
votes
1answer
50 views

How to convert a recursive function to a non recursive one using stack while keeping memoization?

Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'. I could ...
3
votes
1answer
244 views

efficient algorithm for min cut with specified number of vertices

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
2
votes
0answers
42 views

What is the largest sum that can be constructed with the given recipes?

There are $n$ sets of distinct positive integers, $S_1,\ldots,S_n$. There is a set of recipes that allows us to construct tuples of integers from these sets. For example, the recipe {1,2} allows us to ...
2
votes
0answers
22 views

How to linearly combine loss functions to preserve optimal substructure property?

I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
0
votes
0answers
17 views

Minimizing the length a Boolean Algebra Expression in disjunctive normal form

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
4
votes
0answers
44 views

Repeated linear programming with similar (not identical) problems

I have multiple linear programming problems of the form: $$ Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0 $$ Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a ...
1
vote
0answers
43 views

Algorithm for summation with lowest maximum temporary sum

I've got this problem on my last exam, which I struggle to deal with. Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
2
votes
1answer
31 views

Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
1
vote
0answers
68 views

Minimum vertex cover and odd cycles [closed]

Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $...
3
votes
1answer
39 views

Is MAX-averageSAT a well-known problem?

Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an ...
2
votes
2answers
58 views

optimizing for loops

Disclaimer: I'm not a compiler expert. I'm simply curious and come seeking enlightenment. I've seen people claim that -- for efficiency -- for loops should ...
0
votes
0answers
34 views

'Traders's Route' problem optimization algorithm

I've come up with a problem which we'll call the Trader's Route Problem (If it's an already understood problem that would be great as well, let me know). Say there exist N cities, with some arbitrary ...
0
votes
0answers
23 views

Optimal placement of radio towers

Imagine there is an area on which you have to put radio towers. Each radio tower sends signal to a circular area of fixed size. How do I determine the optimal number and placements of these towers so ...
2
votes
1answer
100 views

Minimum vertex cover algorithm with linear programming

Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
0
votes
0answers
20 views

Value Maximisation Algorithm with multiple costs

So in front of me lies different items. To buy each item you will need a certain amount of multiple things. For example, to buy a lamp, you will need to pay 3 apples, 4 oranges and 17 bananas. Each ...
6
votes
2answers
182 views

Odd cycle transversal and linear programming

Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ ...
0
votes
0answers
54 views

Why can't a compiler just “think more” about optimization?

This happens to me from time to time: I compile my code with the highest optimization level (-Ofast) of the allegedly fastest compiler (GCC) of one of the fastest ...
3
votes
0answers
40 views

I'ld like a better algorithm for scheduling tutors to fill a set of shifts

My problem is as follows: I have a set of shifts at various locations that need to be filled by tutors. A simple example would be basic math in room A on M, W, F from 9-11am and Sa from 12-3 pm. ...
1
vote
0answers
50 views

Mathematical limits on lossless data compression

Let's say Bob wants to send a particular binary sequence to Alice. Imagine that Bob and Alice both have powerful machines but slow Internet connections. Bob could just send the sequence directly but ...
2
votes
1answer
80 views

Maximization problem on finite collection of finite sets

Problem I am considering the following maximization problem: Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$. Goal is to find a subset $G \subseteq \mathcal{F}$...
1
vote
0answers
32 views

Baum-Welch Algorithm

I was reading the book by Jurafsky and this is written by the author on HMM Although in principle the forward-backward algorithm can do completely unsu- pervised learning of the A and B parameters, ...
0
votes
0answers
17 views

Newton method using automatic differentiation

I wrote a large Matlab code which solves partial differential equations. Now I would like to test the code on nonlinear problems, for which I need the Newton-Raphson iteration for systems of nonlinear ...
1
vote
0answers
24 views

Finding Smallest Frontier for Graphs of bounded pathwidth

Let $G$ be a graph and $X=x_1,x_2,...,x_n$ be an permutation/ordering of the vertex set of $G$. We then let $S_i = \{x_j:j\le i\}$, and $F_i$ be the number vertices $v\in S_i$ that are adjacent to ...
2
votes
1answer
45 views

Code optimization - syntax tree vs. intermediate representation

I'm working on a compiler for my own custom language. As I was reading an article on code optimization, I noticed that it assumed that the intermediate representation of the code had already been ...
0
votes
0answers
30 views

Is finding the mean of the subset with the smallest variance NP-hard? [closed]

Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. For simplicity, suppose that $\alpha n$ is an integer. Let's consider the following problem $\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\...
0
votes
0answers
40 views

Which advanced data structure to use?

For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
1
vote
0answers
51 views

Which non convex optimization algorithms guarantee a global optima?

Most non-convex optimization algorithms I have come across so far rely basically on random restart to find a better solution. e.g. Genetic Algorithm, Simulated Annealing, Metropolis Hastings Monte ...
0
votes
0answers
21 views

What is the best way to identify highly performing groups?

I am currently working on a project that involves sorting people into groups based on their ability to work well with others. While it is a bit of a simplification, I have a problem that is ...
1
vote
1answer
21 views

Optimal Selection of Non-Overlapping Jobs

I'm trying to find what the family of problem is - as well as an approach - for the following: I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri. Each task ...
0
votes
1answer
46 views

What properties of a discrete function make it a theoretically useful objective function?

A few things to get out of the way first: I'm not asking what properties the function must have such that a global optimum exists, we assume that the objective function has a (possibly non-unique) ...
0
votes
0answers
25 views

Is there any good method to find if a grammar is optimal for a problem?

I've been thinking about grammatical evolution problems and how the grammar influences the algorithm performance. It came to my mind the huge impact that the grammar that you're using has in the time ...
1
vote
0answers
37 views

Clustering sets by set difference

Suppose you have $n$ nonequal sets $S_1, \ldots, S_n$ and some constant $0 \le k < n$. The goal of set clustering is to find a partition of the set $\mathbf{S} = \{S_1, \ldots, S_n\}$ such that the ...
3
votes
1answer
29 views

How to leverage the fact that I'm solving 1000's of very similar SMT instances?

I have a core SMT solver problem consisting of 100,000 bit-vector array clauses, and one 10000-dimensional bit-vector array. Then, my program takes as input k << 100,000 new clauses, and adds ...
5
votes
1answer
69 views

Maximize area of light with 4 light sources on a diagram of a room

Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized. Here is a simple ...
2
votes
1answer
21 views

Force-directed graph optimization with step-wise costs and constraints

Introduction I have an optimization problem. There are up to 25 nodes. The connectivity between the nodes is far less important than the Cartesian placement of the nodes. Since all nodes can ...
1
vote
0answers
53 views

Searching a 2D array of binary Data

I'm working on optimizing the structure of an optical meta device. I have a randomly generated 2D matrix, where 0,1 represents the presence/absence of a hole. Each structure manipulates light ...
0
votes
0answers
17 views

How to consider combinatorial optimization problem with multiple objectives?

I am considering a combinatorial optimization problem with two objectives. The two objectives have a trade-off between each other which means if I minimized the first objective alone it gives the ...
2
votes
0answers
51 views

BFGS vs. Levenberg-Marquardt

I know that BFGS is a general quasi-Newton method, whereas Levenberg-Marquardt (LM) is specifically for non-linear least squares (NLLS). That said, is there a big advantage of using LM instead of BFGS ...
2
votes
1answer
22 views

Why do particles in particle swarm optimization converge to the global best when their personal best has just as much weight?

I know this is probably a really basic question but I just cant wrap my head around it right now. So the basic PSO update formula is as follows: $$\bar{v}_{n+1} = \omega \cdot \bar{v}_n + c_k \cdot ...
0
votes
1answer
41 views

In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
0
votes
0answers
16 views

Bounding 0-1 matrix with k unique rows

Problem Statement: Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the ...
1
vote
1answer
35 views

Find position in array where element-wise multiplication with string of 1 and 0s results in max value

I have a sequence of 1s and 0s. For example: $bits = [1, 0, 1, 1, 1, 0]$. I also have an array of positive integers. For example $arr = [12, 23, 4, 6, 8, 0, 24, 72]$. I need to find the index, $i$, in ...
4
votes
0answers
24 views

Constructing xor separable boolean upper bound

Problem statement Suppose I have a boolean function $f: \mathbb{F}_2^n \times \mathbb{F}_2^m \to \mathbb{F}_2$ where $\mathbb{F}_2 = \{0,1\}$. I define two boolean functions $h: \mathbb{F}_2^n \to \...
0
votes
1answer
18 views

Picking the most cost efficient sets

I have two 2D arrays: $P[n][s]$ and $C[n][s]$, $s \leq n$. P contains sets of nodes and $C$ the cost of a set in $P$, e.g. the cost of $P[2][2]$ is $C[2][2]$ and a set $p \in P = \{ s_0, s_1, ..., s_{...

1
2 3 4 5
29