# Questions tagged [optimization]

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

1,254 questions
Filter by
Sorted by
Tagged with
35 views

### $n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost

I have this problem A ﬁrm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
91 views

### Recursion to DP Solution

There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
49 views

### Finding the best state for chain graph with cycles

I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative)...
41 views

### List of algorithm problems in term of ideals

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
63 views

### Resource allocation / optimization

At work I stumbled across this problem of allocating resources: We are given a set of objects belonging to one of seven possible classes (multiple objects per class are allowed). We distinguish ...
61 views

### Evolutionary optimisation algorithm and graph based search

Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms. Both of these methods entail doing a search on a graph of candidate solutions. Do all other evolutionary ...
86 views

### Finding Conflict algorithm doubt

Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time. I have to find an event that conflict with maximum number of other events. Conflicts means interval ...
77 views

### Solving the Size-Constrained Weighted Set Cover Problem

I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the ...
140 views

### Run-time of Hungarian algorithm - matrix formulation

There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a ...
103 views

### Closest Value instead of Max Value in Knapsack problem

I have a problem like the knapsack problem, except instead of finding the max value, I'm trying to find the closest value to a given value. Anyone know where to start, have a name for this problem, ...
129 views

### Optimal partitioning of n-tuples

Motivation Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
18 views

### Bounds on “well dispersed” sparse matrices

Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is ...
80 views

### Finding optimal multiplication order and optimal binary tree

I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree. Consider the following ...
42 views

### Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached. I thought to run an SCC algorithm to find binding ...
127 views

### Maximum flow with constraints

In a flow network, suppose we add constraints of the following type: The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$. Is maximum-flow with such constraints still ...
16 views

### Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, ...
60 views

### Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa. But which type of repetition is preferable for minimum amount of computational effort and ...
21 views

### If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
27 views

### what can cause the best-bound to get tighter in the first MIP node?

I'm using gurobi MIP optimization engine for solving a mixed integer linear minimization problem. I see that the engine didn't start the branch and bound stage ...
24 views

### Kiln optimization problem

Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings: 102 of A 364 of B 70 of C I can put 50 molds in the kiln at a time. I can have 75 molds made in ...
9 views

### Clarification on descending direction in optimization of function

Could someone clarify for me why given $f:\mathbb{R}^n \rightarrow\mathbb{R}$ to optimize an iterative function according to : $p^k=-M\nabla f(x^k)$ for $p^k$ to be descending direction the matrix M ...
7 views

### What analysis / algorithm helps stabilizing the fit of correlated parameters (but not colinear)?

I have many curves that I want to fit using a convolution of some functions. These functions include Weibull distributions with 2 parameters lambda and ...
10 views

### Most probable inputs assignment in Gaussian process

Given A Guassian process $w(\mu^*,\Sigma^*)$ $n$ observations of the output And $n$ potential inputs. But the assignment of the inputs to the observations is unknown. The goal is to find a inputs-...
15 views

### Disk Scheduling for a Fragmented Hard-Drive

Recently In class I have been learning about simple disk scheduling algorithms such as FCFS, STTF, LOOK, LOOK-SCAN etc. From my understanding these algorithms schedule I/O requests depending on which ...
74 views

### Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem: Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
34 views

### University timetable optimisation - with a twist

I've made a website that helps students at my university optimise their student timetables. Currently, for subjects with not many classes - I can generate and optimise the timetables quite fast. ...
40 views

### Optimizing library dimensions

Say I have a library that looks like that: ...
40 views

### Branch and bound Dual Gap

Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm. I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual ...
37 views

### How fast can we optimally cluster 1-D data?

K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) ...
28 views

### How literally is “optimization” or “optimization algorithm” used in CS?

I have been confronted with two meanings of the term "optimization" or "optimization algorithm": to find the absolute maximum in a set $X$ according to some criterion $f:X\to \mathbb R$ to find a "...
49 views

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 ... 1answer 120 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 ... 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? 1answer 61 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 ... 1answer 201 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. ... 1answer 33 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 ... 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-... 2answers 86 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 ... 1answer 172 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-... 0answers 60 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$... 1answer 210 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 ... 2answers 144 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 ... 3answers 76 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 ... 1answer 233 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)... 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 ... 0answers 32 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 ... 0answers 131 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 ... 1answer 37 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} \...
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$ ...
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 ...