Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
2
votes
2answers
50 views

How to use `cplexAPI` to solve quadratic programs/quadratically constrained linear programs?

I am trying to use cplexAPI to solve quadratic programs or quadratically constrained linear program. While it seems to be pretty straightforward to use ...
2
votes
0answers
87 views

Harvest planning problem

I need to model the following problem: For a planning horizon of $P$ equal periods, one has $N$ harvesting locations and $K$ contractors who can harvest at those locations ($K < N$). Each ...
5
votes
2answers
119 views

In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?

In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something. I'm working ...
1
vote
1answer
78 views

Resource Optimization For Cargo Handling

I have to work on some real world data and come up with an optimization technique to handle cargo. To make thing simpler let's assume that there are 2 types of resources Manpower (150 ton / 8 hour) ...
2
votes
0answers
50 views

How to write the constraint matrix for this blending problem?

Below is a model for maximizing a utility function, a blending of, 3 ingredients $(A, B,C)$ to obtain 3 mixes of fertilizer, with the recipe given as proportions. Ingredients cost $A=130,\ B=150,\ C=...
4
votes
1answer
112 views

Alternate formulation for modeling inventory constraints

I'm working on a inventory optimization problem where inventory used at a time-period is computed based on price-bucket that is selected for an item. Problem contains multiple items (around 10K), 15-...
4
votes
1answer
96 views

LP solver CPLEX is 'optimal with unscaled infeasabilities'?

The problem being solved is finding the truss with the least weight, exactly done as on this website: https://www.layopt.com/truss/. This method is also called the ground structure method. I am aiming ...
2
votes
1answer
62 views

Optimization Problem: Recommending Service Providers to Clients

I am new to optimization, not sure if the problem described below is trivial. Any guidance on solution or nudge in the right direction would be very helpful. Problem: There are two groups – clients ...
2
votes
1answer
123 views

Tuning the coefficients of an objective function of LP

I want to solve a problem that results in this general objective function which I want to maximize: $$a\cdot x_1+b\cdot x_2-c\cdot x_3-d\cdot x_4+e\cdot x_5$$ When I write out in full this objective ...
2
votes
1answer
67 views

Suggestions how to get access to MINTO MILP solver?

I came across the MINTO MILP solver today. A solver i wasn't aware of or at least had not paid attention too. While development seem to have stopped two decades ago however i still wouldn't mind ...
2
votes
0answers
72 views

What if anything do linear relaxations of "nearby" MILP nodes tell us about other MILP nodes

Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree. ...
4
votes
1answer
83 views

Maximizing sum of step functions under single linear constraint

