Bismark Singh

Supermodularity, Curvature, and Convex Relaxations in a Class of Quadratic Binary Optimization Problems

  • Bismark Singh
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization Tags , , ,

    We study the combinatorial structure of a quadratic set function $F(S)$ arising from a class of binary optimization models within the family of undesirable facility location problems. Despite strong empirical evidence of nested optimal solutions in previously studied real-world instances, we show that $F(S)$ is, in general, neither submodular nor supermodular. To quantify deviation from … Read more

    Measuring the Economic Value of Wind–Solar Complementarity in Europe Using Chance Constraints

  • Montree Jaidee
  • Bismark Singh
    • Categories Energy, Stochastic Programming Tags , , , ,

    The variability of wind and solar photovoltaic (PV) generation poses significant risks for producers in day-ahead electricity markets, where commitments must be made before actual output is realized. A common mitigation strategy is to invest in storage, but an alternative is to exploit the natural complementarity between wind and solar resources. We evaluate this economic … Read more

    On the Resolution of Ties in Fair Convex Allocation Problems

  • Bismark Singh
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    We study the emergence of indistinguishable, but structurally distinct, allocation outcomes in convex resource allocation models. Such outcomes occur when different users receive proportionally identical allocations despite differences in initial conditions, eligibility sets, or priority weights. We formalize this behavior and analyze the structural conditions under which it arises, with a focus on fairness-oriented objectives. … Read more

    Constrained Enumeration of Lucky Tickets: Prime Digits, Uniqueness, and Greedy Heuristics

  • Bismark Singh
    • Categories Basic Sciences Applications, Optimization in Data Science

    We revisit the classical Lucky Ticket (LT) enumeration problem, in which an even-digit number is called lucky if the sum of the digits of its first half equals to that of its second half. We introduce two new subclasses — SuperLucky Tickets (SLTs), where all digits are distinct, and LuckyPrime Tickets (LPTs), where all digits … Read more

    An analytical lower bound for a class of minimizing quadratic integer optimization problems

  • Christian Schmitt
  • Bismark Singh
    • Categories Combinatorial Optimization, Integer Programming, Quadratic Programming Tags , , ,

    Lower bounds on minimization problems are essential for convergence of both branching-based and iterative solution methods for optimization problems. They are also required for evaluating the quality of feasible solutions by providing conservative optimality gaps. We provide an analytical lower bound for a class of quadratic optimization problems with binary decision variables. In contrast to … Read more

    The Prime Programming Problem: Formulations and Solution Methods

  • Montree Jaidee
  • Bismark Singh
    • Categories Integer Programming Tags , , , ,

    We introduce the prime programming problem as a subclass of integer programming. These optimization models impose the restriction of feasible solutions being prime numbers. Then, we demonstrate how several classical problems in number theory can be formulated as prime programs. To solve such problems with a commercial optimization solver, we extend the branch-and-bound procedure of … Read more

    The Balanced Facility Location Problem: Complexity and Heuristics

  • Malena Schmidt
  • Bismark Singh
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

    In a recent work, Schmitt and Singh propose a new quadratic facility location model to address ecological challenges faced by policymakers in Bavaria, Germany. Building on this previous work, we significantly extend our understanding of this new problem. We develop connections to traditional combinatorial optimization models and show the problem is NP-hard. We then develop … Read more

    Statistical performance of subgradient step-size update rules in Lagrangian relaxations of chance-constrained optimization models

  • Charlotte Ritter
  • Bismark Singh
    • Categories Stochastic Programming Tags , , , ,

    Published in Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-031-47859-8_26 Lagrangian relaxation schemes, coupled with a subgradient procedure, are frequently employed to solve chance-constrained optimization models. The subgradient procedure typically relies on a step-size update rule. Although there is extensive research on the properties of these step-size update rules, there is little consensus on which rules are … Read more

    Quadratic Optimization Models for Balancing Preferential Access and Fairness: Formulations and Optimality Conditions

  • Christian Schmitt
  • Bismark Singh
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , , ,

    Published in INFORMS Journal on Computing. https://doi.org/10.1007/978-3-031-47859-8_26 Typically, within facility location problems, fairness is defined in terms of accessibility of users. However, for facilities perceived as undesirable by communities hosting them, fairness between the usage of facilities becomes especially important. Limited research exists on this notion of fairness. To close this gap, we develop a series … Read more

    Boole-Bonferroni Inequalities to Approximately Determine Optimal Arrangements

  • Bismark Singh
    • Categories Approximation Algorithms, Combinatorial Optimization, Integer Programming

    We consider the problem of laying out several objects in an equal number of pre-defined positions. Objects are allowed finitely many orientations, can overlap each other, and must be arranged contiguously. We are particularly interested in the case when the evaluation of the dimensions of the objects requires computational or physical effort. We develop a … Read more