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.

Filter by
Sorted by
Tagged with
1
vote
2answers
49 views

Algorithm to solve $L_1$ optimization of $\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$

Is there is an efficient algorithm to solve the following optimization: $\mathbf{x}^* = \arg\min_\mathbf{x}\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$ for given $\mathbf{b_i}, \mathbf{A_i}\ \forall ...
4
votes
1answer
95 views

Heuristics vs meta-heuristics vs hyper-heuristics?

The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic". The wikipedia page on hyper-heuristics states that they are "heuristic ...
1
vote
0answers
32 views

Is a linear classifier convex?

Is the optimization of a linear classifier convex? Is there any local optima or saddle points for a linear classifier?
2
votes
1answer
53 views

Shortest path with nodes containing collectibles of negative cost

Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible ...
1
vote
1answer
157 views

Vertex Cover approximation algorithm

I have an algorithm that solves the Vertex Cover problem. The algorithm is Repeat while there is an edge: Arbitrarily pick an uncovered edge $e = uv$ and add $u$ and $v$ to the solution. ...
0
votes
1answer
32 views

Complexity of linear programming with restricted quadratic constraints

A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $x_i$, there is a variable $s_i$ (intuitively for approximating $x_i^2$, and ...
0
votes
0answers
17 views

How would I optimize a tree-like graph with a significant number of redundant nodes?

Recently, I was looking at the underlying data/implementation of a survey application created using a RPA tool. As a user progresses through the survey, the "decisions" reveal a predominantly tree-...
2
votes
2answers
82 views

Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
0
votes
1answer
136 views

Distribute repeated values into bins as evenly as possible

Preface I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-...
1
vote
0answers
56 views

Big M method for continuous variables

Is there any way to model the big M method for continuous variables? Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$. Due to the precision problem, when the $B$ and $C$ ...
1
vote
1answer
164 views

Minimizing sum of recursive pairwise sums

What is the best algorithm for this? We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at ...
2
votes
2answers
117 views

Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm'

I'm working on solving an algorithm problem defined as follows (important parts in bold): Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a ...
0
votes
3answers
75 views

Find the cheapest combination of raw foods that fulfill nutritional requirements

I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples ...
1
vote
1answer
133 views

Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
2
votes
1answer
128 views

What is the right term/theory for prediction of Binary Variables based upon their continuous value?

I am working with a linear programming problem in which we have around 3500 binary variables. Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
1
vote
0answers
30 views

Algorithm for first-price, sealed bid simultaneous auctions for distinct items and budget-constrained bidders

Context: I play in a simulated online basketball league (a la the NBA) where each human player controls one of the teams. When each simulated basketball player is a free agent (that is, their previous ...
0
votes
0answers
17 views

How to understand the separation phrase for generalized subtour constraints?

Suppose the constraints of our integer programming model consist of two parts: the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the ...
4
votes
0answers
120 views

Maximum-minimum-satisfiability [closed]

In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the ...
0
votes
1answer
36 views

Determining cycle time and and hold time in logic circuits

First I have general question. In a circuit with both logic and D edge flip flop does hold time have to satisfy $t_{hold} < t_{setup}($D-FF$) + t_{pd-min}$(Logic), or is it enough that $t_{hold} \...
5
votes
1answer
110 views

Find a strategy to evade hungry lions on the real line for the longest time

This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up. You are placed on the real line, and there also are $K$ ...
1
vote
1answer
37 views

Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices

I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally: Let: $P$ be a ...
2
votes
0answers
64 views

Given a set of point sets, find points from each set with maximum total distance between them while each distance is larger than a threshold

The title may be a bit confusing but the problem is this; Lets assume I have 5 points in 4 groups (in total 20 points). What I want to achieve is; -> Pick one point from each group (we will have 4 ...
1
vote
1answer
120 views

Help needed for understanding proof of No Regret Multi Armed Bandit Algorithm

I was reading Elad Hazan's book on Online Convex Optimization(http://ocobook.cs.princeton.edu/OCObook.pdf) and am facing difficulty understanding the proof given for the No regret algorithm for MAB (...
1
vote
0answers
21 views

Expected development of 'fitness histogram' for PSO over time

I'm plotting the fitness histogram of my particle swarm optimizer - i.e. the individual fitness scores for each particle and iteration - during a run. The problem tackled is basically curve fitting/...
0
votes
1answer
82 views

Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph

Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+...
0
votes
1answer
134 views

What is the difference in SMO algorithm for SVM and SMO for one class?

Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question? I am trying to understand the difference between the paper : https:/...
2
votes
1answer
37 views

Computational complexity of maximizing sum of rational functions

I have a optimization problem: $$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
0
votes
1answer
63 views

Stable matching with asymmetric arrays (gale shapley)

I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms. One of the answer ...
0
votes
1answer
33 views

If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

My problem is mainly from this lecture notes on convex optimization here page4 Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer ...
0
votes
1answer
53 views

Interpretation of Backtracking Algorithm Problem - weighted matching

I am attempting to resolve the following problem using Backtracking: Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P_{ij}$ is the preference of the man $i$ ...
0
votes
0answers
9 views

Looking for a specific type of ADMM iterates

For a $k-$dimensional optimization variable $b \in \mathbb{R}^k$ say the objective is given as, $$f(b) = \langle b, v \rangle + \langle b , Ab \rangle + \lambda \Vert b \Vert_1$$ for some parameter ...
1
vote
2answers
487 views

Knapsack problem: equal profits

I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal. More formal definition of the problem from a Wikipedia article on KPs: If all the ...
2
votes
1answer
26 views

Positioning items to maximize separation

Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
1answer
62 views

Variant of interval scheduling with varying task durations

I am probably just missing the correct term for my problem to find the solution but here it goes: I have a set of tasks with a given duration and an interval for each task in which it has to be ...
4
votes
1answer
146 views

How to produce nonzero absolute differences between neighboring numbers on a circle as long as possible?

I apologize for the lack of an even better title. The main reason I couldn't find a better one is because I have a problem that I cannot find reference anywhere. I am pretty sure it has a name, but I'...
1
vote
0answers
81 views

NodeJS vs Golang Performance [closed]

I was testing performance of NodeJS vs GoLang with a very simple script. Situation one is three nested for loops to do a Sin calculation and Situation two is just one for loop. It turns out that for ...
1
vote
0answers
22 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
4
votes
1answer
54 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
4
votes
1answer
253 views

Minimize sum of squares of rows in matrix when sum of columns have some constraint

I'm looking for an algorithm that can find any matrix $a_{j,i}$ such that $$ \sum_{i \in I} \left(\sum_{j\in J} a_{j,i}\right)^2 $$ is minimal, while also for each $j\in J$ satisfying the constraint ...
3
votes
2answers
50 views

Optimization Problem when calculating fitness is expensive

I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...
0
votes
1answer
48 views

On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
2
votes
0answers
47 views

How to minimize the number of gates of an arithmetic circuit?

A circuit is simply a DAG, with some input wires, some output wires, and some operations on the vertices. Consider an arithmetic circuit where the only operations are addition ($+$) and ...
1
vote
1answer
476 views

How does the problem of “Scheduling to Minimize Lateness” exhibit optimal substructure?

The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos): Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ ...
0
votes
0answers
38 views

models/formalism for optimization algorithms?

In Wolpert's "No free lunch theorems for optimization", he uses the following formalism for an optimization algorithm: Let $X$ be a finite space of which an element has to be chosen, and let $Y$ be a ...
0
votes
1answer
25 views

What is the difference between the study of Evolutionary algorithm vs. Optimization?

I have a course named "Evolutionary Algorithm". But, our teacher is always mentioning the word "Optimization" in his lectures. I am confused. Is he actually teaching Optimization? If yes, why is the ...
1
vote
1answer
136 views

Optimal substructure and dynamic programming for a variant of the rod cutting problem

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following. Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the ...
2
votes
1answer
42 views

How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there ...
2
votes
1answer
51 views

Optimal assignment of +-1 values to vertices in a graph

Let $(V, E)$ be a simple connected undirected graph, $f: V \to \{-1, +1\}$, and $g: E \to \{-1, +1\}$. The function $g$ is completely defined by $f$, while $f$ is something we get to choose. The only ...
1
vote
1answer
63 views

Knapsack-type problem where the objective function is a ratio

I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole ...
5
votes
0answers
86 views

Specific quadratic 0-1 knapsack problem solvable in linear time?

I am interested in a simple variant of the quadratic knapsack problem. Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...