I am trying to efficiently solve the following optimization problem: \begin{align}\max_{b \in \mathbb{R}_+^D}&\quad\sum_{n=1}^{N}\operatorname H(b^T w^{(n)} - c^{(n)}) \\\text{s.t.}&\quad\sum_{...
4
votes
1answer
89 views

Why does setting up a problem using Excel's OpenSolver slows down after 24,000 variables?

I am modeling a big linear programming problem size with about 50,000 variables using OpenSolver. Open Solver starts setting up the problem at a constant pace of about 100 variables per second, which ...
6
votes
2answers
359 views

How to model this expression?

Suppose $0\le x \le 1$ is a decision variable and $\gamma(x)$ is defined as follows: $$ \gamma(x)= \begin{cases} \theta & x>0\\ 0 & x=0 \end{cases} $$ where $0\le \theta\le 1$. In my model, ...
3
votes
1answer
56 views

How to specify an objective function that prohibits trading in both directions linearly

I am building a small model that trades water and buys water. For simplicity reasons, I am only discussing the relevant constraints: $\sf varWaterIn_h$ is the amount in litres of water bought per hour,...
5
votes
1answer
118 views

Do you know of any formula to calculate the difficulty score of Sudoku?

I am looking for a formula to measure the difficulty level of a Sudoku solution.
8
votes
4answers
440 views

What is the best open source solver for large scale LP optimization in pyomo?

I have used Gurobi and cplex for solving large scale LP problems with Pyomo. However, I do need to use open source solver. Any advise? glpk and cbc seems to be very slow in solving the problem (with ...
6
votes
2answers
200 views

Heuristic solution to the graph partitioning problem

I am working on a graph partitioning problem. A static column generation based solution was proposed in How to partition a graph with optimal number of groups? But I need some MILP solver to solve ...
2
votes
1answer
117 views

Benders Decomposition cuts for MILP problem with further separable subproblems

I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
4
votes
2answers
187 views

Multi-product distribution modeling : too many constraints

I have received many helps to model the problem, thank's for that ! I just edited the post to make clear what my actuel problem is. The following model is giving me amazing results with few products (...
1
vote
1answer
103 views

Conditional constraints in PuLP

I have the following optimization model using PuLP. ...
1
vote
1answer
68 views

LPs having a 'stable' objective value wrt changes in the constraint right-hand sides

I have a problem as: $$ \begin{align} \begin{array}{cl} \underset{x \in \mathbb{R}^n_+}{\min} & c^\top x \\ \mathrm{s.t.} & Ax \leq \mathbf{1} \cdot b , \end{array} \end{align} $$ where $A \in ...
3
votes
2answers
58 views

Write in ILP: If $x$ within range then $s=1$, else $0$

How can write the following function in LP: $$ s= \begin{cases} 1 & 1 \leq x \leq C \\ 0 & \text{otherwise} \end{cases} $$ where $x$ takes only non-negative integers and $C$ is some large ...
2
votes
1answer
112 views

Benders decompositions: Number of iterations does not remain the same

I am solving an LP (i.e 118-bus system economic dispatch for 130% loading) using Benders decomposition. The problem takes 26 iterations to converge. This means that the process adds 25 cuts to the ...
1
vote
0answers
73 views

Optimisation Multiple Constraints

I am trying to solve a linear algebra problem: an optimisation problem and I am using CVXOPT. I've split the problem into 3 components In its simplest form, The general formulation for CVXOPT is \...
4
votes
1answer
183 views

Are decomposition methods applicable on large linear programs?

Working on a very large Linear Program, we tried out some primitive implementations of decomposition techniques such as Lagrangian relaxation and column generation. However, none of these were able to ...
9
votes
2answers
164 views

Are there small LPs out there?

A fair share of academic research and software development focuses on solving ever-larger problems, particularly when it comes to LPs. I am however curious to know in what contexts and to what extent ...
2
votes
1answer
84 views

Linearly independent rows in simplex

I'm having some trouble understanding about the independent rows in a basic solution. In the book Introduction to linear optimization by B&T, the authors give the definition of a basic solution as ...
6
votes
1answer
100 views

Upper and lower bounds of a variable equal

I'm working on a MILP (Mixed-Integer Linear Programming) problem with the Java API of Cplex. In order to easily exclude some variables from my problem I thought about setting both their lower and ...
2
votes
1answer
73 views

Examples of LP problems in irrigate engineering

I need examples of linear programming problems applied to irrigation system. My idea is to give students many examples of LP applications in the irrigation engineering.
2
votes
0answers
81 views

Minimax problem with a large high dimensional feasible region

How to solve minimax mixed integer problem with a large high dimensional feasible region? \begin{aligned} \max_{\vec{x}}\min_{\vec{y}} \quad & \vec{r} \cdot \vec{x} + \vec{s} \cdot \vec{y}\\ \...
2
votes
1answer
91 views

KKT conditions analysis for binary constraints

I am wondering if boolean constraints in a linear program can be solved (after linear relaxation from $x\in\{0,1\}$ to both $x\ge0$ and $x\le1$) using KKT analysis. Most of the algorithms that I have ...
3
votes
1answer
119 views

Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT

I am trying to convert a boolean LP to LP using LP relaxation by converting $x \in {0,1}$ to both $x \ge 0$ and $x \le 1$. Then to use it in my problem analysis, I am trying to build the KKT ...
5
votes
1answer
281 views

Model "if and only if" indicator constraints in Linear programming

Apologies if this question has been asked, but I haven't been able to find it. I'm modelling something with Gurobi and want to do the following: \begin{align}\text{cond} < \dfrac{1}{3} &\iff x =...
4
votes
1answer
231 views

CPLEX log always the same after hours ("Gap" and "Best Integer" always blanks)

I'm using the Java API of CPLEX 12.6.1 (with license) to solve a MILP (Mixed-Integer Linear Programming) maximization problem. The point is that, after 21 hours, CPLEX has consumed 32 GB of RAM and ...
3
votes
1answer
77 views

Need help with an appointment scheduling problem

I am currently stuck on writing a linear programming model to describe the process of appointment scheduling for an Oncological Center. I wanted to share it with you guys and see if anyone here could ...
1
vote
1answer
53 views

Employee allocation based on ranking: Mathematical Model

Suppose I have three employees and I have to assign three employees based on their ranks. If an employee has rank 1 that means he is best. Say, I have the following table ...
4
votes
0answers
193 views

Simplified risk game: writing a pratical Minimax objective for mixed integer programming

Problem To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount ...
-2
votes
1answer
76 views

MODM to create balanced groups of students to maximise diversity

I am very new to LP, Goal Seek, Decision Models etc and I have a multiple-objective decision making problem that may or may not require a mix of techniques although I am trying to solve it purely ...
4
votes
1answer
79 views

An efficient Integer programming model for the minimum spanning tree problem?

Let $T=(V, E')$ be a spanning tree of a graph $G=(V, E)$. Rather than verifying for any subset of vertices $S\subseteq V$ that $|E'(S)|=|S|-1$, is there an efficient way to satisfy the spanning tree ...
3
votes
1answer
121 views

Best way to add dummy to transportation problem? Zero cost will be always chosen first?

I know that an unbalanced transportation problem could be made a balanced transportation problem by adding a dummy node which equals the difference between demand and supply. In literature, dummy ...
5
votes
1answer
245 views

What is a good way to penalise LP relaxation?

I have a binary integer program. It is of a large size and the solver is taking longer time. I am thinking of relaxing the binary integer variable and making it a continuous variable. How can I ...
2
votes
0answers
56 views

How is the dual revised simplex method equivalent to running the RSM on the dual problem?

I've seen the claim (in the title) several places, but can't quite understand why it's true. From what I understand so far, the revised simplex method solves an LP in standard computational form, $$\...
2
votes
2answers
92 views

Transformations that leave the linear program unchanged

A typical linear program is written as $$L_0:\min_{x \geq 0; A^\top x \leq b}c^\top x.$$ Here, $x \in \mathbb{R}^n$, $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$. ...
0
votes
1answer
94 views

Objective function with exponential coefficients

I have a linear programming problem, with $n$ variables and $a\leq x_{i} \leq b$ for each variable $x_{i}$, where the objective function is $\min \sum\limits_{i=1}^{n}{2^{i} x_{i}}$ Is it true that, ...
10
votes
1answer
640 views

Linear Optimization Library for C++ with GPU Support

Does anyone know any linear optimization libraries for C++ supporting GPUs for parallelization? If multiple, which do you recommend? The GPU support is important to me since I am dealing with large ...
-4
votes
1answer
102 views

Multiple If else constraints in Mixed integer programming

How to formulate the following as constraints in MILP? a[0][0] = y, if x[0]= 0, a[0][0] = 0, if x[0] != 0, . . . . a[i][j] = b[i][j-1] + y, if x[j]=i, a[i][j] = a[i][j-1], if x[j] != i, ... . . . b[0]...
1
vote
0answers
49 views

Specializing Iterations of Dantzig-Wolfe Decomposition with an Oracle

This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the bounded ...
5
votes
2answers
166 views

Asymmetric time-constrained capacitated vehicle routing problem

I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)1 (pp.4). The mentioned model caps the travel distance, while I cap the travel time. Let $U$ represent ...
4
votes
1answer
116 views

Extreme points of a simple polyhedron

Consider the polyhedron given by the set of inequalities \begin{align} \mathbf{b}^T\mathbf{x} ~&\leq~ c \\ \mathbf{e}^T\mathbf{x} - 1 ~&\leq~0 \\ \mathbf{x}~&\geq~0 \end{align} where $\...

1
2 3 4 5
8